d라이브러리

컴퓨터로 문제를 해결하려면 컴퓨터에게 문제를 푸는 ‘알고리듬’을 알려줘야 합니다. 단순한 문제도 문제를 빨리 푸는 알고리듬을 모르면 정답을 찾지 못할 수도 있죠. 백만 달러, 한화로 약 11억 1500만 원의 상금이 걸린 7대 밀레니엄 문제 중 하나인 ‘P-NP 문제’는 ‘답을 빨리 찾는 알고리듬을 모르는 문제도 언젠가 그 알고리듬을 찾을 수 있지 않을까’라는 질문에서 출발합니다.
 

▼ 이어지는 기사를 보려면?

Intro. 수학문제 분류소, P와 NP는 같을까? 다를까?

Part1. NP와 P 분류하기

Part2. 'NP-완전' 골라내기 

Part3. P-NP 문제의 끝은 무엇일까? 

참고 이광근 ‘컴퓨터과학이 여는 세계’, 케이스 데블린 ‘수학의 밀레니엄 문제들 7’, 윌리엄 가자르 ‘Guest Column: the second P =?NP poll’

도움 엄상일(기초과학연구원(IBS) 이산수학그룹 CI, KAIST 수리과학과 교수) 디자인 유승민 일러스트 박장규