P=NP는 수십년동안 해결되지 않은 난제로 남아있다. 위 문제가 암호에 관련이 있다고 하는데 어떤 연관이 있는지 알아보자. NP Class 전 시간에 $NP$는 NTM이 다항시간에 해결하는 Problem 집합이라고 했다. 이와 다르게 $NP$를 정의할 수 있다. $NP$는 DTM에게 적절한 힌트를 주면 YES를 검증할 수 있거나 다항시간에 해결할 수 있는 Problem 집합이다. NP-Complete라고 했던 Longest Path 문제를 보자. 단순히 그래프를 주고 A -> B로 가는 가장 긴 경로를 출력하라고 하면 힘들것이다. 하지만 문제를 그래프를 주고 A -> B로 가는 k이상의 경로가 있는가?로 바꾼다면 검증할 수 있다. 그러한 경로를 보여주면 된다! Longest Path문제도 그런 경로를 보..