저는 컴퓨터 과학 학생이며 NP 문제의 검증 기반 정의를 이해하는 데 문제가 있습니다.NP 검증기 기반 정의
정의에 따르면 "인증서"가있는 결정적 튜링 기계로 폴리 노미 널 시간에 문제가 확인 될 수있는 경우 NP에 있음을 나타냅니다.
그러나 인증서가 문제의 해결책 일 경우 어떻게됩니까? 이것은 약간의 문제이며, 입력 크기에 따라 폴리 노미 널 적으로 제한됩니다. 따라서 상수, 즉 폴리 노미 널 시간에서 분명히 검증 가능합니다.
그러므로 각 결정 문제는 NP에 속합니다.
어디가 잘못 되었나요?
그러나 인증서가 문제의 해결책 일 경우 어떻게됩니까? 이것은 약간의 문제이며, 입력 크기에 따라 폴리 노미 널 적으로 제한됩니다. 따라서 상수, 즉 폴리 노미 널 시간에서 분명히 검증 가능합니다.
왜 "분명히"? 솔루션을 검증하는 데 엄청난 시간을 소비해야 할 수도 있습니다.이 경우 NP에 문제가있을 필요는 없습니다. 요점은 인증서가 의사 결정 문제에 대한 단일 비트 임에도 불구하고 모름 해당 비트가 0인지 1인지를 확인하여 문제를 해결할 수 있는지 여부입니다. (당신이 항상 알고 있었다면, P 나 NP의 어떤 결정 문제도 일정 시간 내에 풀릴 수 있습니다.)
해가 길이가 다항식이라 할지라도 다항식으로 모든 문제를 검증 할 수있는 것은 아닙니다. 여행 세일즈맨 문제를 고려해 볼 수 있습니다. 주어진 솔루션이 도시의 여행인지 여부 만 확인할 수있는 해결책이 주어 지지만 모든 가능한 둘러보기를 탐색하지 않는 한 최소 길이의 여행인지 여부를 알 수 없습니다. 최적화 문제는 NP-하드 (예 : 최소 길이 투어를 찾는)
동안 결정 문제는 NP-완료 대부분의 경우에 따라서
은 (도시의 세트가 투어를 포함 여부 예는 찾을 수) 내 말은 : 문제가 주어진 경우 출력을 인증서로 사용하면 문제가 확인되면 1, 문제가 확인되지 않으면 0이됩니다. 따라서 검증기 컴퓨터는 인증서를 출력으로 반환하면됩니다. 정답을 제시하십시오. 의심의 여지가 np 클래스의 개념적 이해가 아니라 그것을 정의하는 형식주의의 이해에 있습니다. – Simone
@ Simone : 당신은 인증서의 정의가 잘못되었다고 생각합니다. [Wikipedia] (http://en.wikipedia.org/wiki/NP_%28complexity%29)는 * 인증서 * (암시 적으로)를 검증 할 후보 솔루션으로 정의합니다. 반드시 단일 비트 일 필요는 없습니다. –
반드시 그런 것은 아니지만 1 개의 단일 비트가 될 수 있습니다. 그리고 만약 그 비트가 문제의 결과물이라면, 검증 자의 출력으로 사용할 수있는 것보다 – Simone