참고문헌 카드

튜링 기계를 정의하고, 기계적 절차로는 풀 수 없는 문제가 있음을 대각선 논법으로 보인 논문이다. 「알고리즘」과 「계산 단계 수」를 수학의 대상으로 만든 출발점으로, 2-1 의 연표가 첫 항목으로 싣는다.

거의 모든 불 함수에 큰 회로가 필요함을 계수 논법으로 보인 논문이다. n 변수 불 함수는 거의 모두 Ω(2ⁿ/n) 개의 게이트가 필요하다는 결과로, 회로 복잡도의 출발점이다. 다만 그런 함수를 구체적으로 하나도 주지 않는다. 2-3 의 회로 하한 글이 인용한다.

게임 이론가 John Nash 가 암호 기계를 제안하며 NSA 에 보낸 편지로, 열쇠를 알아내는 계산량이 열쇠 길이에 대해 지수적으로 늘어난다는 추측이 적혀 있다. Nash 는 충분히 복잡한 암호라면 열쇠 계산의 평균 길이가 열쇠 길이에 지수적으로 는다고 추측하고, 그렇다면 사실상 깰 수 없는 암호를 설계할 수 있다고 썼다. Gödel 의 1956년 편지(godel-1956)보다 한 해 앞서 계산의 어려움을 다항 대 지수로 가른 기록으로 인용한다.

괴델이 폰 노이만에게, 증명을 찾는 일을 기계가 얼마나 빨리 해낼 수 있는지 물은 편지다. P 대 NP 문제가 정식화되기 15년 전에 같은 물음의 핵심을 짚은 사료다. 연결한 Hartmanis 의 글(코넬 대학교 기술 보고서)은 편지가 쓰인 배경과 핵심 대목의 번역을 싣고 있고, 편지 전문의 영문 번역은 sipser-1992 의 부록에 있다. 문제의 역사에 관심 있는 모든 독자에게 권한다.

1차 술어 논리의 증명 절차를 컴퓨터에서 돌리는 방법을 다룬 논문으로, 명제 논리 부분을 처리하는 Davis–Putnam 절차의 출전으로 인용된다. 초록은 당시의 증명 프로그램들이 명제 계산 단계에서 막혔다는 문제의식에서 출발한다. 충족 가능성 판정 알고리즘의 역사를 Cook 의 정리(1971)보다 앞에서부터 적으려는 글에 필요하다. 이어진 구현은 dll-1962.

외판원 문제를 n! 이 아니라 n² · 2ⁿ 정도의 시간에 푸는 동적 계획법의 출전으로 널리 인용된다. 전수 탐색보다는 훨씬 빠르지만 여전히 지수 시간이며, 일반 외판원 문제에서 이보다 본질적으로 빠른 정확한 알고리즘은 알려져 있지 않다고 인용된다. 「지수 시간 안에서의 개선」과 「다항 시간」을 구별해 설명하는 글에 맞다.

증명 절차를 실제 프로그램으로 짜서 돌려 본 경험을 적은 네 쪽짜리 글로, 변수에 값을 넣어 가며 되돌아가는 DPLL 탐색의 출전으로 널리 인용된다. 오늘날 SAT 풀이기의 뼈대인 「값 배정 · 단위 전파 · 되돌아가기」가 davis-putnam-1960 과 이 글에서 비롯했다고 알려져 있다. NP-완전 문제가 실제로는 자주 풀린다는 이야기의 뿌리를 인용하려는 글에 맞다.

덧셈과 곱셈처럼 단계 수가 자릿수의 다항식으로 한정되는 함수들을 따로 다루자고 제안해, 다항 시간이라는 기준의 뿌리가 된 글이다. Edmonds 의 1965년 논문과 함께 클래스 P 의 출발점으로 꼽힌다. 1-1 의 역사 글과 2-1 의 연표가 인용한다. 연결한 것은 Stephen Cook 의 누리집에 있는 사본이다.

계산에 드는 시간으로 문제를 분류하는 틀을 세우고 시간 위계 정리를 증명한 논문이다. 「계산 복잡도」라는 분야가 여기서 시작되었다. 대각선 논법으로 복잡도 종류를 가르는 방법의 뿌리를 보려는 독자에게 권한다. 미국수학회 누리집에 PDF 가 올라 있다.

