co-NP-완전

계산 복잡도 이론에서 복잡도 종류 co-NP-완전(co-NP-complete)이란 co-NP에서 가장 어려운 문제의 집합을 말한다. 여기서 어렵다는 것은, P에 들어갈 가능성이 낮다는 뜻이다. 한 co-NP-완전 문제를 빠르게 푸는 방법을 찾아낸다면, 그 방법을 써서 모든 co-NP-완전 문제를 빠르게 풀 수 있게 된다.

더 공식적인 정의: 결정 문제 C가 co-NP이고 모든 co-NP 문제가 이 문제로 다항 시간 환산 가능하면, C는 co-NP-완전이다. 이것은 모든 co-NP 문제 L에 대해서, L에 대한 어떤 예제든지 C에 대한 예제로 바꿀 수 있는 다항 시간 알고리즘이 있다는 뜻이다. 그러므로 C를 풀 수 있는 다항 시간 알고리즘이 있다면, 모든 co-NP 문제를 다항 시간에 풀 수 있게 된다.

대표적인 co-NP-완전 문제로 항진명제가 있다. 주어진 논리식이 항상 참인 명제인지 판정하는 문제이다. 다시 말해서, 식에서 변수마다 참/거짓 값을 넣을 때, 어떻게 넣어도 논리식 전체는 참이 되는 것이다. 이 문제는 충족 가능성 문제와 깊게 관련되어 있다. 불 만족 문제는 모든 변수값 할당에 대해 논리식이 참이 되는지를 판정하는 항진명제 문제와 달리, 논리식이 참이 되는 변수값 할당이 적어도 하나 있는지를 묻는 문제이다.

co-NP-완전 문제 각각은 NP-완전 문제의 보완 문제가 된다. co-NP-완전과 NP-완전은 같은 집합이거나, 전혀 겹치지 않는 집합이다. 뒤쪽이라는 설이 유력한데 아직 확실하지는 않다. 더 자세한 논의는 co-NP와 NP-완전을 참고하라.