공동 NP

co-NP
컴퓨터 과학의 미해결 문제:

(컴퓨터 과학에서 더 풀리지 않은 문제)

계산 복잡성 이론에서, co-NP는 복잡성 등급이다. 의사결정 문제 X는 그것의 보완 X가 복잡도 등급 NP에 있는 경우에만 공동 NP의 구성원이 된다. 클래스는 다음과 같이 정의될 수 있다: 결정 문제는 오직 no-instance가 다항 길이의 "인증서"를 가지고 있고, 보고된 인증서를 검증하는 데 사용할 수 있는 다항 시간 알고리즘이 있는 경우 정확하게 공동 NP에 있다.

즉, co-NP는 p(n)와 다항 시간 경계 튜링 머신 M이 존재하는 의사결정 문제의 집합으로, 모든 인스턴스 x에 대해 x는 인스턴스 없음인 경우에만: p(n)으로 경계된 길이의 일부 인증서 c에 대해 튜링 머신 M이 쌍(x, c)[1]을 수락한다.

보완적 문제

주요 기사: 보완(복잡성)

NP 문제는 주어진 인스턴스(instance)가 예스 인스턴스(yes-instance)인지 여부를 묻는 반면, 그것의 보완물은 인스턴스(no-instance)인지 여부를 묻는 것으로, 이는 보어가 공동 NP에 있음을 의미한다. 원래 NP 문제에 대한 예스 인스턴스는 그 보완점에 대한 무 인스턴스가 되고, 그 반대도 마찬가지다.

불만족

추가 정보: 불만족핵

NP 완료 문제의 예로는 부울 만족도 문제가 있다. 부울 공식이 주어지면 만족스러운가(공식이 참으로 출력하는 입력 가능한가)? 보완적 문제는 "부울 공식을 고려할 때, 만족스럽지 못한가(공식 출력에 가능한 모든 입력을 거짓으로 하는가)"라고 묻는다. 이것이 만족도 문제의 보완이므로, 비인스턴스에 대한 인증서는 공식을 참으로 만드는 부울 변수 할당 집합인 원래 NP 문제의 예-인스턴스와 동일하다. 반면에 보완적 문제에 대한 예-인스턴스 인증서는 원래 NP 만족도 문제의 무인스턴스만큼 복잡할 것이다.[clarification needed]

이중 문제

주요 기사: 이중성(최적화)

Co-NP-완전성

주요 기사: co-NP-완전

L 문제는 L이 Co-NP에 있는 경우와 Co-NP에 있는 경우에만 Co-NP-완료되며, Co-NP에 문제가 있는 경우, 그 문제에서 L로 다항 시간 단축이 존재한다.

자동학 감소

명제논리의 공식이 tautology인지 아닌지를 결정하는 것은 공동 NP-완전하다. 즉, 공식이 변수에 대한 가능한 모든 할당 하에서 true로 평가되는 경우.[1]

타계급과의 관계

추가 정보: 복잡도 등급

다항식 시간 해결 가능한 문제의 등급인 P는 NP와 공동 NP의 하위 집합이다. P는 두 경우 모두 엄격한 하위 집합으로 간주된다(그리고 한 경우에는 엄격할 수 없고 다른 경우에는 엄격하지 않다).[citation needed]

NP와 co-NP도 불평등하다고 생각된다.[2] 만일 그렇다면, NP-완전한 문제는 co-NP에 있을 수 없고, co-NP-완전한 문제는 NP에 있을 수 없다.[3] 이를 다음과 같이 나타낼 수 있다. 모순을 위해 공동 NP에 있는 NP 완전 문제 X가 존재한다고 가정하자. NP의 모든 문제는 X로 줄일 수 있기 때문에 NP의 모든 문제에 대해 다항 시간(즉, NP ⊆ co-NP)에서 보완을 결정하는 비결정론적 튜링 기계를 구축할 수 있다. 이로부터, NP의 문제 보완 세트가, 즉, co-NP의 문제 보완 세트의 하위 집합인 것으로 이어진다. 즉, co-NP ⊆ NP. 따라서 co-NP = NP. NP ≠ co-NP가 대칭적이라면 공동 NP-완전한 문제가 없다는 증거는 NP에 있을 수 있다.

정수 인자화

주요 기사: 정수 인자화

NP와 co-NP 모두에 속한다고 알려진 문제의 예로는 정수 인자화가 있다. (P에 속한다고는 알려져 있지 않지만) 정수의 m과 n을 주어진다면 m이 n보다 작고 1보다 큰 인자를 가지고 있는지를 결정한다. NP의 멤버십은 명확하다; 만약 m이 그러한 요소를 가지고 있다면, 그 요소 자체는 증명서일 것이다. co-NP의 멤버십은 또한 간단하다: 검증자가 곱셈과 AKS 프라이머리티 테스트에 의해 유효함을 확인할 수 있는 모두 n보다 크거나 같은 m의 주요 인자를 나열할 수 있다. 현재 인자화를 위한 다항식 시간 알고리즘이 있는지 여부는 알 수 없으며, 마찬가지로 정수 인자화가 P에 있으며, 따라서 이 예는 NP와 co-NP에 있지만 P에 있는 것으로 알려져 있지 않은 가장 자연스러운 문제 중 하나로 흥미롭다.[citation needed]

참조

  1. ^ Jump up to: a b Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. p. 56. ISBN 978-0-521-42426-4.
  2. ^ Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Boston: Addison-Wesley. ISBN 0-201-44124-1. 제11장
  3. ^ Goldreich, Oded (2010). P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. p. 155. ISBN 9781139490092.

외부 링크