[개념] P=NP가 증명되면 무슨 일이 생길까요 — Y와 N, 그리고 암호의 운명

Posted by Euisuk's Dev Log on November 22, 2026

YouTube에서 영상 보기

답을 확인하기 쉽다면, 답을 찾기도 쉬울까요

리만 가설의 증명 소식을 접하고 나면 이런 질문이 따라옵니다. “오랫동안 풀리지 않던 문제가 해결됐다면, P=NP도 증명되는 것 아닐까? 그러면 암호가 전부 깨지는 걸까?”

그 우려를 이해하려면 세 가지를 나누어 봐야 합니다. P=NP가 무엇을 주장하는지, 그 주장이 참인지 거짓인지 밝혀지면 무엇이 달라지는지, 참일 때 실제로 얼마나 쓸 만한 알고리즘을 얻게 되는지입니다.

2026년 11월 22일 확인한 클레이 수학연구소의 공식 페이지에서 P 대 NP 문제는 여전히 미해결(Unsolved)로 표시되어 있습니다. 아래는 이미 P=NP가 증명됐다는 뉴스가 아니라, 앞으로 그런 증명이 나온다면 무엇을 뜻하는지 설명하는 글입니다. 리만 가설의 증명이 P=NP를 함께 증명하는 것도 아닙니다. 공식 문제 소개

먼저 질문에 대한 짧은 답을 두겠습니다.

“P=NP인가요?” 증명이 말하는 것 그 자체로 말하지 않는 것
Y: P=NP가 참 짧은 답의 후보를 효율적으로 확인할 수 있는 모든 NP 문제를, 이론상 효율적으로 판정하는 알고리즘이 존재합니다. 내일 모든 프로그램과 암호가 곧바로 바뀐다는 뜻은 아닙니다. 실제 알고리즘의 속도와 구현을 봐야 합니다.
N: P≠NP가 참 NP 문제 중에는 어떤 다항 시간 알고리즘으로도 모든 입력을 해결할 수 없는 문제가 존재합니다. 모든 사례가 어렵다거나, 모든 암호가 안전하다고 보장하지 않습니다.

여기서 N은 아직 P=NP의 증명을 못 찾았다는 뜻이 아니라, 반대로 P≠NP가 증명된 경우입니다.

‘이론상 효율적’이라는 말이 무엇인지는 잠시 뒤에 풉니다. 일단 핵심은 정답을 알아보는 능력과 정답을 찾아내는 능력이 같은 범위인가라는 질문입니다.

1. 숫자 카드로 ‘찾기’와 ‘확인하기’를 나눠 봅시다

다음 카드가 한 장씩 있다고 해 보겠습니다.

3, 5, 8, 12, 14, 19

이 중 몇 장을 골라 합을 27로 만들 수 있을까요? 카드를 중복해서 쓸 수는 없습니다. 처음에는 이것저것 더해 보아야 할 수 있습니다. 그런데 누군가 “8과 19를 골라요”라고 알려주면, 확인은 간단합니다. 두 카드가 실제로 있는지 보고 8+19=27인지 더하면 됩니다.

여섯 숫자 카드에서 합 27을 만드는 조합을 찾는 일과 주어진 8과 19를 확인하는 일을 구분한 도식

같은 카드 문제에서도 조합을 찾아내는 일과 주어진 조합을 확인하는 일은 다릅니다. 필자 작성·설명용 예시, 검증으로 NP를 정의하는 배경: Cook의 공식 해설.

이 작은 예시는 어렵지 않습니다. 하지만 카드가 수백 장으로 늘고 숫자도 커지면 이야기가 달라집니다. 각 카드를 넣거나 빼는 모든 조합을 시험하는 방법은 카드 수가 하나 늘 때마다 경우의 수가 두 배가 됩니다.

카드 수 넣거나 빼는 모든 조합 수
10장 1,024
20장 1,048,576
40장 1,099,511,627,776

이 숫자는 단순히 모든 조합을 열거했을 때의 수입니다. 이만큼 많은 조합이 있다는 사실만으로, 더 영리한 알고리즘이 없다고 증명되지는 않습니다. ‘지금 떠오르는 방법은 느리다’와 ‘어떤 방법을 써도 빠르게 풀 수 없다’는 다른 주장입니다. P 대 NP의 어려움은 바로 그 사이에 있습니다.

2. P와 NP는 무엇을 나누는 이름일까요

