http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

튜링 기계

http://www.ibs.re.kr/newsletter/2014/12/sub_01.html

테이프 위를 움직이며, 테이프에 쓰여진 기호를 읽고 명령을 수행하는 기계.

튜링 기계에는 한 번에 하나의 상태만 가질 수 있는 –현대의 컴퓨터– 결정론적 튜링 기계와 한 번에 여러 상태를 동시에 가질 수 있는 –양자 컴퓨터– 비결정론적 튜링 기계가 있다.

비결정론적 튜링 기계는 분기 상황을 한 번에 진행할 수 있기 때문에, 결정론적 튜링 기계로 지수 시간이 걸리는 문제를 다항식 시간내에 해결할 수 있다. —지수 함수에 Log를 씌웠다고 생각하면 된다.

튜링 기계 –명령을 수행하는 방식– 를 폰 노이만 구조 –CPU, 메모리, 프로그램으로 구분된– 로 만들어낸 것이 현대의 컴퓨터라고 할 수 있다.

결정 문제 (Decision Problem)

Yes or No로 대답할 수 있는 문제.

‘n개의 도시를 모두 방문하고 돌아오는 최단거리를 구하라’는 문제는 Yes, No로 대답할 수 없지만, ‘n개의 도시를 모두 방문하고 돌아오는 거리 K이하인 경로가 존재하는가?’ 는 Yes, No로 대답할 수 있으므로 결정문제다.

P와 NP는 모두 결정 문제에 속한다.

다항 시간

다항 시간이라는 것은 현실적인 시간 내에 해결 가능한 시간을 의미한다. 문제 해결 자체는 가능하지만 해결하는데 시간이 $10^{10}$초 정도의 시간이 걸린다면 현실적으로 해결하기 어려운 시간이라는 의미다. –참고로 우주의 나이는 $4.35 \times 10^{17}$이다. 다항 시간을 넘어서는 시간을 지수 시간이라고 한다.

일반적으로 다항식하면 $x^{n}$이 포함되지만, 알고리즘에서 다항 시간은 알고리즘 함수의 최고차 항의 계수가 3이하이거나 $N \log N$ 으로 표시되는 정도까지 인정한다. 지수 범위가 5만 넘어가도 현실적인 시간 내에 풀기는 어려우므로 다항식 시간이라고 보기는 어렵다.

P (Polynomial time)

결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합.

NP (Non-deterministic Polynomial time)

비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합. 또는 Yes라는 근거가 제시되었을 때 결정론적 튜링 기계로 그것이 옳다는 것을 다항식 시간에 확인할 수 있는 문제의 집합.