co-NP

co-NP는 계산 복잡도 이론에서 정의되는 중요한 복잡도 종류 중 하나이다. 이 클래스는 주어진 문제의 '아니오' 답변, 즉 반례에 대해 효율적으로 검증할 수 있는 증명이 존재하는 문제들의 집합으로 특징지어진다. 구체적으로, 어떤 문제 X가 co-NP에 속한다는 것은 그 문제의 보완 문제 X̅가 NP에 속한다는 것과 동치이다.

co-NP에 속하는 대표적인 예시로는 부분집합 합 문제의 보완 문제가 있다. 또한 정수의 소인수 분해 문제도 co-NP에 속하는 것으로 알려져 있다. 한편, 다항 시간에 해결 가능한 문제들의 집합인 P는 NP와 co-NP 모두의 부분집합이다.

현재 학계의 널리 받아들여지는 추측에 따르면, NP와 co-NP는 서로 같은 집합이 아닐 것으로 보인다. 만약 두 집합이 같다면, 모든 NP-완전 문제가 co-NP에 들어갈 수 있고, 모든 co-NP-완전 문제가 NP에 들어갈 수 있게 되는 결과를 초래하기 때문이다. 따라서 어떤 문제가 NP와 co-NP에 동시에 속한다는 것이 증명된다면, 그 문제가 NP-완전일 가능성은 매우 낮아진다.

co-NP는 계산 복잡도 이론에서 정의되는 중요한 복잡도 종류 중 하나이다. 어떤 결정 문제 X가 co-NP에 속한다는 것은, 그 문제의 보완 문제(complement)인 X̅가 NP에 속한다는 것과 동치이다. 즉, co-NP는 NP에 속하는 문제들의 '보완 문제들'로 이루어진 집합으로 볼 수 있다.

이 정의를 다른 방식으로 설명하면, co-NP는 문제에 대해 '아니오' 답변이 맞다는 것을 효율적으로 검증할 수 있는 증명이 존재하는 문제들의 모임이다. 예를 들어, 어떤 명제가 거짓임을 보여주는 구체적인 반례를 제시하면, 그 반례를 다항 시간 내에 확인하여 '아니오' 답변이 옳음을 검증할 수 있는 문제들이 여기에 해당한다.

부분집합 합 문제의 보완 문제는 co-NP에 속하는 대표적인 예시이다. 또한 정수의 소인수 분해 문제도 NP와 co-NP에 동시에 속하는 것으로 알려져 있다. 다항 시간 내에 해결 가능한 문제들의 집합인 P는 NP의 부분집합이면서 동시에 co-NP의 부분집합임이 알려져 있다.

현재 학계의 널리 받아들여지는 추측에 따르면, NP와 co-NP는 서로 같은 집합이 아닐 것으로 여겨진다. 만약 두 집합이 같다면, 모든 NP-완전 문제가 co-NP에 들어갈 수 있고, 모든 co-NP-완전 문제가 NP에 들어갈 수 있게 되어, 이는 현재까지의 연구와 모순되는 여러 결과를 초래하기 때문이다.

co-NP와 NP의 관계는 계산 복잡도 이론의 핵심적인 질문 중 하나이다. 두 복잡도 종류는 서로 보완적인 관계에 있다. 어떤 문제 X가 co-NP에 속한다는 것은, 그 문제의 보완 문제 X̅가 NP에 속한다는 것과 동치이다. 이는 NP가 '예' 답변에 대한 증명을 효율적으로 검증할 수 있는 문제들의 집합인 반면, co-NP는 '아니오' 답변에 대한 증명(즉, 반례)을 효율적으로 검증할 수 있는 문제들의 집합임을 의미한다.

대부분의 학자들은 NP와 co-NP가 서로 다른 집합이라고 추측한다. 만약 NP와 co-NP가 같다면, 이는 중대한 결과를 초래한다. NP-완전 문제가 co-NP에 들어갈 수 있고, 반대로 co-NP-완전 문제가 NP에 들어갈 수 있게 되기 때문이다. 이는 모든 NP 문제의 보완 문제가 역시 NP에 속함을 의미하게 되어, 현재의 복잡도 이론 체계에 큰 변화를 가져올 것이다.

