주의 ≡

어떤 문제가 NP일 때, 이 문제는 P에도 해당할까요? P-NP 문제는 아직까지도 풀리지 않은 컴퓨터 과학계의 난제입니다. 클레이 수학 연구소(Clay Mathematics Institute)에서는 이를 밀레니엄 문제 중 하나로 선정하고 백만 달러의 상금을 걸었습니다. P-NP 문제에 대한 해답이 밝혀지면 인류는 AI, 암호학, 이론적 컴퓨터 공학 분야에서 엄청난 진전을 이룰 것입니다.

▲ 그림 4-2 풀리지 않은 P-NP 문제