NP-완전

1 개요

NP-completeness

NP-완전

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

2 정의

NP-완전은 다음의 조건을 만족하는 결정 문제 C의 집합이다:

1. C가 NP에 속한다.
2. NP에 속하는 모든 문제를 다항 시간 안에 C로 변환할 수 있다. 즉, 다항 시간 환산을 할 수 있다.

여기에서 두 번째 조건은 NP-난해의 정의이고, 즉 NP-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다.

3 NP-완전 문제의 예

• 해밀턴 경로 문제
• 충족 가능성 문제(SAT)
• 외판원 문제
• 그래프 색칠 문제
• 시간표 짜기

4 같이 보기

• P-NP 문제

5 참고

• 위키백과 "NP-완전"
• 위키낱말사전 "NP-완전"
• 다음사전 "NP-완전"
• 다음백과 "NP-완전"
• 네이버사전 "NP-완전"
• 네이버백과 "NP-완전"