그래프의 최대 매칭을 찾는 알고리즘을 내놓으면서, 수고가 다항식 정도로만 늘어나는 「좋은」 알고리즘이 있는지가 뜻있는 물음이라고 논한 논문이다. Cobham 의 글과 함께, 다항 시간을 「현실적으로 풀 수 있음」의 기준으로 삼는 생각의 출발점이다. 1-1 의 역사 글과 2-1 의 연표가 인용한다.

테이프가 여러 개인 튜링 기계를 두 테이프 기계로 로그 배의 비용만 치르고 흉내 낼 수 있음을 보인 논문이다. 이 결과로 시간 위계 정리의 조건이 지금의 꼴(f(n)·log f(n))로 다듬어졌다. 2-4 의 시간 위계 정리 글이 인용한다.

어떤 기계·프로그램·부호화를 쓰는지에 거의 기대지 않는 일반적인 틀로 계산의 복잡도를 다룬 논문이다. 아무리 빠른 프로그램을 잡아도 그보다 훨씬 빠른 프로그램이 또 있는 함수가 있다는 결과(가속 정리)가 여기서 나온다. 복잡도 이론이 P 대 NP 로 좁혀지기 전에 「계산의 어려움」을 어떻게 정의하려 했는지 보려는 독자에게 맞다.

두 n×n 행렬을 n³ 보다 적은, 대략 n^2.81 번의 산술 연산으로 곱할 수 있음을 보인 세 쪽짜리 논문으로 널리 인용된다. 당연해 보이던 방법이 최선이 아니었다는 대표 사례로, 「더 빠른 알고리즘이 없다」는 말은 하한을 증명하기 전에는 할 수 없다는 교훈과 함께 인용된다. 대수 복잡도 이론의 출발점이기도 하다.

비결정적 공간 s(n) 을 결정적 공간 s(n)² 으로 흉내 낼 수 있다는 Savitch 정리의 출전으로 널리 인용된다. 시간에서는 비결정성을 없애는 데 지수적 비용이 드는 방법밖에 모르는데 공간에서는 제곱이면 된다는 대비가 P 대 NP 를 설명할 때 자주 쓰인다. PSPACE = NPSPACE 의 근거를 인용하려는 글에 필요하다.

NP 의 모든 문제가 명제 논리식의 판정 문제로 환산됨을 보여 NP-완전 이론을 연 논문이다. 8쪽짜리 학회 논문으로, 다항 시간 환산의 개념과 오늘날 「SAT 는 NP-완전」이라 부르는 결과가 여기서 나온다. 용어와 표기(항진식 판정, 오라클을 쓰는 환산)가 지금과 달라서, 교과서로 개념을 익힌 뒤 원전을 확인하려는 독자에게 맞다. 연결한 것은 저자 누리집의 스캔본이다.

서로 달라 보이는 조합 문제 21개가 모두 NP-완전임을 환산의 사슬로 보인 논문이다. 쿡의 결과가 한 문제에 그치지 않고 조합 최적화 전반에 걸친 현상임을 드러내 NP-완전성을 널리 알렸다. 클릭·정점 덮개·해밀턴 순환·배낭 문제 등으로 가는 환산을 직접 보고 싶은 독자에게 좋다. 게시자(Springer) 페이지이며 본문 열람에는 구독이 필요할 수 있다.

제곱 연산이 있는 정규식의 동치 문제가 지수 공간을 요구함을 다룬 논문으로, 다항 위계가 처음 정의된 곳으로 널리 인용된다. NP 위에 양화사를 번갈아 쌓은 다항 위계는 「P = NP 이면 위계 전체가 P 로 무너진다」는 식으로 P 대 NP 의 귀결을 말할 때 쓰인다. 위계의 첫 출전을 밝혀 적으려는 글에 필요하다.

비결정적 시간에도 위계 정리가 성립함을 처음 증명한 논문이다. 따름 결과로 NP ≠ NEXP 가 나온다. 2-4 의 부분 결과 개관과 시간 위계 정리 글이 인용한다.

쿡과 독립적으로, 여러 탐색 문제가 그런 종류의 문제 전체만큼 어려운 「보편」 문제임을 밝힌 두 쪽짜리 논문이다. 소련에서 러시아어로 발표된, 쿡–레빈 정리의 또 한쪽 원전이다. 내용보다 역사적 맥락을 확인하려는 독자에게 권한다. 연결한 Math-Net.Ru 페이지에 서지 사항과 러시아어 원문 PDF 가 있다.

