這也是一個奇怪的講題。
定理意思是 ，如果P 不等於 NP, 則存在某個問題L，不是P，也不是 NP complete.
簡單說 ，就是，他們兩個中間還有很多問題~~~。
這也是目前大家believe的結果，很多難題，像是factoring, graph isomorphism 等等問題
都被認為是這樣類型的問題。
不過要證明這定理，這裡多做一個假設叫做:
exponential time hypothesis (ETH)
意思是假設，sat ，不只沒有Polynomial time algorithm。而且只有指數型的algorithm。
不能再更小了。
如下，則可以證明:Ladner's Theorem
Go back to Main page Notes for Complexity theory
No comments:
Post a Comment