Co-NP-완전

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의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 다항 시간 환산

📚 더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

1. 개요
2. 정의
- 2.1. 상세 설명
3. 예시
- 3.1. 부울 만족 가능성 문제와의 관계

2. 정의

결정 문제 C가 co-NP에 속하고, co-NP에 속하는 모든 문제가 다항 시간 내에 C로 다항 시간 다대일 환원될 수 있다면, C는 co-NP-완전이다.

2.1. 상세 설명

결정 문제 C가 co-NP에 속하고, co-NP에 속하는 모든 문제가 다항 시간 내에 C로 다항 시간 다대일 환원될 수 있다면, C는 co-NP-완전이다. 이는 co-NP 문제 L에 대해, L의 모든 인스턴스를 동일한 진리값을 갖는 C의 인스턴스로 변환할 수 있는 다항 시간 알고리즘이 존재한다는 것을 의미한다. 결과적으로, 만약 C에 대한 다항 시간 알고리즘이 있다면, 우리는 모든 co-NP 문제를 다항 시간 내에 해결할 수 있다.

3. 예시

`co-NP-완전` 문제의 한 예시는 주어진 부울 공식이 항진명제인지 판단하는 문제이다.

3.1. 부울 만족 가능성 문제와의 관계

co-NP-완전 문제의 한 예시는 주어진 부울 공식이 항진명제인지, 즉 변수에 참/거짓 값을 할당하는 모든 가능한 경우에 참이 되는지 판단하는 문제인 항진명제 (tautology)이다. 이는 그러한 할당이 적어도 하나 존재하는지 묻는 부울 만족 가능성 문제와 밀접한 관련이 있으며, 부울 만족 가능성 문제는 NP-완전 문제이다.