확인은 1초, 찾기는 영원 — P vs NP가 55년째 안 풀리는 진짜 이유

여러분이 스도쿠를 하나 받았다고 합시다. 완성된 답을 보면 맞는지 1초 만에 알 수 있습니다. 그런데 그 답을 직접 찾는 데는 몇 시간이 걸릴 수 있습니다.

이 비대칭이 우연인지, 아니면 근본적인 벽인지를 묻는 문제가 P vs NP입니다. 1971년에 공식화됐고, 2000년 밀레니엄 문제로 100만 달러가 걸렸습니다. 그리고 55년째 아무도 못 풀었습니다.

정의: 두 개의 방

P는 '빠르게 풀 수 있는' 문제의 집합입니다. 정확히는 입력 크기 n에 대해 다항 시간(n, n², n³ …)에 답을 내는 알고리즘이 존재하는 문제입니다. 정렬, 최단 경로, 소수 판정이 여기 있습니다.

NP는 '빠르게 확인할 수 있는' 문제의 집합입니다. 답 후보를 받았을 때, 그게 맞는지 다항 시간에 검증할 수 있으면 NP입니다.

중요한 것은 P는 NP에 포함된다는 점입니다. 빠르게 풀 수 있으면, 풀어놓고 확인하는 것도 빠릅니다. 그래서 질문은 딱 하나로 좁혀집니다.

P = NP인가, P ≠ NP인가. 즉 '확인은 쉬운데 찾기는 어려운' 문제가 정말로 존재하는가.

왜 이게 실용적인가: 세상이 걸려 있다

이 문제가 추상적 수학처럼 보이지만, 실제로는 현대 문명의 암호가 여기 매달려 있습니다.

RSA 암호는 '큰 수의 소인수분해는 어렵다'는 가정에 기반합니다. 두 소수를 곱하는 것은 쉽습니다. 곱해진 결과에서 원래 두 소수를 찾는 것은 어렵습니다. 이 비대칭이 보안의 근거입니다.

만약 P = NP라면? 소인수분해도 '빠르게 풀 수 있는' 문제가 됩니다. 그러면 RSA가 무너집니다. 인터넷 뱅킹, 전자서명, HTTPS의 상당 부분이 같은 운명입니다.

반대로 P ≠ NP라면? 암호는 안전하고, 대신 '어떤 문제는 영원히 효율적으로 풀 수 없다'는 것이 확정됩니다. 최적화, 단백질 접힘, 외판원 문제 같은 것들이 구조적으로 어렵다고 증명되는 것입니다.

스티븐 쿡. 1971년 모든 NP 문제가 SAT로 환원됨을 증명했습니다. (CC BY 2.0)

핵심 도구: 환원(reduction)

여기서 수학의 무기가 등장합니다. 환원(reduction)입니다. 문제 A를 문제 B로 바꿔치기할 수 있다면, B를 푸는 방법으로 A도 풉니다.

1971년 스티븐 쿡이 결정적 결과를 냈습니다. SAT(불 만족 문제) — 논리식이 참이 되게 하는 변수 조합이 있는지 — 를 모든 NP 문제가 환원될 수 있는 문제로 증명했습니다.

즉 SAT는 NP에서 가장 어렵습니다. SAT를 빠르게 풀면 모든 NP 문제를 빠르게 풉니다. 이런 문제를 NP-완전(NP-complete)이라고 부릅니다. 쿡은 이 공로로 튜링상을 받았습니다.

그리고 같은 해 레오니드 레빈이 독립적으로 같은 결과를 냈습니다. 그래서 쿡-레빈 정리입니다.

이후 수천 개의 문제가 NP-완전으로 판명됐습니다. 외판원 문제, 배낭 문제, 그래프 색칠, 스도쿠 일반화, 스케줄링. 전부 서로 환원됩니다. 하나만 빠르게 풀면 전부 무너집니다.

튜링 기계 모형. P와 NP는 모두 이 계산 모델 위에서 정의됩니다. (CC BY 3.0)

왜 안 풀리나: 4개의 벽

여기가 이 글의 핵심입니다. '아직 못 풀었다'가 아니라 '어떤 증명 방법은 이미 불가능하다고 증명됐다'는 것이 진짜 상황입니다.

1) 상대화(relativization)의 벽. 1975년 베이커, 길, 솔로베이가 발견했습니다. 오라클을 붙이면 P=NP가 되는 세계도, P≠NP가 되는 세계도 존재합니다. 즉 '오라클을 써도 통하는 증명 기법'으로는 절대 답을 낼 수 없습니다. 대각선 논법 같은 고전적 기법이 여기서 막힙니다.

2) 자연적 증명(natural proofs)의 벽. 1994년 라즈보로프와 루디치가 보였습니다. 회로 복잡도 하한을 증명하는 자연스러운 방식은, 암호가 존재한다는 가정과 충돌합니다. 즉 그런 증명이 성공하면 RSA가 깨진다는 뜻이 되어, 암호학자들이 반대편에서 막고 있습니다.

3) 대수화(algebraization)의 벽. 2008년 애런슨과 위그더슨. 산술화한 증명 기법도 모든 오라클에 대해 통하면 마찬가지로 막힙니다.

4) 장벽 자체가 정리다. 이 세 개는 '우리가 쓰는 도구로는 안 된다'를 수학적으로 확정한 결과입니다. 그래서 새 증명은 이 장벽을 우회하는 완전히 새로운 아이디어를 필요로 합니다.

반전: '거의 증명'은 계속 나온다

여기서 균형이 필요합니다. P vs NP는 아무 진전이 없는 문제가 아닙니다. 다만 진전이 다른 방향으로 나갑니다.

