NP-완전

위키백과 ― 우리 모두의 백과사전.

계산 복잡도 이론에서 NP-완전(영어: NP-complete)은 NP에 속한 가장 어려운 문제의 집합이다. 거의 모든 사람들이 NP-완전 문제들은 P에 속하지 않을 것이라고 예상하고 있다. 만약 누군가가 어떤 NP-완전 문제를 빠르게 풀 수 있다면, 이것을 이용하여 모든 NP 문제를 빨리 풀 수 있기 때문이다.

[편집] 정의

결정문제 C는 다음 두 가지 조건을 만족하면 NP-완전이다.

1. C가 NP에 속한다.
2. C가 NP-난해하다. 즉, NP에 속한 모든 문제들을 이 문제로 환산할 수 있다.

위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다.

NP-완전이라는 개념은 1971년에 스티븐 쿡이 정의했다. (물론 "NP-완전"이라는 용어는 그의 논문에서 나온 것이 아니다.) 쿡은 불 만족 문제가 위 정의의 두 가지 조건을 모두 만족한다는 것을 증명했다. 1972년에 리처드 카프는 21가지의 다른 문제들도 마찬가지로 위 두가지 조건을 만족한다는 것을 증명했다. 쿡이 최초의 NP-완전 문제를 발견한 이후로, 많은 사람들이 NP-완전 문제라고 이미 알려진 문제로부터 환산하는 방법으로 수 많은 문제들 역시 NP-완전임을 증명했으며 현재 NP-완전 문제의 개수는 수천가지에 이른다. NP-완전 문제의 목록은 게리와 존슨이 1979년에 쓴 Computers and Intractability: A Guide to NP-Completeness에 정리되어 있다.

[편집] NP-완전 문제의 예

• 외판원 문제
• 그래프 색칠 문제

[편집] 참조

• P-NP 문제

주요 복잡도 종류 (더 보기)
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.