이러한 추측을 뒷받침하는 한 가지 논증은 다음과 같다. 만약 어떤 NP-완전 문제가 co-NP에도 속한다고 가정하면, 모든 NP 문제는 그 문제로 다항 시간 내에 환산될 수 있으므로, 모든 NP 문제의 보완 문제 역시 다항 시간 비결정적 알고리즘으로 판정 가능해진다. 이는 NP가 co-NP의 부분집합이 됨을 뜻한다. 대칭적인 논리로 co-NP도 NP의 부분집합이 되어, 결국 두 집합이 동일하다는 결론에 도달한다. 그러나 현재까지 그러한 NP-완전 문제는 발견되지 않았으며, 발견된다면 P-NP 문제에 대한 해답과도 깊이 연관될 것이다.

따라서, 어떤 문제가 NP와 co-NP의 교집합에 속한다는 것이 확인되면, 그 문제가 NP-완전일 가능성은 매우 낮아진다. 대표적인 예로 소인수분해 문제나 소수 판별 문제가 있으며, 이들은 둘 다 NP와 co-NP에 속하는 것으로 알려져 있다. 특히 소수 판별 문제는 이후 다항 시간 내에 풀 수 있음이 증명되어 P에 속함이 확인되었다.

co-NP-완전은 계산 복잡도 이론에서 중요한 복잡도 종류 중 하나이다. 어떤 문제가 co-NP-완전이 되려면 두 가지 조건을 만족해야 한다. 첫째, 그 문제는 co-NP에 속해야 한다. 둘째, co-NP에 속하는 모든 다른 문제가 그 문제로 다항 시간 환산될 수 있어야 한다. 이는 NP-완전 문제의 정의와 정확히 대칭적인 개념으로, co-NP-완전 문제는 co-NP 내에서 가장 어려운 문제들의 집합을 의미한다.

co-NP-완전 문제의 대표적인 예로는 보편 타당성 문제가 있다. 이 문제는 주어진 명제 논리식이 모든 가능한 변수 값에 대해 항상 참인지 묻는 문제이다. "아니오"라는 답변에 대한 증명은 해당 논리식을 거짓으로 만드는 변수 값의 할당, 즉 반례를 제시하는 것으로, 이 증명은 다항 시간 내에 검증 가능하다. 따라서 이 문제는 co-NP에 속하며, co-NP의 다른 모든 문제가 이 문제로 환산될 수 있음이 알려져 있어 co-NP-완전으로 분류된다.

만약 하나의 NP-완전 문제가 동시에 co-NP에 속한다면, 이는 모든 NP 문제가 co-NP에 속함을 의미하게 된다. 이 경우 NP와 co-NP가 동일한 집합이 될 수 있다. 그러나 대부분의 학자들은 NP와 co-NP가 다를 것으로 추측하고 있으며, 따라서 NP-완전 문제가 co-NP에 속하거나, co-NP-완전 문제가 NP에 속하는 상황은 발생하지 않을 것으로 예상한다. 이는 P-NP 문제와 더불어 계산 복잡도 이론의 주요 미해결 문제 중 하나이다.

co-NP에 속하는 대표적인 문제로는 부분집합 합 문제의 보완 문제가 있다. 부분집합 합 문제는 주어진 정수 집합에서 합이 0이 되는 공집합이 아닌 부분집합이 존재하는지 묻는 NP-완전 문제이다. 이 문제의 보완 문제, 즉 "주어진 집합의 모든 공집합이 아닌 부분집합의 합이 0이 아니다"라는 명제는 co-NP에 속한다. 이 보기(반례)에 대한 증명은 합이 0이 되는 부분집합 하나를 제시하는 것으로, 이 증명은 다항 시간 내에 쉽게 검증 가능하다.

또 다른 중요한 예시는 정수의 소인수 분해와 관련된 결정 문제이다. "양의 정수 m이 1보다 크고 n보다 작은 약수를 갖는가?"라는 질문은 co-NP에 속한다. '아니오'라는 대답, 즉 m이 그런 약수를 전혀 갖지 않는다는 것을 증명하는 것은 어려울 수 있지만, '예'라는 대답에 대한 증명은 그런 약수 하나를 제시하면 되므로 검증이 쉽다. 이 문제는 NP에도 속하는 것으로 알려져 있다.