P는 문제의 크기가 커져도, 계산 단계 수를 입력 길이의 일정한 거듭제곱으로 제한할 수 있는 알고리즘이 존재하는 판정 문제들의 모음입니다. 판정 문제는 “조건을 만족하는 답이 있나요?”처럼 예·아니오로 답하는 문제입니다.

NP는 ‘예’라는 답이 맞다는 것을 보여 주는 길이가 적당히 제한된 증거가 있고, 그 증거를 입력 길이에 대한 다항 시간 안에 검사할 수 있는 판정 문제들의 모음입니다. 앞의 카드 문제에서는 선택한 카드 목록이 증거입니다. Cook의 정의, PDF 1–2쪽

말을 줄이면 P는 ‘효율적으로 판정할 수 있는 문제’, NP는 ‘예라는 답의 증거를 효율적으로 검사할 수 있는 문제’입니다. NP는 Non-Polynomial의 약자가 아닙니다. ‘빠르게 못 푸는 문제’라고 정의한 집합도 아닙니다. 원래 이름은 Nondeterministic Polynomial Time입니다.

P에 속하면 NP에도 속합니다. 스스로 효율적으로 답을 구할 수 있다면, 남이 가져온 증거에 기대지 않고도 판정할 수 있기 때문입니다. 아직 모르는 것은 그 반대입니다. NP에 있는 문제도 전부 P에 들어갈까요? MIT 강의 14

‘확인이 쉽다’는 말도 범위를 조심해야 합니다. NP의 정의는 ‘예’인 경우의 짧은 증거를 말합니다. 예컨대 합 27을 만드는 카드가 있으면 목록을 보여 주면 됩니다. 그런 카드 조합이 없다는 것을 짧게 증명할 방법까지 모든 NP 문제에 주어지는 것은 아닙니다.

여기서 ‘빠르다’와 ‘입력 길이’의 정확한 뜻

입력 길이를 n이라고 할 때 n²이나 n³ 같은 고정 차수의 식으로 계산량을 제한하는 것을 다항 시간이라고 합니다. 2ⁿ처럼 n이 조금만 늘어도 배씩 커지는 계산과 구분하기 위한 기준입니다.

중요한 것은 숫자의 값 자체보다 그 숫자를 적는 데 필요한 길이입니다. 예를 들어 1,000,000이라는 값은 십진수로 일곱 자리입니다. 계산을 백만 번 한다고 해서 일곱 자리 입력의 길이에 비례하는 계산이라고 말할 수는 없습니다.

다항 시간은 알고리즘을 분류하는 수학적 기준입니다. 매우 큰 고정 차수나 상수가 붙으면 실제 컴퓨터에서는 감당하기 어려울 수도 있습니다. 이 차이는 P=NP가 참일 때의 영향을 읽는 데 중요합니다. Cook 공식 해설, Aaronson §1.2.1

3. 왜 한 문제를 풀면 수많은 문제가 함께 움직일까요

NP 안에는 NP-완전(NP-complete)이라고 부르는 문제들이 있습니다. 두 가지 조건을 만족합니다. 그 문제 자체가 NP에 속하고, NP의 다른 모든 문제를 효율적으로 이 문제의 형태로 바꿀 수 있어야 합니다.

이를 ‘번역’에 비유할 수 있습니다. 서로 다른 질문들을 같은 형식으로 바꾸되, 원래 답이 예인지 아니오인지도 보존하는 것입니다. 번역 과정도 효율적이어야 합니다. 변환에 이미 천문학적인 시간이 든다면 빠른 해결로 이어지지 않기 때문입니다. MIT 강의 15

대표적인 문제가 SAT, 논리식 만족 가능성 문제입니다. 여러 참·거짓 조건을 전부 만족시키는 값의 배치가 있는지 묻습니다. Cook–Levin 정리는 SAT가 NP-완전임을 보입니다. 그래서 SAT를 모든 입력에 대해 다항 시간에 푸는 알고리즘 하나를 얻으면, 다른 모든 NP 문제도 효율적으로 변환한 뒤 풀 수 있습니다. 이것이 P=NP가 됩니다. MIT 강의 16

다만 “이번 시간표는 금방 짰다”, “실제 데이터 대부분에서 SAT가 빨리 풀린다”는 결과로는 충분하지 않습니다. 문제 크기가 커져도 모든 입력을 처리하는 시간 보장이 필요합니다. 특정 사례의 성공과 문제 전체에 대한 증명은 다릅니다.

4. N이라면: P≠NP는 무엇을 밝혀낼까요