· 회로 하한. 'P에 있지만 작은 회로로는 못 푸는 문제'가 존재한다는 것은 증명됐습니다. 다만 그게 NP 전체와 어떤 관계인지는 모릅니다.

· 조건부 결과. '만약 X가 성립하면 P≠NP'라는 형태의 정리가 많이 나왔습니다. 문제를 다른 미해결 문제에 묶어놓는 방식입니다.

· 특수 모델에서의 분리. 단조 회로, 결정 트리, 양자 쿼리 같은 제한된 계산 모델에서는 하한이 증명됩니다. 문제는 그 모델이 실제 컴퓨터와 다르다는 것입니다.

· 잘못된 증명의 역사. 2010년 HP의 비나이 데올라리카르가 P≠NP 증명을 발표했지만 오류로 판명됐습니다. 이후에도 수차례 '증명'이 나왔고 모두 검증을 통과하지 못했습니다. 이 분야에서 '증명했다'는 주장은 검증 전까지 신뢰하지 않는 것이 규칙입니다.

NP와 다른 것들: 헷갈리는 지도

주변 개념을 정리하면 이렇습니다.

· co-NP — '아니다'를 빠르게 확인할 수 있는 문제. P=NP 문제는 P=co-NP 문제와도 연결됩니다.
· NP-난해(NP-hard) — NP의 모든 문제가 환원되는 문제. NP에 속하지 않아도 됩니다. 정지 문제는 NP-hard입니다.
· PSPACE — 다항 공간으로 풀 수 있는 문제. NP를 포함하고, P=NP여도 PSPACE는 더 클 수 있습니다.
· BQP — 양자 컴퓨터가 효율적으로 푸는 문제. 양자 컴퓨터도 P vs NP를 해결하지 않습니다. 쇼어 알고리즘은 인수분해를 빠르게 하지만, NP-완전 문제는 여전히 어렵습니다.

마지막 항목이 자주 오해됩니다. '양자 컴퓨터가 나오면 P=NP 아니냐'는 질문이 많은데, 답은 아니오입니다.

왜 증명이 이렇게 어려운가: 기술적 이유

증명하기 어려운 구조적 이유가 있습니다.

1) 부정 명제를 증명해야 한다. 'P=NP'를 보이려면 알고리즘 하나를 제시하면 됩니다. 증명은 쉽습니다(찾기만 하면). 반면 'P≠NP'는 '모든 가능한 알고리즘이 실패한다'를 보여야 합니다. 무한한 공간에 대한 부정입니다.

2) 하한 증명의 일반적 난점. 어떤 문제가 빠르게 풀릴 수 없다는 것을 보이는 것은, 풀릴 수 있다는 것을 보이는 것보다 원리적으로 어렵습니다. 좋은 알고리즘을 못 찾은 것과 존재하지 않는다는 것은 완전히 다릅니다.

3) 이론과 실전의 간극. 실제로 NP-완전 문제들은 SAT 솔버로 놀랍게 잘 풀립니다. 산업 규모의 문제도 풀립니다. 만약 그렇다면 P=NP에 가까운 무언가가 있는 것일까요. 아닙니다. 솔버는 최악의 경우를 보장하지 않습니다. P vs NP는 최악의 경우에 대한 질문입니다.

실무자에게 이 문제가 주는 것

P vs NP를 몰라도 코딩은 됩니다. 하지만 이 문제를 알면 세 가지 판단이 달라집니다.

1) '최적화가 안 되는 문제'를 구분합니다. 스케줄링, 배차, 패킹이 안 풀릴 때 코드가 나쁜 게 아니라 문제가 NP-완전일 수 있습니다. 그때는 정확해를 포기하고 근사·휴리스틱으로 가야 합니다.

2) '확인 가능성'을 설계 도구로 씁니다. 답을 검증하는 함수가 쉽게 써진다면, 그 문제는 NP에 있습니다. 그러면 해를 찾는 대신 후보를 생성하고 검증하는 구조가 유효합니다.

3) 암호의 가정을 이해합니다. 우리가 쓰는 보안은 P≠NP(또는 그 특수한 경우)에 기대고 있습니다. 이 가정이 흔들리면 시스템 전체가 흔들립니다. 그래서 양자내성암호로의 이전이 진행 중입니다.

그래서 결론

P vs NP는 '아직 못 푼 문제'가 아니라 '어떻게 풀어야 하는지조차 모르는 문제'입니다. 우리가 아는 증명 기법 상당수가 이 문제에는 쓸 수 없다고 이미 증명됐습니다.

그리고 이 문제의 답이 무엇이든 세상은 크게 바뀝니다. P=NP면 암호가 무너지고, P≠NP면 '영원히 어려운 문제'가 확정됩니다. 어느 쪽이든 인류의 계산관이 바뀝니다.

여러분 생각은 어떠신가요? P=NP일까요, P≠NP일까요? 그리고 만약 P=NP라면 가장 먼저 무엇을 하시겠습니까? 댓글로 남겨주세요.

참고 자료

• Cook, S. A. (1971), "The Complexity of Theorem-Proving Procedures" — NP-완전성과 쿡-레빈 정리
• Baker, Gill, Solovay (1975), "Relativizations of the P =? NP Question" — 상대화 장벽
• Razborov, Rudich (1994), "Natural Proofs" — 자연적 증명 장벽
• Aaronson, Wigderson (2008), "Algebrization: A New Barrier in Complexity Theory" — 대수화 장벽
• Clay Mathematics Institute — 밀레니엄 문제(P vs NP), 상금 100만 달러
• 본 글은 개념과 연구 지형을 정리한 것이며, 문제의 해결을 주장하지 않습니다.