开发者

NP Hardness boundary

I have two problems.

开发者_Python百科
  1. Is there a clique of size k in a graph? NP Hard

  2. 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).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