P=NP? P≠NP?
P 대 NP 문제에 대한 정확한 설명은 Stephen Cook 이 그의 선구적 논문 “The Complexity of Theorem‑Proving Procedures” (1971) 과 같은 시기에 러시아 학자인 Leonid Levin 논문으로 부터 출발했다. Cook-Levin 정리 발표 이후 Richard Karp가 “Reducibility Among Combinatorial Problems” (1972) 논문을 통해 21가지 문제가 NP-완전임을 증명하였다. P=NP는 모든 NP 문제를 P 문제처럼 다항 시간 안에 해결할 수 있는지를 묻는 문제이다. 클래스 P는 결정론적 튜링 기계로 다항 시간 안에 해를 찾을 수 있는 문제들의 집합이고, NP는 해답이 주어졌을 때 그 해를 다항 시간 안에 검증할 수..
