推 da0910cc:感謝~!!!!~~!! 06/19 10:00
推 da0910cc:請問甚麼是super-polnomial 囧rz 06/19 10:11
推 da0910cc:忘了google 慚愧 謝謝大大 06/19 21:56
※ 引述《da0910cc (da0910cc)》之銘言：
: ※ 引述《da0910cc (da0910cc)》之銘言：
: : consider a NP-complete problem.Is it meaningful to give a lower bound of this
: : NP-complete problem?
: : Does it make sense to talk about the upper bound of this problem?
: 因為NPC是NP問題也是NP-hard,既然是nondeterminstic 討論upper就沒意義
: 因為可以非常複雜 lower才有討論的價值
: .....
: 這樣解對嗎@@?
: 有沒有大大能為我解惑 囧
如果證明了NPC問題有super-polnomial的lower bound，那麼你就證明NP != P。
如果證明NPC問題有polynomial的upper bound，那麼你就證明NP = P。
以這角度來看，upper bound和lower bound都有意義。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50