최초의 NP- 완료 문제는 NP- 완성 된 것으로 어떻게 나타 났습니까?

Question

NP-Complete의 Wikipedia 항목에서 :

"새로운 문제가 NP- 완성임을 증명하는 가장 쉬운 방법은 먼저 NP에 있음을 증명 한 다음 알려진 NP- 완성 문제를 줄이는 것입니다."

나는 이것을 이해한다고 확신한다 : 문제가 있다면, 나는 그것이 np- 완성임을 보여줄 수있다.

1. NP에 있음을 보여줍니다 (문제에 대한 해결책은 비 결정적 튜링 머신에서 다항식 시간에 확인할 수 있습니다).

2. NP- 완성으로 이미 알려진 문제는 새로운 문제로 '축소'될 수 있음을 보여줍니다.

제 질문은, 최초의 NP- 완료 문제가 NP- 완성 된 것으로 어떻게 입증 되었습니까? 한 번에 알려진 NP- 완료 문제의 세트는 0이었을 것입니다. 이는 위의 프로세스에서 2 단계에 의지하는 것이 불가능했을 것입니다.

이것은 내가 알지 못하는 증거를위한 다른 방법이 있다고 생각하게한다. 그 중 하나 또는 아마도 NP- 완료 속성이 알려진 다항식 시간 솔루션이 없기 때문에 특정 문제에 대해 '가정'될 수 있습니다. (실제로, 이것을 썼다면, 이것이 사실이라면 놀라지 않을 것입니다. 그러나 어느 쪽이든 구루 피드백을 원합니다).

Answer 1

쿡의 정리

클래스 NP는 다항식 시간에 비정상적인 튜링 머신에 의해 결정될 수있는 문제의 클래스로 정의 될 수 있습니다. 이 정리는 그것을 보여줍니다 SAT는 NP- 완성입니다 부울 공식으로 비 결정적 튜링 머신의 작동을 인코딩함으로써, 해당 공식이 만족할 경우에만 기계가 수락하는 방식으로.

역사적으로, NP- 완전성의 개념은 Richard Karp의 주요 논문에서 소개되었습니다.조합 문제 사이의 감소성), 그는 NP- 완성성을 정의하고 Cook의 정리를 사용했으며 한 번의 큰 샷으로 NP가 완성 된 21 가지 문제를 입증했습니다.

Answer 2

당신에게 증거의 본질을주기 위해 (Garey & Johnson의 열심히 가고있는 여러 페이지 컴퓨터 및 다루기 쉬운):

계산 문제는 튜링 머신으로 표현 될 수 있습니다.

튜링 머신을 논리 문제로 표현하여 특정 복잡성 제약 조건을 충족 할 수 있습니다.

따라서 다항식 시간에 논리 문제를 해결할 수 있다면 다항식 시간에 튜링 머신 문제를 해결할 수 있습니다.

이것은 다른 고려 사항과 함께 다항식 시간에 논리 문제를 해결할 수 있다면 다항식 시간에 NP 문제를 해결할 수 있음을 보여줍니다. 이것은 NP- 완성의 정의이기 때문에 논리 문제는 NP- 완성되므로 다른 문제의 기초로 사용될 수 있습니다.

사용 된 논리 문제를 만족도라고합니다 (종종 SAT로 약칭). 양식 (A 또는 NOT-B 또는 NOT-C)의 일련의 조항 (논리적 또는 논리적으로 연결된 제안의 여러 가지 제안과 부정으로 구성된 조항)을 감안할 때, 모든 것을 만드는 제안에 진실 가치의 할당이 있습니까? 조항이 사실입니까?

NP- 완성성은 잘 정의 된 속성입니다. NP- 완료 문제에 대해 의심스러운 유일한 이유는 다른 NP- 완성 문제를 줄일 수 있다고 생각했지만 편리한 문제를 찾거나 아직 증거를 도출하지 않았기 때문입니다.

문제는 NP- 완료 문제가 존재하는지 또는 문제를 증명하는 방법이 NP- 완성인지가 아니라 그 의미입니다. 아무도 NP- 완성 문제를 해결하기 위해 다항식 시간 알고리즘을 아직 생성하지 않았으며, 그러한 알고리즘이 존재할 수 없다는 것을 증명하지는 않았습니다. P = NP의 여부에 관계없이, 우리는 확실히 NP- 완성 문제를 해결할 수있는 좋은 알고리즘이 없습니다.

이것은 Claypool Foundation의 Millenium 문제 중 하나이므로 몇 년 동안 매우 밝은 사람들을 피한 증거를 제시 할 수 있다면 백만 달러가 있습니다.