P≠NP가 증명되면, 빠르게 확인할 수 있다고 해서 모두 빠르게 풀 수 있는 것은 아니다라는 경계가 확정됩니다. 지금까지 알고리즘을 잘 못 찾아서 어려웠던 것인지, 다항 시간 해결 자체가 불가능한 문제인지에 대한 근본적인 답입니다.

특히 NP-완전 문제는 P에 들어가지 못합니다. 어느 하나라도 들어가면 다른 모든 NP 문제도 P로 옮겨져 P=NP가 되기 때문입니다. 이 의미에서 NP-완전성은 하나의 문제에 대한 난도를 넓은 문제군과 연결합니다. MIT 강의 15

하지만 N의 의미를 지나치게 넓히면 안 됩니다.

  • 모든 입력이 어렵다는 뜻은 아닙니다. 어떤 시간표나 작은 퍼즐은 계속 쉽게 풀립니다.
  • 반드시 지수 시간이 필요하다는 증명도 아닙니다. ‘다항 시간은 불가능’과 ‘이 특정한 지수 시간보다 더 빠를 수 없음’은 다른 강도의 주장입니다.
  • 근사나 특정 조건의 빠른 해법을 막지 않습니다. 최적해가 아닌 충분히 좋은 답, 제한된 입력 구조를 이용하는 방법은 여전히 의미가 있습니다.
  • RSA 같은 개별 암호의 안전성을 보장하지 않습니다. 암호에 필요한 어려움은 더 구체적입니다.

마지막 항목이 중요합니다. P≠NP는 어떤 문제군의 최악의 입력까지 전부 빠르게 해결하는 것이 불가능하다는 말입니다. 암호에는 우리가 실제로 생성해 쓰는 키와 공격 상황에서 어려움이 유지되는지도 필요합니다. 최악의 경우의 어려움만으로 평균적인 경우의 어려움과 암호 안전성이 자동으로 따라오지는 않습니다. Bogdanov·Trevisan의 평균 경우 복잡도 해설

5. Y라면: ‘찾기’의 범위가 ‘확인하기’의 범위로 넓어집니다

P=NP가 참으로 증명되면, NP의 모든 판정 문제에 다항 시간 알고리즘이 존재하게 됩니다. 주목할 점은 한 퍼즐의 풀이법이 추가되는 것에 그치지 않는다는 것입니다. 짧은 증거를 효율적으로 확인할 수 있는 문제 전체가 효율적인 판정의 범위에 들어옵니다.

‘있나요?’라는 판정만 빠르게 한다면 실제 답도 구할 수 있을까요? SAT에서는 질문을 여러 번 바꾸어 물으면 됩니다. 첫 번째 변수를 참으로 고정해도 답이 있는지 확인합니다. 있다면 그대로 두고, 없다면 거짓으로 고정합니다. 다음 변수에도 반복하면 조건을 만족하는 배치 자체를 찾습니다.

즉, 한 번의 호출이 정답 전체를 내놓지 않아도, 빠른 판정기를 입력 길이에 비례한 횟수만큼 사용해 답을 구성할 수 있습니다. 이런 판정과 탐색의 연결 때문에 P=NP의 파급이 큽니다. Aaronson §2.2.1

P=NP의 Y와 P≠NP의 N에서 P와 NP의 포함 관계를 비교한 도식

Y이면 P와 NP가 같은 집합이고, N이면 P는 NP의 일부입니다. 오른쪽에서 NP-완전 문제를 P 바깥에 놓은 것은 P≠NP를 가정한 그림입니다. 필자 작성, 정의와 NP-완전성: MIT 강의 14–15.

다만 이 결론의 다항 시간을 곧바로 몇 초 안에로 바꾸어 읽으면 안 됩니다. 여기서 Y의 의미는 다시 세 단계로 갈립니다.

알게 된 것 의미 다음으로 확인할 것
P=NP라는 존재 증명 다항 시간 알고리즘이 존재한다는 이론적 경계가 바뀝니다. 알고리즘을 구체적으로 얻을 수 있는가?
구체적 알고리즘도 제시 실제 계산 절차를 연구할 수 있습니다. 차수·상수·메모리가 감당 가능한가?
실제 규모에서도 빠른 알고리즘 산업과 암호에 직접 적용할 가능성이 커집니다. 문제를 변환하는 비용과 구현 조건까지 포함해 빠른가?

