유명한 동형 추측 버먼과 Hartmanis의는 모든 것을 말한다 – 완전한 언어가 서로 다항식 시간 동형 (P-동형)입니다. 추측의 중요한 의미는 P ≠ N P를 암시한다는 것 입니다. 그것은 1977 년에 출판, 증거를 지원하는 조각은 모든 것을이었다 N P 당시에 알려진 – 완전한 문제가 실제로 P-동형했다. 사실, 그들은 모두 패딩 가능했습니다 . 이는 훌륭하고 자연적인 속성이며, 사소한 방식으로 p 동형을 의미합니다.
NPP≠NP
NP
후보 때문에 그 이후로, 추측의 신뢰 악화 – 완전한 언어 가능성이 P-동형을 할 수없는 것을 발견 한 S T 문제가 여전히 열려 있지만,. 그러나 내가 아는 한, 이러한 후보 중 어느 것도 자연 문제를 대표하지 않습니다 . 그것들은 동 형사상 추측을 반증하기 위해 대각선 화를 통해 구성된다.
NPSAT
거의 40 년이 지난 후에도 알려진 모든 자연적인 – P- 완전 문제가 S A T에 대해 p- 동형 이라는 것이 여전히 사실 입니까? 아니면, 그에 반대되는 추측 된 자연적인 후보자가 있습니까?
NPSAT
답변
나는 그 대답이 ‘그렇다’고 생각한다. 오늘날에도 이소 모 니즘 추측을 위반할 수있는 알려진 자연적 문제는 없다.
주된 이유는 일반적으로 자연적인 NP- 완전 문제가 쉽게 패딩 될 수있는 것으로 보여 졌기 때문에 Berman과 Hartmanis는 SAT에 동형 인 것으로 나타났습니다. 자연스러운 그래프 관련 문제의 경우 일반적으로 그래프에서 연결이 끊어 지거나 매우 특정한 (보통 명백한) 방식으로 연결된 추가 정점을 추가해야합니다. 의사 결정 버전의 최적화 문제의 경우 일반적으로 제약 조건이없는 새로운 더미 변수를 추가해야합니다. 등등.