co-NP 복잡도 클래스 (co-NP complexity class)
쉽게 풀면
NP가 '예'라는 답을 다항 시간에 검증할 수 있는 문제들의 모임이라면, co-NP는 그 반대로 '아니오'라는 답을 다항 시간에 검증할 수 있는 문제들의 모임이다. 예를 들어 어떤 논리식이 '충족 불가능하다'는 것, 즉 어떤 값을 넣어도 참이 될 수 없다는 것을 증명하는 문제는 co-NP에 속한다. NP와 co-NP가 서로 같은 클래스인지(즉 NP=co-NP인지)는 P=NP 문제와 마찬가지로 아직 증명되지 않은 미해결 문제이며, 많은 학자들은 이 둘이 다를 것이라 추측한다.
왜 중요한가
co-NP는 P=NP 문제와 밀접하게 얽혀 있는 개념으로, 어떤 문제의 복잡도 하한이나 계산 난이도를 논할 때 자주 등장한다. 특히 어떤 문제가 NP∩co-NP에 속한다는 사실은 그 문제가 NP-완전일 가능성이 낮다는 정황 증거로 쓰이며, 이는 알고리즘 설계자가 다항 시간 알고리즘을 찾는 노력을 계속할지 판단하는 데 중요한 근거가 된다. 또한 co-NP는 복잡도 클래스들의 계층 구조(다항 계층, PH)를 정의하는 출발점이기도 해서, 계산 복잡도 이론 논문에서 상위 클래스를 설명할 때 기준점으로 자주 인용된다.
논문에서는 이렇게 쓰입니다
어떤 문제가 NP-완전이 아닐 가능성이 있음을 설명하는 이론적 근거로 NP와 co-NP 교집합 개념이 인용된다.
암호학 관련 논문에서 정수 인수분해의 계산 난이도를 논할 때, NP∩co-NP 소속 여부를 근거로 그 난이도가 NP-완전 문제보다 낮을 가능성을 시사하는 데 활용된다.
인공지능·제약 만족 분야 논문에서 특정 문제가 co-NP에 속함을 형식적으로 증명하는 절차를 설명하는 데 쓰이는 표현이다.
조금 더 깊게 보면
NP∩co-NP는 NP와 co-NP 양쪽에 모두 속하는 문제들의 교집합으로, '예'와 '아니오' 답 모두를 다항 시간에 검증할 수 있는 증거가 존재하는 문제들을 가리킨다. 이 개념은 정수 인수분해처럼 P에 속하는지 아직 밝혀지지 않았지만 NP-완전은 아닐 것으로 추측되는 문제들을 설명할 때 자주 등장한다. 한편 co-NP는 다항 계층(polynomial hierarchy)의 첫 단계를 구성하는 클래스 중 하나로, 이 계층을 통해 NP나 co-NP보다 더 강력한 계산 자원을 요구하는 문제들을 세분화하여 분류할 수 있다. 논문을 읽을 때는 저자가 co-NP 소속성을 증명함으로써 무엇을 주장하려는지(하한 증명인지, NP-완전성 배제인지)를 함께 살펴보는 것이 이해에 도움이 된다.
주의할 점
NP=co-NP인지는 아직 미해결 문제이며, 만약 어떤 NP-완전 문제가 co-NP에도 속한다는 것이 증명된다면 이는 NP=co-NP를 함축하게 되므로 그런 증명은 발견되지 않고 있다.