NP 경도 경계

Question

두 가지 문제점이 있습니다.

1. 그래프의 크기 K의 도당 있는가? NP 하드

2. 그래프에 크기가 50 인 파벌이 있습니까? - 다항식 시간 O (N^50)

왜 번째 문제가되지 NP 하드 첫번째는대로에 를 발견 할 수 있는가?

EDIT! = P 가정 n^50 다항식 반면 NP

Answer 1

첫 번째 문제는 임의의 NP 완전 문제 (예 : 3-SAT)를 다항식 시간으로 줄일 수 있기 때문에 NP 하드입니다. (NP 경도의 정의에 의한)

두 번째 문제는 임의의 NP 완성 문제 (예 : 3 절 이상,> 50 절)로 축소 될 수 없기 때문에 NP 하드가 아닙니다. O(n^50)는 P.에 속하지만 (즉, NP 비 다항식을 의미하지 않음) NP-어렵지 않다 이유 이유 없기 때문에 실제로

는 두 번째 문제는, P이다.

Answer 2

n^k는 지수이다.