NP 복잡도

NP

• 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합
• NP는 비결 정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자

NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립

또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로,

• P 집합: NP 집합의 부분집합이다.
  이때 P가 NP의 진부분집합(Proper Subset)인 지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았다. 이 문제는 P-NP 문제로 불리우며 컴퓨터과학 분야의 대표적인 미해결 문제 중 하나다.

클레이 수학 연구소에서 발표한 7개의 밀레니엄 문제(미해결 문제) 중 하나이며 해결하는 사람에게 100만 달러의 상금이 걸려 있기도 하다.

왜 해밀턴 경로 문제와 외판원 문제의 NP 문제가 다른이유

먼저, 혼동될 수 있으니 3가지 문제의 구분부터 다시 한번 살펴보자.
more learn

• 해밀턴 경로: 한 번만 방문하는 경로
• 해밀턴 순환: 한 번만 방문하여 출발지로 돌아오는 경로
• 외판원 문제: 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로

따라서 이 세 문제는 ‘해밀턴 경로 > 해밀턴 순환 > 외판원 문제’의 포함 관계를 이룸

이제 해밀턴 경로와 외판원 문제, 2가지 문제를 다시 한번 정의해보자.

1. 해밀턴 경로가 존재하는가?
2. 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾아라(최단 거리 해밀턴 순환을 찾아라).

NP-완전 문제의 조건.
•NP 문제다.
•NP-난해 문제다.

앞서 P-NP 문제는 컴퓨터과학 분야의 대표적인 미해결 문제 중 하나라고 했는데,
그림 12-5는 이에 따라 P≠NP인 경우와 P=NP인 경우의 NP-완전, NP-난해 문제 집합에 대한 관계다.
참고로 P≠NP일 것이라고 많은 사람들이 추측만 할 뿐이며 아직 증명되지 않았다.
어느 경우이든 NP이면서 NP-난해 문제인 경우를 NP-완전 문제라 한다.
(1번 문제)

• 결정 문제(Decision Problem)로 다항 시간에 정답을 검증 가능
• 즉 NP 문제 이며, NP-난해 문제다.
• NP-완전 문제다

(2번 문제)

• 결정 문제가 아님
• NP 문제가 아닐 수 있음.
• 증명할 수 있는 NP-난해 문제이 지만 NP 문제가 아닐 수 있음
• NP-완전 문제가 아님
• 2번은 NP-난해 문제