수학 개념 지도
논리와 계산(Logic and computation)

P 대 NP 문제(P versus NP problem)

답이 주어지면 빠르게 확인할 수 있는 문제(NP)는 모두 빠르게 풀 수도 있는가(P)? 컴퓨터 과학의 가장 유명한 미해결 문제.

P=?NP\mathrm{P} \overset{?}{=} \mathrm{NP}
먼저 보면 좋은 개념튜링 기계멱집합

누가 스도쿠⁠(sudoku)⁠의 답을 건네주면 맞는지 확인하는 데는 1분이면 충분합니다. 빈 판에서 답을 찾는 것은 훨씬 어렵습니다. 답을 확인하기는 쉬운데 찾기는 어려워 보이는 문제가 세상에는 아주 많습니다. NP는 답이 '예'일 때 그 근거(증명서, 스도쿠라면 채운 판)가 주어지면 그것이 맞는지를 빠르게 확인할 수 있는 예/아니오 문제들의 모임이고, P는 처음부터 빠르게 풀 수 있는 예/아니오 문제들의 모임입니다. 흔히 NP를 '다항식⁠(polynomial)⁠이 아닌(non-polynomial)'의 줄임으로 알지만, '비결정적 다항 시간(nondeterministic polynomial time)'의 줄임입니다. 갈림길마다 옳은 쪽을 알아서 고르는 가상의 기계라면 다항 시간에 풀 수 있다는 뜻이고, 이것은 증명서를 받아 확인하는 것과 같은 말입니다. '빠르게'는 입력 크기 n의 다항식만큼의 걸음, 예를 들어 n2n^2이나 n3n^3걸음 안에 끝난다는 뜻입니다. 이런 성장 속도⁠(velocity)⁠를 상수배를 무시하고 O(n2)O(n^2)처럼 적는 것이 점근 표기법⁠(asymptotic notation)⁠입니다. 걸음은 튜링 기계⁠(Turing machine)⁠의 걸음으로 재지만, 어떤 합리적인 계산 모형을 써도 결론은 같습니다. 빠르게 풀 수 있으면 확인도 빠르니 P는 NP 안에 들어 있습니다. 문제는 거꾸로입니다. 확인하기 쉬운 문제는 모두 풀기도 쉬울까요?

대표적인 NP 문제 하나가 부분집합 합 문제입니다. 수 몇 개 가운데 몇 개를 골라 합이 정확히 T가 되게 할 수 있을까요? 수를 눌러 골라 보세요. 고른 답이 맞는지는 덧셈 몇 번으로 바로 확인됩니다. 수의 개수는 개입니다. 모든 부분집합을 차례로 시도 새 문제

노랗게 칠한 수가 내가 고른 부분집합⁠(subset)⁠, 분홍 테두리는 무차별 탐색이 지금 시도하는 부분집합입니다.

답을 찾으려면 부분집합을 하나씩 시도할 수 있습니다. n개의 수에서 만들 수 있는 부분집합은 멱집합⁠(power set)⁠의 크기인 2n2^n개입니다. 탐색은 부분집합에 0부터 2n−12^n - 1까지의 이진수 번호를 붙여 차례로 셉니다. n이 하나 늘 때마다 시도할 것이 두 배가 됩니다. 요령을 부리면 조금 줄일 수는 있습니다. 수를 두 무리로 나눠 무리마다 가능한 합을 모두 구해 정렬한 뒤 더해서 T가 되는 짝을 찾으면(1974년 호로위츠와 사니의 방법) 시도가 2n/22^{n/2} 정도로 줄어듭니다. 또 T가 작으면 '0부터 T까지 각 합을 만들 수 있는가'를 표로 채워 가는 동적 계획법⁠(dynamic programming)⁠이 n × T걸음 정도로 풉니다. 하지만 T가 100자리 수라면 이 표는 쓸모가 없습니다. 걸음 수가 T의 자릿수에 대해 지수적으로 늘기 때문입니다. 수가 크고 많을 때 다항 시간에 푸는 방법은 알려져 있지 않습니다.

세로축은 로그 눈금이라 1만큼 올라갈 때마다 10배이고, 가로선은 10⁵배 간격입니다. 두 점선은 1초와 1년 동안 할 수 있는 걸음 수(1초에 10억 걸음 기준)입니다.

