Co-NP
1. 개요
co-NP는 어떤 결정 문제의 보문제가 NP에 속하는 복잡도 종류이다. P는 NP와 co-NP의 부분집합이며, P ⊆ NP와 P ⊆ co-NP가 알려져 있다. 만약 P=NP라면 NP=co-NP가 되며, NP≠co-NP를 증명하는 것은 P≠NP를 증명하는 것과 연관되어 있다. co-NP-완전 문제는 co-NP에 속하며, co-NP에 속하는 모든 문제로부터 다항 시간 환산이 가능한 문제이다. 명제 논리에서 공식이 항진명제인지 결정하는 것은 co-NP-완전 문제이다. 정수 인수분해 문제는 NP와 co-NP에 속하지만, 현재 P에 속하는지는 밝혀지지 않았다.
2. 정의
co-NP는 "어떤 결정 문제 S의 보문제가 NP에 속하면, S는 co-NP에 속한다" 와 같이 정의되는 문제의 클래스이다. 여기서 보문제란 결정 문제의 '예'와 '아니오'가 뒤바뀐 문제이다. 예를 들어 "어떤 수 N은 소수인가?"라는 문제의 보문제는 "어떤 수 N은 합성수인가?"가 된다. P ⊆ NP와 마찬가지로 P ⊆ co-NP임이 알려져 있다.
3. co-NP-완전
어떤 문제 L이 co-NP-완전(co-NP-complete)이라는 것은, L이 co-NP에 속하고, co-NP에 속하는 모든 다른 문제를 다항 시간 내에 L로 환산(reduction)할 수 있다는 것을 의미한다. 대표적인 co-NP-완전 문제로는 명제 논리에서 주어진 논리식이 항진명제인지 판별하는 문제가 있다. 즉, 모든 가능한 변수 할당에 대해 해당 논리식이 항상 참인지 판별하는 것이다.
3.1. 만족 불가능성 (Unsatisfiability)
NP-완전 문제의 예시로 부울 만족 가능성 문제가 있다. 부울 식이 주어졌을 때, 이 식이 '만족 가능한가'(식을 참으로 만드는 변수 할당이 존재하는가) 하는 문제이다. 이 문제의 반대 문제는 "주어진 부울 식이 '만족 불가능한가'(식의 모든 가능한 입력이 거짓을 출력하는가)?"를 묻는다. 이는 만족 가능성 문제의 보완 문제이므로, 원래 NP 문제의 '예' 인스턴스에 대한 증명, 즉 식을 참으로 만드는 부울 변수 할당 집합은 이 문제에서는 '아니요' 인스턴스에 대한 증명이 된다.
4. 다른 복잡도 종류와의 관계
P는 다항 시간 내에 풀리는 문제들의 종류로, NP와 co-NP 모두의 부분 집합이다. P는 보완 연산에 닫혀 있고, NP와 co-NP는 서로 보완적이므로, P가 NP와 같으면 co-NP와 같아야 하며, 그 반대도 성립한다.
NP와 co-NP는 서로 같지 않은 것으로 여겨진다. 만약 NP = co-NP라면, 어떤 NP-완전 문제도 co-NP에 속할 수 없고, 어떤 co-NP-완전 문제도 NP에 속할 수 없다.
co-NP는 PH의 부분 집합이며, PH는 다시 PSPACE의 부분 집합이다.
만약 P=NP라고 가정하면 NP=co-NP가 된다. 여기서 대우를 취하면 NP≠co-NP이면 P≠NP임을 증명할 수 있다. 이 때문에 NP≠co-NP를 증명하는 것은 P≠NP 가설에 대한 유력한 해결 수단 중 하나로 초기에 여겨졌으나, 현재까지 미해결 상태이며 P≠NP를 증명하는 것과 마찬가지이거나 그 이상으로 어려울 것으로 추정된다.
5. 정수 인수분해 문제
정수 인수분해는 주어진 양의 정수 m과 n에 대해, m이 1보다 크고 n보다 작은 약수를 갖는지 판별하는 문제이다. 이 문제는 NP와 co-NP 모두에 속한다. m이 그러한 인수를 가지고 있다면, 그 인수 자체가 증명이 되므로 NP에 속한다는 것은 명백하다. co-NP에 속하는 것 또한 간단한데, m의 소인수를 나열하면 되며, 이 소인수들은 모두 n보다 크거나 같고, 검증자는 곱셈과 AKS 소수 판별법을 통해 유효한지 확인할 수 있다. 현재 인수분해를 위한 다항 시간 알고리즘, 즉 정수 인수분해가 P에 속하는지 여부는 알려져 있지 않다.