P-NP 관련 문제

Optimal한 해결책을 찾을 수 있을까?

두가지 경우로 나눌 수 있다. 되는경우, 안되는경우

먼저 되는경우를 보자.
되는 경우는 graph coloring이다. 이것은 NP-complete이다.
'k개의 color로 vertex를 칠할 수 있는가?' 라는 decision problem이 polynomial time내에 결정가능하다면 vertex 수만큼 1~n까지 반복해도 역시 n에 polynomial time내에 칠할 수 있으므로 optimal한 해결책을 찾을 수 있다.

그렇다면 안되는 경우는 무엇일까?
Hamilton cycle이다. 이것 역시 대표적인 NP-complete이다.
'tour 할때 비용이 k이하인 답이 있는가?'라는 decision problem이 polynomial time내에 결정가능하다고하자. 하지만 그 k이하인 답이 언제 나올지 나올지 모른다. 처음 시도하자마자 나올수도 있고 죽을때까지 하더라도 못찾을 수도 있다. 따라서 이것을 polynomial time내에 할 수 있다고 단정할 수 없다.  따라서 이것은 optimal한 해결책을 찾을 수 없다.