作者cmlrdg (心之语)
看板Prob_Solve
标题[请益] 关於gap theorem的证明
时间Thu Aug 21 03:54:03 2008
我最近在读computational complexity
(Papadimitriou写的那本)
读到gap theorem的时候
(gap theorem: 存在有recursive function f
使得 TIME(f(n)) = TIME(2^f(n)) )
看不懂他的证明@@"
请教各位大大
是否有比较浅显易懂的证明?
或者有谁可以解释Papadimitriou的证明? XD
感激不尽 <(_ _)>
--
我是新手@@, 感谢各位的指教 <(_ _)>
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.5.39