1,000조각 직소 퍼즐을 맞추는 데는 몇 시간이 걸려요. 다른 사람이 다 맞춘 걸 확인하는 데는 몇 초면 돼요. 이 차이는 진짜일까요, 아니면 아직 똑똑한 방법을 못 찾았을 뿐일까요? 그게 P 대 NP 문제예요.

기숙사 배정 예시
클레이 수학연구소는 이렇게 설명해요. 학생은 400명인데 기숙사 자리는 100개뿐이고, 학장이 함께 살면 안 되는 학생 짝 목록을 줘요. 누가 만든 100명 명단을 확인하는 건 쉬워요. 금지된 짝이 없는지만 보면 되니까요. 하지만 그런 명단을 처음부터 찾는 건 달라요. 400명 중 100명을 고르는 방법의 수가 알려진 우주의 원자 수보다 많아서, 컴퓨터로 하나씩 다 따져 볼 수도 없어요.
P와 NP는 무슨 뜻일까

P는 컴퓨터가 빨리 풀 수 있는 문제들이에요. NP는 제시된 답을 빨리 확인할 수 있는 문제들이에요. 클레이 연구소는 P를 '찾기 쉬움', NP를 '확인하기 쉬움'이라고 줄여 말해요.
핵심 질문은 이거예요. 확인하기 쉬운 문제는 사실 모두 풀기도 쉬울까요? 그렇다면 P = NP예요. 대부분의 연구자는 아니라고 짐작하지만, 어느 쪽도 증명한 사람은 없어요.
100만 달러짜리 질문
스티븐 쿡과 레오니드 레빈이 1971년 각자 이 문제를 정식화했어요. 클레이 연구소는 2000년 이 문제를 7대 밀레니엄 문제 중 하나로 정하고 문제마다 100만 달러를 걸었어요. 지금까지 풀린 건 푸앵카레 추측 하나뿐이에요.
자주 묻는 질문
- NP는 무슨 뜻이에요?
- 비결정적 다항 시간(Nondeterministic Polynomial time)의 약자예요. 쉽게 말해 답을 빨리 확인할 수 있다는 뜻이에요.
- 누가 풀었나요?
- 아직 아무도 못 풀었고, 클레이 상금도 그대로 남아 있어요.
- 왜 중요해요?
- 일정 짜기, 경로 찾기, 보안 같은 어려운 문제들에 빠른 해법이 있는지가 걸려 있어요.
참고문헌
- Clay Mathematics Institute. P vs NP. 공식 문제 소개: 확인은 쉬운데 풀기도 쉬울까, 기숙사 배정 예시, 1971년 쿡과 레빈.
- Clay Mathematics Institute. The Millennium Prize Problems. 2000년 지정된 7문제, 문제당 100만 달러, 푸앵카레 추측만 해결.