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是多项式。