양화된 불 식의 참·거짓 판정 같은 문제가 다항 공간에 대해 완전함을 다룬 논문으로 널리 인용된다. NP-완전성 바로 위 단계인 PSPACE-완전성의 출발점으로 꼽힌다. P 와 PSPACE 조차 갈라 놓지 못했다는 사실을 설명하면서 PSPACE-완전 문제의 출전을 적으려는 글에 맞다.

유한 구조의 성질이 NP 에 속하는 것과 존재 2차 논리의 식으로 적히는 것이 같음을 보인 논문이다. 기계도 시간도 쓰지 않고 NP 를 논리의 표현력으로 특징지은 Fagin 의 정리의 원전이다. 1-1 의 「여러 얼굴」 글이 인용한다. 논문 본문을 열지 못해, 정리를 소개하는 위키백과 문서로 연결한다.

어떤 수가 소수라는 사실에도 자릿수의 다항식 길이인 짧은 증명서가 있음을 보인 논문이다. 합성수의 증명서(약수)는 자명하므로, 이로써 소수 판정은 NP 와 coNP 양쪽에 들게 되었다. 「NP ∩ coNP 에 있지만 P 인지 모르던 문제」의 고전적인 예로, 2004년에 P 임이 밝혀지기까지(aks-2004)의 역사를 적는 글에 필요하다.

P ≠ NP 라면 P 에도 속하지 않고 NP-완전도 아닌 NP 문제가 반드시 있음을 증명한 논문이다. NP-중간이라는 개념의 근거가 되는 정리의 원전이다. 복잡도 이론 교과서에서 래드너의 정리를 먼저 읽고 원문을 찾는 독자에게 맞다. ACM 디지털 도서관으로 연결된다.

P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.

전산학에 자연스럽게 나타나는 문제들 가운데 형식화된 집합론으로는 답할 수 없는 사례가 있음을 보인 글이다. 초록은 그 예로 P = NP 문제의 어떤 상대화된 판이 집합론에서 결정되지 않음을 든다. 「P 대 NP 가 공리계와 독립일 수 있는가」라는 물음의 가장 이른 문헌으로 인용한다. 상대화되지 않은 본래 문제가 독립이라는 뜻은 아니다.

비밀을 미리 나누지 않은 두 사람이 공개 통신만으로 안전하게 통신할 수 있다는 공개 키 암호의 생각을 내놓은 논문으로 널리 인용된다. 암호의 안전성을 「계산하기 어려운 문제」에 기대게 만든 출발점이다. P = NP 라면 이런 암호가 모두 깨진다는 설명의 근거로, P 대 NP 가 왜 실용적으로 중요한지 쓰는 글이 인용한다.

다항 위계의 형식적 정의가 나온 논문이다. NP 와 coNP 위에 한정 기호가 번갈아 나오는 문제를 층층이 쌓은 위계를 다룬다. 1-1 의 「여러 얼굴」 글이 인용한다. 게시자(Elsevier) 페이지로 연결된다.

삼각 부등식을 만족하는 외판원 문제에서 최적의 3/2 배를 넘지 않는 경로를 O(n³) 시간에 찾는 알고리즘을 내놓은 보고서다. NP-난해 문제도 「근사」로는 다항 시간에 다룰 수 있음을 보여 주는 가장 유명한 예다. 정식 학술지에 실리지 않은 채 수십 년 인용되다가 2022년에 재수록되었으므로 인용할 때 두 서지를 함께 적는 것이 좋다.

동전을 던지는 튜링 기계를 정의하고, 확률적 다항 시간에 인식되는 언어 클래스들을 정해 NP 와 견준 논문이다. BPP·RP·PP·ZPP 같은 확률적 클래스의 출전으로 인용된다. 「무작위성을 쓰면 NP 문제가 쉬워지는가」를 다루는 글이 정의의 근거로 삼는다.

알려진 NP-완전 집합이 모두 다항 시간 동형임을 보이고, 모든 NP-완전 집합이 그렇다면 P ≠ NP 임을 밝힌 논문이다. 「모든 NP-완전 집합은 서로 다항 시간 동형이다」라는 동형 추측의 출전이다. 추측이 참이면 희소한 NP-완전 집합이 없다는 귀결도 여기서 나온다. NP-완전 문제들의 구조에서 P ≠ NP 로 가려는 접근을 다루는 글에 필요하다.