n = 일 때

1971년 미국 태생의 캐나다 컴퓨터 과학자 스티븐 쿡은 불 대수⁠(Boolean algebra)⁠ 식을 참으로 만드는 입력이 있는지 묻는 충족 가능성 문제(SAT)가 'NP 완전⁠(NP-complete)⁠'임을 보였습니다. NP 완전이란 NP에 속하면서, 다른 모든 NP 문제를 다항 시간 안에 그 문제로 번역할 수 있다는 뜻입니다. 예를 들어 '이 지도를 세 가지 색으로 칠할 수 있는가'는 '나라 A는 빨강이다', '이웃한 두 나라는 색이 다르다' 같은 조건을 AND·OR·NOT으로 엮은 식 하나로 바꿀 수 있고, 그 식이 참이 될 수 있는지가 원래 질문의 답입니다. 그러니 SAT 하나만 빠르게 풀면 모든 NP 문제가 빠르게 풀립니다. 소련의 레오니트 레빈도 따로 같은 결과에 이르러 1973년에 발표했고, 1972년 미국의 리처드 카프가 21개의 자연스러운 문제가 NP 완전임을 보인 뒤로 수천 개가 더해졌습니다. 부분집합 합, 모든 꼭짓점⁠(vertex)⁠을 한 번씩 지나는 해밀턴 경로⁠(Hamiltonian path)⁠, 그래프를 세 가지 색으로 칠하기(평면 그래프⁠(planar graph)⁠로 좁혀도 NP 완전이라, 네 가지 색이면 언제나 된다는 4색 정리⁠(four color theorem)⁠와 대조적입니다), 외판원 문제⁠(traveling salesman problem)⁠의 판정판이 모두 그렇습니다. 외판원 문제는 여러 도시를 한 번씩 들르고 돌아오는 가장 짧은 길을 찾는 문제이고, 판정판은 '길이 L 이하인 길이 있는가'를 묻습니다. 반면 모든 변을 한 번씩 지나는 오일러 경로⁠(Euler path)⁠는 꼭짓점마다 붙은 변의 개수(차수)를 세어 홀수인 꼭짓점이 0개나 2개인지만 보면 되고(그래프가 이어져 있을 때), 최단 경로⁠(shortest path)⁠도 길이가 음수가 아니면 다익스트라 알고리즘(에츠허르 데이크스트라, 1959)으로 빠르게 풉니다. 모양이 비슷해 보이는 문제가 쉬움과 어려움으로 갈립니다.

큰 수를 소인수분해⁠(prime factorization)⁠하는 문제도 'N에 k보다 작은 인수가 있는가'라는 예/아니오 꼴로 바꾸면 NP에 속합니다. 인수를 건네받으면 나눠 보면 되기 때문입니다. 그러나 NP 완전인지는 모르고, 다항 시간 방법이 알려져 있지 않다는 사실에 RSA 암호가 기대고 있습니다. 디피–헬먼 키 교환⁠(Diffie–Hellman key exchange)⁠이 기대는 이산 로그⁠(discrete logarithm)⁠ 문제, 곧 gx≡h(modp)g^x \equiv h \pmod p에서 g, h, p를 알 때 x를 찾는 문제도 마찬가지입니다. P = NP라면 이런 문제가 모두 다항 시간에 풀리므로 이런 암호가 원리적으로 무너집니다. 거꾸로 P ≠ NP가 증명되어도 소인수분해가 어렵다는 보장은 되지 않습니다. 소인수분해가 NP 완전이라는 증명이 없기 때문입니다. 반면 수가 소수⁠(prime number)⁠인지 판정하는 문제는 2002년 인도의 아그라왈·카얄·삭세나가 내놓은 AKS 알고리즘⁠(algorithm)⁠으로 P에 속함이 증명되었습니다(소수 판정⁠(primality test)⁠). 인수를 찾는 것과 소수인지 아는 것은 다른 문제입니다.