예를 들어 n의 1,000제곱에 비례하는 알고리즘도 형식적으로는 다항 시간입니다. 하지만 이 사실만으로 실용적이라고 할 수는 없습니다. 존재의 증명이 즉시 쓸 수 있는 좋은 구현을 주지 않는 가능성도 구별해야 합니다. 이것은 Y의 중요성을 없애는 예외가 아니라, 수학적 충격과 실제 변화의 속도를 따로 보아야 하는 이유입니다. Aaronson §1.2.1·§1.2.7

6. Y이고 실제로도 빠르다면: 좋은 쪽의 변화

가장 큰 기대는 무수한 후보 중 조건에 맞는 것을 찾는 작업입니다. 다음은 그런 적용 가능성을 설명하는 사례이며, P=NP로 이미 달성한 성과가 아닙니다.

분야 컴퓨터에 줄 수 있는 질문 기대할 수 있는 변화
시간표·근무표 인력·시간·자격 조건을 모두 만족하는 배치가 있는가? 가능한 배치를 찾고 조건을 바꾸어 비교하는 작업
물류·경로 정해진 비용 이하로 배송 조건을 만족하는 경로가 있는가? 비용 한도를 조절하며 더 나은 경로를 찾는 작업
회로·설계 주어진 유한한 시험 입력들에서 원하는 출력과 자원 조건을 만족하는 회로가 있는가? 설계 후보의 탐색 범위 확대
형식 증명 정해진 길이 안에, 검사 규칙을 만족하는 증명이 있는가? 길이가 제한된 증명을 찾는 작업의 가속

이 표의 공통 조건은 입력을 유한한 문제로 표현하고, 답의 크기를 제한하고, 조건 충족 여부를 효율적으로 검사할 수 있어야 한다는 것입니다. 모든 현실 문제가 이 틀에 저절로 들어가는 것은 아닙니다. 현실을 어떤 조건과 숫자로 표현할지 정하는 일도 남습니다. Cook의 NP 정의와 NP-완전성

증명 찾기도 마찬가지입니다. 특정 형식 체계에서 길이가 L 이하인 증명을 찾아 달라는 문제와, 모든 수학적 참·거짓을 무조건 판별하는 기계는 다릅니다. 필요한 증명이 너무 길거나, 그 체계에서 증명할 수 없다면 P=NP만으로 해결되지 않습니다. 또 ‘모두가 감동하는 소설’처럼 좋은 답인지 판정하는 규칙 자체가 명확하지 않은 목표도 그대로 해결된다고 할 수 없습니다. Aaronson §1.1

7. Y일 때 왜 암호 걱정이 나올까요

많은 암호는 정해진 방향으로 계산하기는 쉽지만, 비밀을 모른 채 거꾸로 되돌리기는 어렵다는 성질에 기대고 있습니다. 쉬운 예로 7×11=77은 바로 계산하지만, 아주 큰 수의 숨은 소인수를 찾는 일은 별개의 계산입니다.

이 차이는 소수의 분포를 다루는 리만 가설과도 구별해야 합니다. 소수가 얼마나 있는지 잘 추정하는 것과, 특정 합성수의 인수를 빠르게 찾는 것은 같은 작업이 아닙니다. 반면 P=NP는 확인 가능한 해답을 찾는 문제 전체에 관한 주장이라 영향 범위가 훨씬 넓습니다.

암호 문헌에서 중요한 개념은 일방향 함수입니다. 앞으로 계산하기는 효율적이지만, 무작위 입력에서 나온 결과를 거꾸로 되돌리는 것은 효율적인 공격으로 어렵기를 요구합니다. P=NP라면 표준적인 복잡도 기반 일방향 함수는 존재할 수 없습니다. 거꾸로 대응하는 입력을 찾는 일을 효율적인 검증과 탐색의 문제로 다룰 수 있기 때문입니다. Bogdanov·Trevisan의 암호와 평균 경우 복잡도 설명

그래서 우려에는 근거가 있습니다. 특히 실제 키 크기에서도 빠른 방법을 얻으면, 비밀키를 찾거나 유효한 서명을 만들어내기 어렵다는 계산상의 장벽에 기대는 보안 체계가 큰 타격을 받을 수 있습니다. 기밀 보호뿐 아니라 ‘이 메시지를 누가 승인했는가’를 확인하는 전자서명의 신뢰도도 문제입니다.

그렇다고 “P=NP 논문이 올라온 순간 모든 계좌가 열리고 모든 암호문이 읽힌다”는 결론은 아닙니다. 실제 공격에는 해당 문제로의 변환, 입력 규모, 실행 시간과 메모리 등 구체적인 조건이 걸립니다. 암호가 기대는 이론적 토대에 대한 충격과 특정 시스템을 실제로 공격할 수 있음은 나누어 보아야 합니다.

