무언가를 증명하기 위해 NP 하드, 왜 NP 완성에서 그것을 줄일 필요가 있습니까? 위키

Question

:

문제 H는 H (즉, L에 ≤ 된 TH)까지 다항식 시간 튜링 환원성 인 NP 완전 문제 L가있는 경우에만, NP-어렵다.

왜 문제가 (NP라고도 부름) NP 완성이 필요합니까? 왜 그것은 NP 하드가 아닌가? 그것은 당신이 W에 대해 신경 쓰지 않는 것처럼 보입니다.

생각하십니까?

Answer 1

수 있습니다. 사실 두 번째 단락은 첫 번째 단락을 의미합니다.

NP 어려운 문제 H가 다항식으로 문제 X에 축소 될 수 있다고 가정합니다. 정의에 따르면, NP에 완전한 문제 C가 있습니다. 두 축소가 다항식이므로 다항식 시간에서 C에서 X까지 줄일 수 있습니다 . 따라서, NP 완전 문제 C는 다항식 시간에 X로 환원 가능하다. 따라서 문제 X는 NP 어렵다.

Answer 2

문제의 NP 경도를 증명하는 데 충분할 정도로 NP 하드 문제를 다항식으로 줄일 수 있으면 문제를 해결할 수 있습니다. 그러나 특정 NP 하드 문제는 NP 하드 일지라도 다항식으로 문제를 해결할 수 없습니다.

또한 NP 경도를 줄임으로써 증명할 필요도 없으며 직접 증명할 수도 있습니다.