결정 문제가 다음과 같이 정의된다는 생각을 이해합니다.
비용이 C보다 낮은 경로 P가 있습니까?
수신 경로를 확인하여 이것이 사실인지 쉽게 확인할 수 있습니다.
그러나이 기준에 맞는 경로가 없으면 어떻게됩니까? 최고의 경로 TSP 문제를 해결하지 않고 “아니오”라는 대답을 어떻게 확인하고 가장 좋은 방법을 찾는 것이 C보다 비용이 더 비쌉니까?
답변
NP 는 “예”인스턴스를 확인할 수있는 문제의 클래스입니다. “아니오”인스턴스를 확인할 수 있다는 보장은 없습니다.
다항식 시간에 “아니오”인스턴스를 확인할 수있는 문제 클래스는 co-NP 입니다. 의 모든 언어 공동 순이익은 일부 언어의 보완 NP , 그 반대의 경우도 마찬가지입니다. 예는 비 착색성과 같은 것들을 포함합니다. “최대 길이를 가진 TSP 경로가 없습니까?” 에 또한 공동 NP : 당신이 이중 부정을 뽑아 풀다 경우, 그 문제에 “NO”인스턴스는 TSP에 “예”인스턴스가없는 우리는 다항식 시간에 사람들을 확인할 수 있습니다.
C
정수 인수 분해 및 P의 문제와 같이 NP 와 co-NP 모두에있는 것으로 알려진 몇 가지 문제 가 있습니다 . ( 이 점을 지적 해 준 user21820 에게 감사합니다 .)
NP 와 co-NP 가 동일한 문제 세트 인지 여부는 알려져 있지 않습니다 . 동일한 경우 TSP의 “예”와 “아니오”인스턴스를 모두 확인할 수 있습니다. 서로 다르면 P
≠우리는 P를 알고 있기 때문에 NP
=co-P (결정적 기계의 대답을 부정하고 보완 문제에 대한 답을 줄 수 있기 때문에).
답변
“여행 판매원 문제를 다항식 시간으로 어떻게 확인할 수 있습니까?”
당신이 묘사하는 방식 중 하나이거나, 그런 방법으로 알려져 있지 않습니다.
“그러나이 기준에 맞는 경로가 없으면 어떻게됩니까?”
이 경우 결정 문제점에 대한 모든 NP 기계에 대해 기계는 모든 후보 인증에 대해 아니오를 리턴합니다.
“최고의 경로 TSP 문제를 해결하지 않고”아니오 “의 답을 어떻게 확인하고 가장 좋은 것을 찾는 것이 C보다 비용이 더 비쌉니까?”
글쎄, 그러한 경로가 없다는 대화식 증거를 얻을 수 있습니다.
설명하는 문제인 TSP는 coNP 에있는 것으로 알려져 있지 않으므로 이러한 경로가 없음을 확인하는 “NP와 같은”방법은 없습니다.