이어지는 곳. 2000년 클레이 수학연구소는 이 문제를 상금 100만 달러의 밀레니엄 문제 가운데 하나로 꼽았습니다. 대부분의 연구자는 P ≠ NP라고 믿지만 증명은 없습니다. 정지 문제⁠(halting problem)⁠는 아무리 오래 걸려도 풀 수 없는 문제이고, P 대 NP는 풀 수 있는 문제 안에서 빠르기를 묻는 문제입니다. 무엇을 계산할 수 있는가를 묻는 계산 가능성⁠(computability)⁠ 이론 다음 층이, 문제를 푸는 데 드는 시간과 기억 공간을 재어 문제들을 분류하는 계산 복잡도 이론입니다.

관련 인물윌리엄 로언 해밀턴안드레이 콜모고로프존 폰 노이만쿠르트 괴델앨런 튜링조지 댄치그에츠허르 데이크스트라도널드 크누스
관련된 시대와 장소프린스턴 고등연구소와 로스앨러모스
이 개념이 나오는 큰 생각쌍대성가장 좋은 것 고르기

이 개념이 나오는 긴 글

정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 계산언어학 말을 세는 기계 문법은 규칙일까, 확률일까? 파니니의 문법에서 촘스키의 위계, 섀넌의 영어 엔트로피, 오늘날의 언어 모델까지. 매칭과 흐름 짝을 찾는 알고리즘 의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 냉전의 철도 지도에서 노벨 경제학상까지 이어진다. 램지 이론 완전한 무질서는 없다 여섯 명이 모이면 서로 아는 세 사람이나 서로 모르는 세 사람이 반드시 있다. 충분히 크면 어디에나 질서가 숨어 있다는 이론과, 그것을 동전 던지기로 증명한 에르되시. 알고리즘과 복잡도 줄 세우기의 한계 카드 천 장을 가장 빨리 줄 세우는 방법은? 인구조사의 천공 카드에서 퀵정렬까지, 그리고 어떤 방법도 넘을 수 없는 n log n의 벽. 게임과 증명 이기는 쪽이 존재한다 "이 판은 백이 이겼다"는 흑이 어떻게 두든 백에게 답이 있다는 말이다. 체스의 체르멜로 정리, ε–δ, 님의 이진법, 폰 노이만의 최소최대와 쌍대성, 논리의 한계를 재는 게임, 끝나지 않는 게임과 선택공리, 대화로 읽는 증명, 겨루며 배우는 신경망까지. 수학의 참을 두 사람의 게임으로 읽는다. 불가능성 정리 불가능의 증명 각의 삼등분, 5차방정식의 근의 공식, 모든 파일을 줄이는 압축, 멈춤을 판정하는 프로그램, 공정한 투표 규칙. 없다는 것은 어떻게 증명할까? 서로 먼 분야의 불가능성 증명들은 거의 모두 불변량, 세기, 대각선이라는 세 가지 무기 가운데 하나를 쓴다. 반환과 동적 계획법 같은 계산, 다른 덧셈 가장 짧은 길, 길의 가짓수, 가장 그럴듯한 해석, 갈 수 있는지 없는지. 따로 태어난 알고리즘들이 사실은 한 계산이고, 달라지는 것은 더하기와 곱하기 자리에 무엇을 넣느냐뿐이다. 그렇게 바꿔 넣어도 되는 까닭은 분배법칙 하나다.