컴퓨터가 풀기 어렵다는 가정에 의존하지 않는 보안 방식도 구분해야 합니다. 예를 들어 일회용 패드의 정보이론적 비밀성은 메시지 길이 이상의 무작위 비밀키를 미리 공유하고, 안전하게 보관하며, 재사용하지 않는 등의 조건에 기댑니다. P=NP가 그런 비밀성을 자동으로 없애지는 않습니다. 대신 키 공유와 관리라는 제약이 남습니다. Aaronson §1.1

8. 양자내성 암호라면 P=NP에도 안전할까요

양자 컴퓨터에 대한 방어와 P=NP에 대한 방어는 같은 조건이 아닙니다.

양자내성 암호는 충분히 강한 양자 컴퓨터의 공격까지 고려해 설계하는 계산 기반 암호입니다. NIST는 격자와 해시 등 여러 수학적 기반을 검토하고 표준화해 왔습니다. 이 말이 모든 고전적 알고리즘의 획기적인 발견이나 P=NP의 결과까지 무조건 막는다는 뜻은 아닙니다. NIST의 양자내성 암호 설명

또한 양자 컴퓨터로 소인수분해를 빠르게 할 수 있다는 사실만으로 P=NP가 되는 것도 아닙니다. P는 고전적인 결정적 계산 모델의 다항 시간 문제를 말합니다. 어떤 계산 모델에서 무엇이 빨라지는지, 어느 문제까지 해결하는지 구분해야 합니다.

따라서 ‘양자내성’이라는 이름을 ‘어떤 수학적 발견에도 안전함’으로 읽으면 안 됩니다. P=NP에 대한 실용적인 알고리즘이 등장한다면, 어떤 계산이 어렵다는 가정에 기대고 있는지를 훨씬 넓게 다시 살펴야 합니다.

9. 풀린다는 소식을 들으면 무엇부터 확인하면 될까요

P 대 NP의 해결 소식에서는 먼저 결론의 방향을 봐야 합니다. P=NP라는 주장인지, P≠NP라는 주장인지부터 다릅니다. 많은 사례에서 빠른 성능을 냈다는 실험과, 모든 입력 크기를 포괄하는 복잡도 증명도 구별해야 합니다.

Y라는 주장이라면 다음으로 알고리즘이 제시되었는지, 최악의 경우에도 다항 시간이라는 논증이 맞는지, 실제 크기에서도 빠른지를 봅니다. ‘효율적’이라는 한 단어에 서로 다른 단계가 섞이기 쉽습니다. N이라면 알려진 몇몇 알고리즘의 실패만 보인 것인지, 가능한 모든 다항 시간 알고리즘을 배제한 것인지가 핵심입니다.

흔히 섞이는 말 정확히 구분할 내용
리만 가설이 증명됐으니 P=NP도 참이다 한 문제의 해결은 다른 명제의 참·거짓을 결정하지 않습니다.
NP니까 느리다 P도 NP에 포함됩니다. NP는 검증 가능성을 말합니다.
Y면 컴퓨터가 모든 문제를 푼다 NP의 범위, 입력과 답의 크기, 검증 조건이 있습니다.
N이면 기존 암호는 전부 안전하다 개별 문제와 실제 입력 분포에서의 어려움은 별도입니다.
Y면 내일 당장 모든 암호가 깨진다 실용적인 알고리즘과 구체적인 공격 가능성까지 확인해야 합니다.

Y가 바꾸는 것은 ‘답을 찾을 수 있는 범위’입니다

P=NP가 참이라는 증명은, 효율적으로 확인할 수 있는 짧은 해답을 효율적으로 찾는 방향으로 계산의 경계를 바꿉니다. 이것이 실제로도 빠른 알고리즘으로 이어진다면, 탐색과 설계에는 큰 기회가 되고 계산의 어려움에 기대던 보안에는 큰 위험이 됩니다.

P≠NP라는 증명은 반대로, 확인과 해결 사이에 본질적인 간격이 존재함을 확정합니다. 다만 그 간격이 모든 사례와 모든 암호를 한꺼번에 설명해 주지는 않습니다.

이 문제의 무게는 “컴퓨터가 얼마나 똑똑해질까”에만 있지 않습니다. 무엇을 확인할 수 있다는 사실이, 그것을 찾아낼 수 있다는 사실까지 보장하는가. Y와 N 어느 쪽이 밝혀지든, 계산으로 할 수 있는 일의 범위를 이해하는 데 근본적인 변화입니다.