Co-NP

3. co-NP-완전

어떤 문제 ''L''이 co-NP-완전(co-NP-complete)이라는 것은, L이 co-NP에 속하고, co-NP에 속하는 모든 다른 문제를 다항 시간 내에 L로 환산(reduction)할 수 있다는 것을 의미한다. 대표적인 co-NP-완전 문제로는 명제 논리에서 주어진 논리식이 항진명제인지 판별하는 문제가 있다. 즉, 모든 가능한 변수 할당에 대해 해당 논리식이 항상 참인지 판별하는 것이다.^[1]

3. 1. 만족 불가능성 (Unsatisfiability)

4. 다른 복잡도 종류와의 관계

P는 다항 시간 내에 풀리는 문제들의 종류로, NP와 co-NP 모두의 부분 집합이다. P는 보완 연산에 닫혀 있고, NP와 co-NP는 서로 보완적이므로, P가 NP와 같으면 co-NP와 같아야 하며, 그 반대도 성립한다.^[2]

NP와 co-NP는 서로 같지 않은 것으로 여겨진다.^[3] 만약 NP = co-NP라면, 어떤 NP-완전 문제도 co-NP에 속할 수 없고, 어떤 co-NP-완전 문제도 NP에 속할 수 없다.^[4]

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 소수 판별법을 통해 유효한지 확인할 수 있다.^[5] 현재 인수분해를 위한 다항 시간 알고리즘, 즉 정수 인수분해가 P에 속하는지 여부는 알려져 있지 않다.

6. P ≠ NP 추측과의 관계

만약 P=NP라고 가정하면, NP=co-NP가 된다. 이 명제의 대우는 "NP≠co-NP이면 P≠NP"이다.^[3] 따라서 NP≠co-NP를 증명하는 것은 P≠NP 추측을 증명하는 하나의 방법이 될 수 있다. 그러나 NP≠co-NP를 증명하는 것 역시 P≠NP를 증명하는 것만큼이나 어려운 문제로 여겨지고 있다.

참조

_[1] 서적 Complexity Theory: A Modern Approach http://www.cs.prince[...] Cambridge University Press 2009
_[2] 논문 P versus NP https://dialnet.unir[...]
_[3] 서적 Introduction to Automata Theory, Languages, and Computation Addison-Wesley
_[4] 서적 P, NP, and NP-completeness: The Basics of Computational Complexity Cambridge University Press
_[5] 서적 Open Problems in Mathematics Springer International Publishing
_[6] 논문 소수 문제가 P임을 밝힌 논문 http://www.math.prin[...]