co-NP-완전
co-NP-complete복잡도 이론에서, co-NP-완전 계산 문제는 co-NP에서 가장 어려운 문제이며, 이는 co-NP의 어떤 문제도 다항식 오버헤드만으로 co-NP-완전 문제의 특별한 경우로 재구성될 수 있다는 점에서 그러하다.만약 P가 co-NP와 다르다면, 모든 co-NP-완전 문제는 다항식 시간에 풀 수 없습니다.co-NP-완전 문제를 신속하게 해결하는 방법이 있다면 그 알고리즘을 사용하여 모든 co-NP 문제를 신속하게 해결할 수 있습니다.
각 co-NP-완전 문제는 NP-완전 문제를 보완하는 것입니다.NP와 co-NP에는 모두 문제가 있습니다. 예를 들어 P의 모든 문제 또는 정수 인수분해와 같은 문제가 있습니다.그러나 불평등이 더 가능성이 높다고 생각되지만 집합이 동일한지 여부는 알려지지 않았다.자세한 내용은 co-NP 및 NP-complete를 참조하십시오.
Fortune은 1979년에 만약 어떤 희박한 언어가 co-NP-완전(또는 단지 co-NP-hard)이라면, P = NP,[1] Mahaney의 정리에 대한 중요한 기초라는 것을 보여주었다.
형식적 정의
판정문제 C는 co-NP에 있고, co-NP 내의 모든 문제가 다항식-다항식-다항식일 경우 [2]co-NP-완전이다.즉, 모든 co-NP 문제 L에 대해 L의 인스턴스를 동일한 진실 값을 가진 C의 인스턴스로 변환할 수 있는 다항식 시간 알고리즘이 존재함을 의미합니다.결과적으로, 만약 우리가 C에 대한 다항식 시간 알고리즘을 가지고 있다면, 우리는 모든 co-NP 문제를 다항식 시간에 풀 수 있을 것이다.
예
co-NP-완전문제의 예로는 tautology가 있습니다.이것은 주어진 부울식이 tautology인지 아닌지를 판별하는 문제입니다.즉, 변수에 참/거짓 값을 할당할 수 있는 모든 것이 참 스테이트먼트를 산출하는 것입니다.이는 이러한 할당이 적어도1개 존재하는지 여부를 묻고 NP-완전인 부울 만족도 문제와 [2]밀접하게 관련되어 있습니다.
레퍼런스
- ^ Fortune, S. (1979). "A Note on Sparse Complete Sets" (PDF). SIAM Journal on Computing. 8 (3): 431–433. doi:10.1137/0208034. hdl:1813/7473.
- ^ a b Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
