P-NP

- https://gazelle-and-cs.tistory.com/64

P = deterministic Polynomial, NP = Nondeterministic Polynomial

P vs NP 쉽게 이해하기 블로그에 따르면 어떤 질문에 Yes / No로 답할 수 있거나 배열을 정렬하는 것과 같이 같은 입력으로 같은 출력이 나오는 문제를 결정론적이라고 말할 수 있습니다. 반면에 날씨를 예측한다거나 외판원이 모든 도시를 방문하는 가장 저렴한 경로를 찾는 문제와 같이 문제를 해결하기 위한 방법 혹은 그 결과가 매번 달라질 수 있는 문제를 비결정론적이라고 말할 수 있습니다.

스도쿠 문제를 예로 들어봅시다. 빈칸을 채워넣어 가로, 세로, 빈칸이 위치한 9개 크기의 셀 각각에 대하여 1부터 9까지가 유일하게 들어가야 합니다. 빈칸에 집어넣을 수 있는 경우의 수는 1부터 9까지, 총 81개의 빈칸을 채워야 하므로 무려 \(9^{81}\)이나 되는 무지막지한 경우의 수를 채워야 합니다. 빈칸의 개수를 N으로 두었을때 최악시간복잡도는 \(O(9^N)\)이죠. 이는 다항시간 내에 계산이 불가능하므로 P가 아닙니다.

다만 N개의 빈칸에 숫자를 채워넣었을때 그것이 틀린 답인지, 옳은 답인지를 구별하는데는 다항시간 내에 계산이 됩니다. 따라서 비결정적 알고리즘으로 보았을땐 다항시간으로 문제가 풀리므로 NP입니다.