NP 완전 (NP-complete, NP-C, NPC)

jino630·2021년 6월 16일
0

P-NP

목록 보기
3/5

출처 - 위키

NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다.


NP와 NP-완전 간의 관계

NP -> (다항 시간) -> NP-완전

NP-완전을 다항시간 안에 해결할 수 있다면 (P에 속한다면), NP문제와 NP-완전 문제 모두 P문제가 된다.

아직 NP-완전 문제를 다항시간안에 해결하지 못했다.


P!=NP 일경우


P=NP 일 경우


0개의 댓글