NP Hardness boundary
I have two problems.
开发者_Python百科
Is there a clique of size k in a graph? NP Hard
Is there a clique of size 50 in a graph? - Can be found out in polynomial time O(n^50)
Why is the second problem not NP hard where as the first one is?
EDIT: Assuming P!=NP
n^k
is exponential whereas n^50
is polynomial.
The first problem is NP-hard because an arbitrary NP-complete problem (say, 3-SAT) can be reduced to it in polynomial time. (by the definition of NP-hardness)
The second problem is not NP-hard, because an arbitrary NP-complete problem cannot be reduced to it (say, 3-SAT, with >50 clauses).
In fact, the second problem is in P, because O(n^50)
belongs to P. But that isn't the reason why it is not NP-hard (specifically, NP doesn't mean non-polynomial).
精彩评论