NP硬度境界

Question

私には2つの問題があります。

1. グラフのサイズkのクリークはありますか？ NPハード

2. グラフにサイズ50のクリークはありますか？ - 多項式時間はO（n^50）

がなぜ第二の問題はないNPハード最初のものがあるされているように を見つけることができますか？

EDIT：！Pを仮定= n^50が多項式であるのに対し、NP

Answer 1

第1の問題は、任意のNP完全問題（例えば、3-SAT）を多項式時間で減らすことができるため、NP困難である。 （NP硬度の定義による）

第2の問題は、任意のNP完全問題をそれに還元することができないので（例えば、3つのSAT、> 50節）、NPハードではない。 O(n^50)はPに属する。しかし、それは（具体的には、NP は非多項式を意味するものではありません）NP-難しいことではありませんなぜそれが理由ではないので、実際には

は、第二の問題は、Pです。

Answer 2

n^kが指数関数的です。