Co-NP-완전
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
Co-NP-완전은 결정 문제 C가 co-NP에 속하고, co-NP에 속하는 모든 문제가 다항 시간 내에 C로 다항 시간 다대일 환원될 수 있을 때를 의미한다. 이는 co-NP 문제 L에 대해, L의 모든 인스턴스를 동일한 진리값을 갖는 C의 인스턴스로 변환할 수 있는 다항 시간 알고리즘이 존재한다는 것을 뜻한다. 만약 C에 대한 다항 시간 알고리즘이 존재한다면, 모든 co-NP 문제를 다항 시간 내에 해결할 수 있다. 주어진 부울 공식이 항진명제인지 판단하는 문제는 co-NP-완전 문제의 대표적인 예시이며, 이는 부울 만족 가능성 문제와 밀접한 관련이 있다.
더 읽어볼만한 페이지
| Co-NP-완전 | |
|---|---|
| 개요 | |
| 정의 | 어떤 NP 문제에 대해, 그 문제의 여집합이 다항 시간 내에 주어진 co-NP 문제로 환산될 수 있다면, 그 co-NP 문제는 co-NP-완전이라고 한다. |
| 설명 | co-NP-완전 문제는 NP-완전 문제와 유사하게, co-NP에서 가장 어려운 문제 부류로 생각할 수 있다. |
| 특징 | 어떤 문제가 NP와 co-NP에 동시에 속한다면, 그 문제는 NP-완전 문제도 아니고 co-NP-완전 문제도 아니다. 만약 NP와 co-NP가 같다면 예외이다. 어떤 문제가 NP-완전이라면, 그 문제의 여집합은 co-NP-완전이다. |
| 중요성 | 만약 어떤 NP-완전 문제가 co-NP에 속한다면, NP = co-NP이다. |
| 참고 | NP = co-NP인지 여부는 P = NP 문제만큼이나 풀리지 않은 중요한 문제이다. |
| 같이 보기 | |
| 관련 개념 | NP NP-완전 co-NP 다항 시간 환산 |
2. 정의
결정 문제 ''C''가 co-NP에 속하고, co-NP에 속하는 모든 문제가 다항 시간 내에 ''C''로 다항 시간 다대일 환원될 수 있다면, ''C''는 co-NP-완전이다.[2]
2. 1. 상세 설명
결정 문제 C가 co-NP에 속하고, co-NP에 속하는 모든 문제가 다항 시간 내에 C로 다항 시간 다대일 환원될 수 있다면, C는 co-NP-완전이다.[2] 이는 co-NP 문제 L에 대해, L의 모든 인스턴스를 동일한 진리값을 갖는 C의 인스턴스로 변환할 수 있는 다항 시간 알고리즘이 존재한다는 것을 의미한다. 결과적으로, 만약 C에 대한 다항 시간 알고리즘이 있다면, 우리는 모든 co-NP 문제를 다항 시간 내에 해결할 수 있다.3. 예시
`co-NP-완전` 문제의 한 예시는 주어진 부울 공식이 항진명제인지 판단하는 문제이다.[2]
3. 1. 부울 만족 가능성 문제와의 관계
co-NP-완전 문제의 한 예시는 주어진 부울 공식이 항진명제인지, 즉 변수에 참/거짓 값을 할당하는 모든 가능한 경우에 참이 되는지 판단하는 문제인 항진명제 (tautology)이다. 이는 그러한 할당이 ''적어도 하나'' 존재하는지 묻는 부울 만족 가능성 문제와 밀접한 관련이 있으며, 부울 만족 가능성 문제는 NP-완전 문제이다.[2]참조
[1]
논문
A Note on Sparse Complete Sets
https://ecommons.cor[...]
[2]
서적
Complexity Theory: A Modern Approach
http://www.cs.prince[...]
Cambridge University Press
2009
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com