np 하드로 환원

Question

Wiki에 따르면 폴리 시간에서 np 복잡성 문제를 A로 변환하면 A는 np 하드입니다. 는

http://en.wikipedia.org/wiki/NP-hard를 참조하지만, 아래의 PDF는 다항식 시간에 문제 A를에 NP 어려운 문제를 변환 할 때, A는 NP 것을 말한다 - http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

하드 하나가 내가 생각해야합니까?

Answer 1

둘 다. NP-complete는 NP-hard의 하위 집합입니다. NP 완전 문제는 정의상 NP 어렵다. 하나의 진술 만 기억한다면, 후자를 기억하십시오 : NP-hard의 문제가 다항식 시간의 문제 A로 축소 될 수 있다면 A도 NP 하드입니다.

NP의 경도는 NP의 모든 문제가 다항식 시간에서 문제로 감소 될 수있는 경우를 나타냅니다. NP-completeness는 문제가 NP와 NP-hard 모두에있는 경우를 나타냅니다.