이 개념을 언급하는 페이지

  • RSA 암호

    … 어려워 보입니다. 이처럼 답을 빨리 확인할 수 있는 문제가 모두 빨리 풀 수도 있는 문제인지 묻는 것이P 대 NP 문제입니다. 다만 P ≠ NP가 증명되더라도 소인수분해가 어렵다는 결론은 곧바로 나오지 않습니다. 소인수분해는 …

  • 오일러 경로

    … 데서 붙은 이름입니다. 해밀턴 경로에는 차수의 홀짝 같은 간단한 판정법이 알려져 있지 않습니다. 이 문제는NP-완전문제입니다. 누가 길을 내놓으면 맞는지 확인하기는 쉽지만, 길을 빠르게 찾는 방법은 아무도 모르는 문제들이 …

  • 4색 정리

    … 확인하기는 쉽지만, 빠르게 칠하는 방법은 알려져 있지 않고, 이런 부류에서 가장 어려운 문제라는 뜻입니다(P 대 NP 문제). 컴퓨터가 증명을 도왔다는 사실은 '사람이 끝까지 읽을 수 없는 증명도 증명인가'라는 물음을 …

  • k-평균 군집

    … 더 나아질 수 없는 국소 최솟값입니다. 가장 좋은 나눔을 찾는 문제는 일반적으로 계산이 매우 어려운 문제(NP-난해)로 알려져 있어서, 실제로는 여러 번 무작위로 시작해 가장 좋은 답을 고르거나, 이미 고른 중심에서 먼 …

  • 불 대수

    … 진리표 2^n 줄을 다 보면 풀립니다. 입력 크기의 다항식만큼의 걸음으로 푸는 방법이 있느냐는 물음은P 대 NP 문제와 같은 물음입니다. SAT가 NP 완전이기 때문입니다. 게이트만 이은 회로는 기억이 없습니다. 출력을 …

  • 튜링 기계

    … 길이 n인 입력에 대략 n²에 비례하는 걸음이 듭니다. 알고리즘의 빠르기를 이런 걸음 수로 재는 것이P 대 NP 문제의 출발점입니다. 바쁜 비버 는 기호 0과 1만 쓰는 n상태 기계 가운데, 빈 테이프에서 출발해 언젠가 …

  • 정지 문제

    … 정지 문제를 풀어 버리기 때문입니다. 풀 수 있는 문제 안에서 '얼마나 빨리' 풀 수 있는지를 묻는 것이P 대 NP 문제입니다. 어떤 문자열을 출력하는 가장 짧은 프로그램의 길이, 곧 콜모고로프 복잡도도 계산할 수 …

  • 처치–튜링 논제

    … 어떤 문제가 '빨리'(다항식 걸음 안에) 풀리는지는 합리적인 모형 사이에서 달라지지 않고, 이것이P 대 NP 문제를 모형과 상관없이 물을 수 있는 이유입니다. 여기서 한 걸음 더 나아가 '물리적으로 만들 수 있는 모든 …

  • 촘스키 위계

    … 아니라 '얼마나 빨리 알아볼 수 있는가'도 물을 수 있고, 이렇게 계산에 드는 시간을 따지는 물음의 대표가P 대 NP 문제입니다. 가장 바깥 층의 기계인 튜링 기계와 같은 힘을 기계 대신 함수로 적은 것이 람다 계산입니다.

  • 정규 표현식

    … 문자열 aⁿbaⁿ을 알아봅니다. 그 대가로 속도를 보장할 수 없습니다. 되참조가 있는 패턴을 맞추는 일은NP 완전문제여서, 다항 시간 방법이 있다면 P = NP가 됩니다. 이어지는 곳. 뒤에 유닉스 운영체제를 함께 만든 …

  • 순열

    … 곧 답이 주어지면 확인하기는 쉬운 문제들 가운데 가장 어려운 축에 들기 때문에, 이 물음의 답은P 대 NP 문제의 답과 같습니다. 순서를 잊으면. 고른 k개의 순서를 무시하면 같은 k개로 만든 배열 k!개가 한 묶음이 …

  • 반 데르 바르던 정리

    … 답이 주어지면 확인하기 쉬운 문제를 언제나 크기의 다항식(n², n³ 같은) 정도의 시간에 풀 수 있느냐가P 대 NP 문제입니다.

  • 알고리즘

    … 논리⟧입니다. 답이 맞는지 확인하기는 쉬운데 빠른 알고리즘이 있는지조차 모르는 문제들을 둘러싼 큰 물음은P 대 NP 문제입니다. 알고리즘은 정보를 재는 잣대도 됩니다. 프로그래밍 언어를 하나 정해 두면, 어떤 문자열을 출력하는 …

  • 점근 표기법

    … 묶이는 알고리즘을 '빠르다'고 부르고, 그런 알고리즘으로 풀리는 예/아니오 문제들의 모임을 P라고 합니다(P 대 NP 문제). 정확한 뜻은 위의 식입니다. 어떤 상수 c와 문턱 n_0 이 있어서 그 뒤로는 f가 g의 c배를 넘지 …

  • 무작위 알고리즘

    … 곧 자릿수의 다항식만큼의 걸음에 하는 방법(AKS)을 찾아낸 것도 그 방향의 증거로 꼽힙니다. 이 물음은P 대 NP 문제와 나란히 계산 복잡도 이론의 큰 물음입니다.

  • 최소 신장 트리

    … 범주⟧가 바로 이 거리입니다. 모든 점을 한 번씩 들르고 돌아오는 가장 짧은 순회를 찾는 외판원 문제는NP-난해합니다. NP-완전 문제만큼 또는 그보다 어려워서, 빠른 풀이법이 알려져 있지 않다는 뜻입니다. 그래도 …

  • 홀의 정리

    … 딴판입니다. 행렬식은 가우스 소거법으로 빠르게 계산되지만, 퍼머넌트를 빠르게 계산하는 방법이 있다면P 대 NP 문제가 P = NP로 풀려 버린다는 것이 증명되어 있습니다(1979년 영국의 컴퓨터 과학자 레슬리 밸리언트). …

  • 최대 흐름 최소 절단 정리

    … 가장 싼 절단은 색이 크게 바뀌는 곳을 따라 지나갑니다. 반대로 건너는 변이 가장 많은 절단을 찾는 문제는NP-난해하다는 것, 곧 빠른 풀이법이 있다면 모든 NP-완전 문제가 빠르게 풀린다는 것이 알려져 있어, 최소와 …

  • 선형 계획법

    … 문제를 빠르게 풀 수 있게 되는 문제입니다. 그런 풀이법은 알려져 있지 않고, 없으리라고 널리 믿어집니다(P 대 NP 문제). 그림자 가격과 쌍대성. 밀가루를 kg으로 바꿔 보세요. 밀가루의 양에 따른 가장 큰 이익. 이 선의 …

  • 라틴 방진

    … 답을 확인하기는 쉽지만 찾는 빠른 방법은 알려져 있지 않은 문제들 가운데 가장 어려운 부류임을 보였습니다(P 대 NP 문제). 반면 몇 개의 가로줄을 빈칸 없이 채워 두었다면(각 세로줄에 겹침이 없게) 남은 줄은 언제나 채울 수 …

  • 결정 트리와 랜덤 포레스트

    … 질문 수가 가장 적은 결정 트리를 찾는 문제는, 1976년 하이아필과 리베스트가 NP-완전임을 보였습니다(P 대 NP). 탐욕의 한계를 보여 주는 예가 XOR입니다. 네 사분면에 노랑과 파랑이 엇갈려 있으면 어떤 첫 …

  • 게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색

    … 것은 증명되어 있으므로(시간 계층 정리), 일반화한 체스는 다항 시간에 풀 수 없습니다. 아직 답이 없는P 대 NP문제와 달리 이쪽은 증명된 사실입니다. 컴퓨터 체스의 설계도를 일찍 적은 사람으로는 섀넌과 튜링이 …

  • 단순 타입 람다 계산

    … 공간으로 풀리는 문제들의 부류로 NP를 포함하며, 그 안에서 가장 어려운 문제들과 같은 급이라는 뜻입니다(P 대 NP 문제참고). 이 문제는 직관주의 명제 논리에서 '이면'만 쓴 식이 증명되는지 묻는 문제와 같습니다. 둘, 이 …

  • 증명 보조기

    … 들어가는 증명의 뼈대는 대부분 사람이 적습니다. 답을 확인하기는 쉬운데 찾기는 어려워 보인다는 이 모양은P 대 NP 문제의 모양과도 닮았습니다. 또 검사를 통과한 증명이 보증하는 것은 '적어 넣은 형식 명제가 체계의 공리에서 …

  • 추론 모델과 테스트 시점 계산

    … 일은 몬테카를로 방법입니다. 답을 확인하기가 찾기보다 쉬운 문제에서 이 방법이 잘 듣는다는 점은P 대 NP문제의 직관과 닿아 있고, 가장 엄격한 채점기는 증명 보조기입니다. 계산량과 성능의 경험적 관계는 …

이 페이지가 가리키는 개념

다항식점근 표기법진법동적 계획법불 대수그래프4색 정리오일러 경로최단 경로에츠허르 데이크스트라소인수분해RSA 암호디피–헬먼 키 교환소수와 에라토스테네스의 체소수 판정정지 문제