0
그래프에 해밀턴 경로가 있는지 알아 내려면 다항식 시간으로 계산되지 않는다고 들었습니다. 우리가 다항식 시간에 그것을 풀 수 있다고 가정 해 봅시다. 어떻게 증명할 수 있습니까? 그것은 NP 어려운 문제이기 때문에 불가능한가요?해밀턴 경로 분석
A
답변
0
Hamiltonian Path Problem은 NP-complete입니다.
아무도 입증 된이 다항식 시간에 그것을 해결하는 것은 불가능하지만 그러한 솔루션이 존재하는 것은 거의 없습니다. 만약 당신이 그것을 발견하게된다면, 이것은 당신이 P = NP로 입증되었음을 암시하며, Clay Math Institute는 말 그대로 백만 달러를 당신에게 줄 것입니다.