這也是一個奇怪的講題。
定理意思是 ,如果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