天才宇 發問時間: 科學數學 · 9 年前

"NP-complete"和"時間複雜度"之間的關係?

如題,請問"NP-complete"和"時間複雜度"之間的關係為何?

如何證明某個問題是屬於NP-complete?

可以由時間複雜度來證明某個問題是屬於NP-complete嗎?

謝謝指教。

1 個解答

評分
  • 9 年前
    最佳解答

    請問"NP-complete"和"時間複雜度"之間的關係為何?

    NP-complete 是 NP-hard 與 NP 的交集. 它的時間複雜度已知是 polynomial time only on non-deterministic Turing machine. 若是將來有人証出用polynomial time on deterministic Turing machine 那就是証明 NP=P

    如何證明某個問題是屬於NP-complete?

    通常要證明某個問題 P1 是屬於NP-complete 就是拿另一已知 NP-complete問題 P2.

    從 P1 reduce 到P2 in polynomial time 或是

    從 P2 reduce 到P1 in polynomial time

    可以由時間複雜度來證明某個問題是屬於NP-complete嗎?

    不行 因為妳沒有辦法證明妳得到的時間複雜度是最佳的

    若是可以的話 那妳就是証明了 NP不等於P了

    不過 妳是可以由時間複雜度來證明某個問題是屬於 P

    謝謝指教。

    不謝!

    九年級時候教的 有點忘記了

    所以沒有辦法去簡單地向妳解釋 non-deterministic Turing machine v. deterministic TM. Sorry!

還有問題?馬上發問,尋求解答。