作者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