P 대 NP 문제 — 정의 한글 번역

서문

P 대 NP 문제(P versus NP problem)는 이론 컴퓨터 과학의 주요 미해결 문제이다. 비형식적으로 말하면, 해(답)를 빠르게 검증할 수 있는 모든 문제가 또한 빠르게 풀릴 수도 있는지를 묻는 문제이다.

여기서 "빠르게"란 그 작업을 해결하는, 다항 시간에 실행되는 알고리즘이 존재한다는 뜻이다. (예컨대 지수 시간과 대비된다.) 즉 작업을 끝내는 데 걸리는 시간이 알고리즘 입력 크기에 대한 다항 함수로 위에서 유계라는 의미이다. 어떤 알고리즘이 다항 시간 안에 답할 수 있는 질문들의 일반적 부류를 "P" 또는 "클래스 P"라 한다. 어떤 질문들은 답을 빠르게 찾는 방법이 알려져 있지 않지만, 답이 주어지면 그 답을 빠르게 검증할 수는 있다. 이렇게 답을 다항 시간 안에 '검증'할 수 있는 질문들의 부류가 "NP"이며, 이는 "비결정론적 다항 시간(nondeterministic polynomial time)"의 약자이다.

P 대 NP 질문에 대한 답은, 다항 시간에 검증될 수 있는 문제가 다항 시간에 풀릴 수도 있는지를 결정하게 된다. 널리 믿어지는 바와 같이 만약 P ≠ NP 라면, NP 안에는 검증하기보다 계산하기가 더 어려운 문제들이 존재한다는 뜻이 된다. 그런 문제들은 다항 시간 안에 풀 수는 없지만, 답이 주어지면 다항 시간 안에 검증할 수는 있다.

이 문제는 컴퓨터 과학에서 가장 중요한 미해결 문제라고 불려 왔다. 계산 이론의 중요한 문제라는 점을 넘어, 어느 방향으로든 증명이 이루어지면 수학, 암호학, 알고리즘 연구, 인공지능, 게임 이론, 멀티미디어 처리, 철학, 경제학을 비롯한 수많은 분야에 심대한 영향을 미치게 된다. 이 문제는 클레이 수학연구소(Clay Mathematics Institute)가 선정한 7개의 밀레니엄 난제(Millennium Prize Problems) 중 하나이며, 각 문제에는 최초의 올바른 풀이에 대해 미화 100만 달러의 상금이 걸려 있다.

예시

다음의 예/아니오 문제를 생각해 보자. 크기 n² × n² 의 미완성 스도쿠 격자가 주어졌을 때, 모든 행과 열, 그리고 각 n × n 정사각형이 1부터 n² 까지의 정수를 모두 포함하게 되는 올바른 해가 적어도 하나 존재하는가? 후보 해가 주어져 있다면 이 일반화된 스도쿠 문제의 "예" 사례를 검증하는 일은 간단하다. 그러나 이 문제의 모든 사례에 대해 "예" 또는 "아니오"를 올바르게 답할 수 있는 다항 시간 알고리즘이 존재하는지는 알려져 있지 않다. 따라서 일반화된 스도쿠는 NP(빠르게 검증 가능)에 속하지만, P(빠르게 해결 가능)에 속하는지 여부는 알 수 없다. (일반화된 버전의 스도쿠를 고려해야 하는 이유는, 크기가 고정된 스도쿠는 가능한 격자의 수가 유한하기 때문이다. 이 경우 문제는 P에 속하는데, 표 조회(table lookup)만으로 답을 찾을 수 있기 때문이다.)

역사 — 정확한 진술

P 대 NP 문제의 정확한 진술은 1971년 스티븐 쿡(Stephen Cook)이 그의 기념비적 논문 "The complexity of theorem proving procedures"(정리 증명 절차의 복잡도)에서 도입하였고, 1973년 레오니트 레빈(Leonid Levin)이 독립적으로 도입하였다.

형식적 정의 — P 와 NP

결정 문제(decision problem)란 알파벳 Σ 위의 어떤 문자열 w 를 입력으로 받아 "예" 또는 "아니오"를 출력하는 문제이다. 길이 n 인 임의의 입력 문자열에 대해 많아야 c·n^k 단계 안에 올바른 답을 내는 알고리즘(예: 튜링 기계, 또는 메모리 제한이 없는 컴퓨터 프로그램)이 존재한다면 — 여기서 k 와 c 는 입력 문자열과 무관한 상수이다 — 그 문제는 다항 시간에 풀 수 있다고 말하며, 그 문제를 클래스 P 에 넣는다. 형식적으로 P 는 결정론적 다항 시간 튜링 기계가 판정할 수 있는 언어들의 집합이다. 여기서 결정론적 다항 시간 튜링 기계란 다음 두 조건을 만족하는 결정론적 튜링 기계 M 을 말한다.

1. M 은 모든 입력 w 에 대해 정지한다.
2. M 의 실행 단계 수가 입력 길이 n 에 대해 어떤 상수 k 에 대한 n^k 수준(빅오 표기)으로 유계이다.

(집합 표기를 사용한 정확한 수식 정의는 영어 원문 글의 원문을 참조.)

NP 는 전통적으로는 비결정론적 튜링 기계를 사용해 비슷한 방식으로 정의할 수 있다. 그러나 현대적 접근은 '인증서(certificate)'와 '검증기(verifier)' 개념을 사용한다. 형식적으로 NP 는 유한 알파벳을 가지며 다항 시간에 실행되는 검증기가 존재하는 언어들의 집합이다. 검증기는 다음과 같이 정의된다.

L 을 유한 알파벳 Σ 위의 언어라 하자. L 이 NP 에 속한다는 것과, 다음 두 조건을 만족하는 이진 관계 R(Σ 위 문자열 쌍들의 집합)과 양의 정수 k 가 존재한다는 것은 동치이다.

1. 모든 문자열 x 에 대해, "x 가 L 에 속한다"는 것과 "(x, y) 가 R 에 속하고 y 의 길이가 |x|^k 수준으로 유계인 문자열 y 가 존재한다"는 것이 동치이다.
2. 관계 R 을 부호화한 언어(x 와 y 를 구분자 # 로 이어 붙인 문자열들의 언어)를 결정론적 튜링 기계가 다항 시간에 판정할 수 있다.

이때 그 튜링 기계를 L 의 검증기라 부르고, (x, y) 가 R 에 속하게 되는 y 를 "x 가 L 에 속함의 인증서(certificate of membership)"라 부른다.

모든 검증기가 다항 시간이어야 하는 것은 아니다. 다만 L 이 NP 에 속하려면, 다항 시간에 실행되는 검증기가 적어도 하나 존재해야 한다.