이러한 예시들은 co-NP의 본질을 보여준다. 즉, 어떤 명제가 거짓임을 보이는 '반례'가 존재할 때, 그 반례 자체를 효율적으로 검증할 수 있는 증거로 삼을 수 있는 문제들의 집합이 co-NP이다. 이는 '예'라는 답에 대해 검증 가능한 증거가 있는 문제들의 집합인 NP와 대칭을 이룬다.

P, NP, co-NP의 관계는 계산 복잡도 이론의 핵심적인 질문 중 하나를 이룬다. 이 세 복잡도 종류는 포함 관계를 통해 서로 얽혀 있으며, 이 관계에 대한 해답은 P-NP 문제와도 깊이 연관되어 있다.

현재 알려진 사실에 따르면, P는 NP와 co-NP 모두의 부분집합이다. 즉, 다항 시간 내에 해를 구할 수 있는 모든 문제는 그 해답을 다항 시간 내에 검증할 수도 있고(NP), 그 문제의 '아니오' 답변에 대한 증거도 다항 시간 내에 검증할 수 있다(co-NP). 그러나 P가 NP와 co-NP의 진부분집합인지는 아직 증명되지 않았다. 만약 P = NP라면, 자동으로 P = co-NP = NP가 성립하게 된다.

NP와 co-NP의 관계는 더욱 미스터리하다. 일반적으로 NP와 co-NP는 서로 다른 집합일 것으로 추측되지만, NP = co-NP인지 여부는 여전히 열려 있는 문제이다. 만약 NP와 co-NP가 같다면, 모든 NP-완전 문제는 co-NP에도 속하게 되고, 모든 co-NP-완전 문제는 NP에도 속하게 된다. 이는 현재의 지식과 상충되는 결과를 초래할 수 있어, 대부분의 학자들은 NP ≠ co-NP일 것이라고 믿는다.

이러한 관계 속에서, 어떤 문제가 NP와 co-NP에 동시에 속한다는 것이 확인되면, 그 문제가 NP-완전일 가능성은 매우 낮아진다. 대표적인 예로 소인수분해 문제나 소수 판별 문제가 있으며, 이들은 각각 NP와 co-NP의 교집합에 속하는 것으로 알려져 있다. 특히 소수 판별 문제는 이후 P에도 속함이 증명되었다. 따라서 P, NP, co-NP의 관계를 규명하는 것은 복잡도 이론의 근본적인 난제를 해결하는 열쇠가 된다.

co-NP는 NP와 밀접한 쌍대 관계에 있는 복잡도 종류이다. 이 개념은 계산 복잡도 이론에서 결정 문제의 "예" 답변과 "아니오" 답변의 비대칭성을 연구하는 데 중요한 틀을 제공한다. NP가 "예" 답변에 대한 검증이 쉬운 문제들의 집합이라면, co-NP는 "아니오" 답변에 대한 검증이 쉬운 문제들의 집합으로 이해할 수 있다.

co-NP-완전 문제는 co-NP 내에서 가장 어려운 문제들을 의미하며, 만약 이들 중 하나라도 다항 시간에 풀린다면 NP와 co-NP가 동일한 집합이 된다는 것이 증명된다. 이는 P-NP 문제와 더불어 계산 이론의 주요 미해결 난제 중 하나로 남아 있다. 현재 학계의 지배적인 견해는 NP와 co-NP가 서로 다를 것이라고 추측하고 있으며, 이는 소인수분해와 같은 문제가 NP-완전이 아닐 것이라는 강력한 근거가 된다.

co-NP의 연구는 암호학과 알고리즘 설계에 실질적인 영향을 미친다. 예를 들어, 어떤 문제가 NP와 co-NP에 동시에 속한다는 것이 확인되면, 그 문제는 NP-완전일 가능성이 극히 낮아지며, 이는 더 효율적인 알고리즘을 찾을 수 있는 가능성을 시사한다. 이러한 성질은 정수론 기반 암호 시스템의 안전성을 분석하는 데에도 활용된다.

• ko.wikipedia.org