NP硬度邊界

Question

我有兩個問題。

1. 有大小爲k的在圖中的集團？ NP硬

2. 在圖中是否有一個大小爲50的集團？ - 可以在多項式時間爲O（n^50）

爲什麼第二個問題不是NP難，其中的第一個是被發現 ？

編輯：！假設P = NP

Answer 1

第一個問題是NP-hard，因爲任意NP完全問題（比如3-SAT）可以在多項式時間內減少到它。 （根據NP硬度的定義）

第二個問題不是NP難題，因爲任意的NP完全問題不能簡化爲它（比如3-SAT，有> 50個子句）。

事實上，第二個問題是在P，因爲O(n^50)屬於P.但是，這不是原因，它不是NP難（特別是，NP 並不意味着非多項式）。

Answer 2

n^k是指數的，而n^50是多項式。