NP-완전
위키백과 ― 우리 모두의 백과사전.
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-완전은 다음의 조건을 만족하는 결정 문제 C의 집합이다:
여기에서 두 번째 조건은 NP-난해의 정의이고, 즉 NP-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다.
[편집] 역사
NP-완전이라는 개념은 1971년에 스티븐 쿡이 정의했다. 하지만 그의 논문에서 ‘NP-완전’이라는 용어가 나온 것은 아니다. 쿡은 불 만족 문제(SAT)가 위 정의의 두 가지 조건을 모두 만족한다는 것을 증명했다. 1972년에 리처드 카프는 21가지의 다른 문제들도 마찬가지로 위 두가지 조건을 만족한다는 것을 증명했다. 쿡이 최초의 NP-완전 문제를 발견한 이후로, 많은 사람들이 NP-완전 문제라고 이미 알려진 문제로부터 환산하는 방법으로 수많은 문제들 역시 NP-완전임을 증명했으며 현재 NP-완전 문제의 개수는 해마다 수천 개씩 늘어나고 있다. NP-완전 문제의 목록은 게리와 존슨이 1979년에 쓴 Computers and Intractability: A Guide to NP-Completeness에 정리되어 있다.
[편집] 근사 알고리즘
현재 NP-완전 문제를 다항 시간 안에 푸는 알고리즘은 발견되지 않았고, 또한 그러한 알고리즘이 존재할 것인지도 알려지지 않았다. 대신, 특정한 NP-완전 문제에 대한 근사 알고리즘이 알려져 있다.
[편집] 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 |
