什麼是NP-中級問題？

Question

假設P！= NP

歐拉圖顯示的部分不是P和NP完整的一部分。我在維基百科上讀到這個集合稱爲NP-Intermediate。

Euler Diagram

我有些懷疑，如何定義NPI問題？

Answer 1

的NP - 中間的問題是決策問題

• 是NP（即回答 「是」 可以在多項式時間內驗證），
• 不P（也就是說，沒有用於解決問題的多項式時間算法），並且
• 不是NP -complete。

最後一個標準可以用許多不同的方式來陳述。一種說法是，從SAT到那個特定問題沒有多項式時間映射的減少。

這些問題主要的理論興趣，因爲現在我們不知道是否存在任何NP - 中間的問題 - 如果我們能找到一個，我們不得不在NP的問題，這不是在P，這意味着P ≠ NP！然而，他們是有趣的，因爲如果我們能證明P ≠ NP，那麼我們知道，有在一些問題NP是太難了在多項式時間內解決，但不中在NP（問題是NP -complete）中的「最難」的難題。

倘若P = NP，那麼就不會有任何NP - 中間的問題，因爲你不能有一個問題在NP但不是在P。如果P ≠ NP，然後拉德納定理保證至少一個NP - 中間存在問題，而是通過專門構建的一個問題是高度人工化這樣做而只是爲在這種情況下，NP - 中間。現在，除少數例外（特別是graph isomorphism problem），我們知道所有的問題在NP要麼正視在P或已知NP -complete。