Stephen  Cook  &  Leonid  Levin

 

컴퓨터를 만든 15 인의 과학자 : Dennis Shasha. Cathy Lazere 공저, 박영숙 옮김, 세종연구원, 1998 (원서 : Out of Their Minds : 1995)

훌륭한 해법은 찾아 내기 어렵다

그것을 풀어 낼 알고리즘은 없을 것이라고 하는 결코 변하지 않을 어떤 기본적인 발상, 바로 그 발상이 나의 마음을 끈다. - Stephen Cook 때로는 어떤 것이 불가능하다는 사실이 좋을 때도 있다. 난 누구도 내게 해 줄 수 없는 것이 많다는 데 행복을 느낀다. - Leonid Levin

 

스티븐 쿡 : 논리학과 서구의 전통 만족성 (satisfiability) 비다항식-완전 (NP-complete) 의 정의 (거의) 영구적인 토론 기계

레오니드 레빈 : 콜모고로프의 전통 콜모고로프 복잡성 쿡과 레빈-NP-완전 이후 커다란 문제

평균적으로 15 살쯤 되면 피타고라스 정리의 증명을 이해할 수 있지만, 그리스의 기하학자들이 그것을 발견하였을 때에는 신에게 제물을 태워 바쳤다. 수백만의 사람들이 베토벤의 9 번 교향곡 가운데 한 부분을 휘파람으로 불 수는 있지만, 그의 음악적 천재성을 갈망할 수 있는 사람은 거의 없다. 모든 훌륭한 발상은 기본적으로 어떤 비대칭성을 지니고 있다. 그것은 바로 그 발상을 발견하는 것보다 인식하는 것이 더 쉽다는 점이다. 계산의 이론에서는 이같은 비대칭이 인생의 중심적 사실이다. 혹은 그렇게 보인다.

잘 알려져 있는 세일즈맨의 여행 문제를 한 번 살펴보기로 하자. 우리의 세일즈맨 윌리 로먼 (Willy Loman) 은 판매망과 여행 예산, 그리고 비행기 요금의 팜플렛을 가지고 있다. 그는 보스턴에서 출발해 그의 예산의 한도 내에서 그림 1 에 나와 있는 9 군데의 도시를 두루 여행한 뒤 다시 보스턴으로 돌아가야 한다. 그가 당신에게 어떤 경로를 택해야 할 지 알아내 달라고 요구한다. 그에게 주어진 예산이 많다면 당신이 해야 할 일은 어렵지 않을 것이다. 하지만 허용된 예산이 적을 경우, 아주 힘들여 작업을 해야만 할 것이다. 예산의 한도를 넘기지 않는 것조차 불가능할 수도 있다. 둘 중 어떤 상황이든, 당신은 그 도시들에 대해 가능한 모든 순서를 고려해야 할 것이다. 이처럼 몇 안 되는 도시들을 고려하는 데에만도 실상 가능한 경로의 수는 대략 10 만 가지에 달한다!

그림 1  세일즈맨의 여행 문제 여기서의 작업은 세일즈맨 윌리가 일정한 예산 한도 내에서 보스턴을 출발해 다른 모든 도시를 여행하고 다시 보스턴까지 되돌아올 수 있는지 여부를 판별하는 것이다.

3 개의 도시 A, B, C 가 있는데 이들을 어떤 식으로 짝을 짓더라도 그 사이에 직항 비행 노선이 있다고 한다면, 가능한 순서 (즉, 각각의 도시를 방문하는 순서) 는 ABC, ACB, BAC, BCA, CAB, CBA 등 모두 6 가지이다. 도시의 수가 4 개가 되면 24 가지 순서를 만들 수 있다. 네 번째 도시 D 를 앞서 나열한 A, B, C 의 6 가지 가능한 순서 하나 하나마다 각각 4 군데 위치에 끼워 넣을 수 있는 것이다. 예를 들어 BCA 의 순서와 관련해서는 다음과 같이 4 가지로 순서를 결정할 수 있다.

DBCA, BDCA, BCDA, BCAD

순서의 가짓수는 계승 (! 기호로 표현되는) 으로 알려져 있다. 계승 (factorial) 은 빠르게 아주 큰 수에 이른다. 4 의 계승, 즉 4! = 4 × 3 × 2 × 1 = 24 이며, 5! = 5 × 4! 즉 5 × 24 = 120 이 되고, 6! = 720 이 되는 식으로 계속 이어진다. 물론, 컴퓨터는 많은 가능성을 다루는 데 훌륭한 능력을 발휘하지만, 급격히 증가하는 가능성의 수가 모든 계산 자원의 용량을 압도한다. 스티븐 쿡은 이러한 점을 지적한다.

만일 100 개의 도시가 있다면 100 의 계승에 해당하는 여행 방법들을 평가해야 합니다. 어떠한 컴퓨터도 100 의 계승만큼의 여행 방법을 시도해 볼 수는 없을 것입니다. 사람들이 그것을 이해하기는 어렵지요. 몇 가지 간단한 계산을 해 보면, 만일 당신이 태양계에서 각각의 회전수에 비할 만한 빈도로 그것에 작용하는 모든 전자들을 가지고 있을 경우, 그것을 찾는 데에는 태양이 다 타 버릴  때까지 시간이 걸릴 것이란 사실을 깨달을 수 있습니다. 우리가 이해해야 할 기본적인 요점은 실제로 실행에 옮길 수 없는 일들이 존재한다는 사실입니다.

세일즈맨의 문제를 지닌 비대칭성은 이것이다. 즉, 누군가가 윌리에게 특별한 경로를 줄 때 그 경로가 예산의 제한 조건을 충족시키는지 여부를 점검하는 일은 용이하다는 것이다. 윌리에게 좋은 해법을 찾는다는 것은 어려운 일이겠지만 그것을 검증하기는 쉽다.

1950 년대와 1960 년대에 걸쳐 설계, 오퍼레이션즈 리서치, 인공 지능 등의 분야에서 나타난 수많은 문제들은 이처럼 찾기는 어렵지만 검증은 용이한 속성을 지닌 것으로 보였다. 컴퓨터 과학계에 속한 많은 사람들이 이러한 문제들은 공통의 수학적 패밀리에 속한다고 생각하였다.

같은 시기에 각각 독립적으로 연구를 진행한 두 명의 과학자, 미국의 스티븐 쿡과 러시아의 레오니드 레빈이 1970 년대 초 바로 그 패밀리를 묘사하였다. 지금은 (아래에서 보게 될 이유들로 인해) '비다항식-완전 문제 (NP-complete problem)' 라고 알려져 있는 그 문제들의 수는 아주 많고, 또 점점 증가하고 있다. 연구 중인 컴퓨터 과학자들에게 있어 이 패밀리에 속한 문제를 증명한다는 것은 그에 대한 정확한 해법을 찾는 것이 불가능하다는 사실, 즉 고객이 그저 근접한 해법에 만족해야만 한다는 것을 보여 주는 것과 같은 일이다.

서구 계산 이론의 전통에서 계산의 난이도라는 개념은 논리학과 앨런 튜링이 제시한 '계산 불가능성' 의 연구 결과에 뿌리를 두고 있다. 마이클 라빈은 1959 년 계산 가능한 문제들의 고유한 난이도라는 개념을 최초로 공식화하였다. 1971 년 비다항식 완전 문제를 정의하면서 스티븐 쿡은 이같은 전통을 따르고 있었다.

러시아의 오퍼레이션즈 리서치 분야에서는 1950 년대 후반부터 특정한 최적화의 문제들이 러시아어로 '동물적 힘 (brute force)' 을 의미하는 '페레보 (perebor)' 를 필요로 한다고, 혹은 철저한 (exhustive) 특성을 가진다고 비공식적으로 규정하였다. 페레보의 범주에 들어가는 러시아의 과학자들은 누군가가 최상의 해법을 찾을 수 있다는 확신이 설 때까지 모든 대안, 혹은 거의 모든 대안을 탐색해야 하는 문제들을 조사한다. 예를 들어, 세일즈맨의 여행 문제처럼 문제의 크기가 그다지 크지 않은 경우라 해도 모든 대안을 시도하는 것이 실행 불가능할 수 있다.

하지만 페레보 문제의 이면에 깔린 이론에 영감을 불어넣은 것은 서구의 전통과는 달리 논리학이 아니라, 바로 안드레이 콜모고로프 (Andrei Kolmogorov) 가 문자들의 순서가 지니는 임의성과 그것을 설명하는 난이도 사이의 관계에 대해 제시한 개념이었다. 이 접근 방식은 1940 년대 후반 미국의 클로드 섀넌이 주창한 정보 이론에 의지하고 있었다. 그 때 이후로 수학적 과학 분야에서 구 소비에트 연방과 서구 사회 간에 이루어진 의사 소통은 기껏해야 산발적인 수준이었다.

레오니드 레빈은 1971 년 소비에트의 대학들에서 행한 강의와 1973 년의 한 짤막한 잡지 논문에서 페레보와 콜모고로프의 발상의 관계를 보여 주었다. 그 연구 결과 가운데 하나가 비다항식 완전 문제의 특성을 규정한 것이었다.

이것은 단지 논의의 시작에 지나지 않았다. 쿡이나 레빈을 비롯해 어떤 과학자도 그 이후로 이 패밀리에 속한 문제들이 지극히 어렵다는 사실을 실제로 입증하지는 못했다. 그들은 단지 이 패밀리 가운데 어떤 문제가 어려울 경우 모든 문제가 어려울 것이라는 걸 보여 주었을 뿐이다. 그렇게 하여 그들은 오늘날의 이론적 컴퓨터 과학에 아직 해결되지 않은 주요한 문제를 던져 주었다. 그것은 '비다항식 완전 문제가 철저한 조사를 필요로 하는가 아니면 필요로하지 않는가?' 라는 문제이다. 그것을 다른 식으로 표현하면 다음과 같다. 즉, 세일즈맨의 여행 문제와 같은 문제들에 대해 가능한 경로들 가운데 오로지 어떤 작은 부분만을 검토하면서 그 문제를 해결할 수 있는 알고리즘이 컴퓨터 과학의 역사를 변화시킬 것이란 이야기이다.

스티븐 쿡 : 논리학과 서구의 전통

스티븐 쿡은 1939 년 뉴욕 주 버펄로에서 태어났다. 쿡의 아버지는 유니온 카바이드 (Union Carbide) 의 화학자였으며 버펄로 대학에서 강의도 맡고 있었다. 그가 늘 시골 생활을 꿈꾸어 오던 중 스티븐이 열 살 되던 해에 온 가족이 뉴욕 주 클래런스에 있는 낙농장으로 이사를 하게 되었다. 그들은 농부에게 땅을 임대하였지만 젖소 (스티브가 젖을 짜던) 를 비롯해 일부 동물들은 그대로 가지고 있었다.

난 체스같은 것들에 대해 그저 평범한 정도의 흥미를 가지고 있었습니다. 특별한 것은 전혀 없었지요. 학교에서는 수학에 재능을 보였지만, 그곳은 단지 보통의 시골 고등학교에 지나지 않았습니다. 난 수학자가 되는 것에 대해 한 번도 생각해 본 적이 없었습니다. 어머니의 삼촌인 아서 (Arthur) 는 위치타의 수학 교수로 계셨는데, 그 분이 조상들 가운데 내가 알고 있는 유일한 수학자였습니다.

뉴욕 주의 클래런스는 이식이 가능한 심장의 페이스메이커를 발명해 낸 윌슨 그레이트배치 (Wilson Greatbatch) 의 고향이기도 하다. 그는 십대 시절의 쿡에게 전기 기사가 되고자 하는 야심을 불어넣었다.

난 여름이면 그가 작은 상점을 경영하고 있었던 농장의 다락방에서 그를 위해 일을 했습니다. 50 년대 당시로선 트랜지스터가 아주 낯선 물건이었는데, 그는 트랜지스터 회로를 가지고 실험을 하고 있었습니다. 난 그가 납땜으로 회로를 결합시키는 일을 돕곤 했지요. 난 그것이 아주 흥미진진한 일임을 알 게 되었습니다. 내가 미시건 대학에 처음 들어갔을 때 전공은 그들이 과학 공학이라 부르던 것이었지만, 실제 관심을 가지고 있었던 분야는 전기 공학이었습니다. 신입생 시절 (1957) 난 버나드 갤러 (Bernard Galler) 의 1 학점 짜리 프로그래밍 과정을 신청했습니다.

쿡과 한 친구는 3 보다 큰 모든 짝수는 두 소수의 합이라고 하는 그 유명한 골드바흐의 예상 (Goldbach's conjecture) 을 시험해 볼 프로그램을 짰다.

그들이 계산을 수행할 수 있는 한 그 예상은 유효하였다. (소수들에 대한 보편적인 속성을 증명하는 것은 아주 어렵기 때문에 그 예상은 아직까지도 미해결 상태로 남아 있다. 한편, 누구도 그것을 반증하는 예를 찾아 내지는 못하였다.)

쿡은 수학으로 전공 과정을 마쳤지만, 튜링의 정지 문제 (라빈의 장에서 다루어진) 와 같이 본래 불가능한 문제들에 대해 이해하기 위해서 계산 이론 과정도 충분히 익혔다. 그런 다음 쿡은 대수학을 공부할 목적으로 하버드의 수학 박사 과정에 들어갔다. 그러나 결과적으로 그에게 가장 많은 영향을 끼친 스승은 응용 과학 분야의 하오 왕 (Hao Wang) 이었다. 수학의 논리와 철학에 단련된 왕 교수는 자동 정리 증명, 즉 컴퓨터 자체에 의한 증명의 발견에 대한 연구를 하였다.

또 한 가지 그에게 영향을 준 것은 마이클 라빈의 1959 년 논문에 의해 당시 막 수학적 기초를 확립하게 되었던 복잡성 이론 (complexity theory) 이었다. 라빈, 하트마니스, 스턴즈 등을 포함하여 복잡성 이론의 여러 장래성 있는 인물들이 쿡처럼 열성적인 대학원생들에게 강의를 하였다.

그것은 아주 자연스럽고 기본적인 문제로 여겨졌습니다. 원칙적으로는 알고리즘을 이용해 해결할 수 있지만 실제로는 그렇지 못한 문제들이 명백하게 존재합니다. 그것은 당신이 그 문제들을 풀기 전에 태양이 다 타버리기 때문이지요. 따라서, 문제들의 고유한 난이도에 관해 묻는 것은 그저 아주 자연스러운 질문일 뿐입니다. 실제로 컴퓨터가 존재하기 이전에는 직접 손으로 하지 않으면 알고리즘을 실행할 수가 없었지요. 그 과정이 아주 지루하여 복잡성의 문제는 그다지 흥미를 일으키지 못했습니다. 우리는 이 강력한 기계들이 우리를 도와 주도록 만들었고 그 기계들은 상당히 강력한 도구 (초당 수천 번의 연산을 실행하는) 로 보였기 때문에, 우리가 실제로 풀 수 있는 것이 어떤 종류의 문제인지를 묻는 것은 아주 자연스러웠습니다.

쿡의 조언자 하오 왕은 이들 고려 사항에 논리적 관점을 더하였다.

난 그 (하오 왕) 가 내놓은 아이디어와 기법들에 대해 잘 알고 있었습니다. 비다항식-완전 문제에 대한 나의 연구 결과는 그의 것과 유사하지요. 단지 튜링과 왕은 술어 계산에 관해 논하고 있었고, 나는 명제 계산에 대해 논하고 있었습니다.

술어 계산법과 명제 계산법은 수학의 논리에서 사용되는 두 가지 언어이다. 왕은 술어 계산법에 대한 '만족성 (satisfiability) 문제' 의 복잡성을 연구하였다. 쿡은 훗날 명제 계산법의 만족성에 관심을 갖게 되었다. 그 차이를 이해하기 위해 다음의 예들을 살펴 보자.

술어 계산법은 개인으로 이루어진 집단에 관한 문장을 만든다. 예를 들어, 'All Olympic athletes are fit (모든 올림픽 출전 선수들은 원기왕성하다)' 라는 주장은 다음과 같이 된다. '모든 x 에 대해 OlympicAthlete(x) 는 fit(x) 를 함축한다.'

술어 계산법은 특정한 개인들을 x 로 대체할 수 있도록 허용한다. 예를 들어, 아킬레스 (Achilles) 가 올림픽 선수라는 사실, 즉 'Olympicathlete (Achilles)' 가 사실이라는 것을 알고 있다면 위의 공식은 'fit (Achilles)' 역시 사실이라는 결론에 이르게 된다.

이와 대조적으로, 쿡이 연구한 명제 계산법은 보다 단순한 언어로서 단지 개인에 대한 가정만을 허용한다. 예를 들면, 'Tweety is a bird (트위티는 새이다)' 와 같은 문장을 생각해 볼 수 있다. 명제 계산의 규칙들을 사용하면 기존의 명제들로부터 새로운 명제들을 결론으로 이끌어 낼 수 있다. 예를 들어, '트위티가 새이거나 루크가 가젤이다' 와 '루크는 가젤이 아니다' 라는 두 명제문이 모두 사실이라면, 그 원칙에 따라 '트위티는 새다' 가 사실이라는 결론을 추론할 수 있는 것이다.

만족성

그 두 가지 논리적 언어 모두에 중요하게 적용되는 문제는 주어진 식을 사실로 만드는 참값과 거짓값의 지정이 있느냐의 여부이다. 만일 있다면 그 식은 '만족할 만하며 (satisfiable)', 반대의 경우라면 그 식은 '만족스럽지 못하다 (unsatisfiable)'. 예를 들어, 'x and not y' 는 만족스럽다. x 가 참값으로 지정되고 y 가 거짓값으로 지정되면 언제나 그것은 참이 되기 때문이다.

한편, 'x and not y and not x' 는 만족스럽지 못하다. 그 진리값이 어떻게 지정되더라도 x 나 not x 가운데 하나는 반드시 거짓이 되어, 결국 전체 가정을 거짓으로 만들기 때문이다.

알론조 처치와 앨런 튜링은 술어 계산법으로 나타낸 특정한 식이 만족스러운지 여부를 가리는 것은 무한 대의 시간을 들이더라도 계산할 수 없다는 것을 보여 주었다. 쿡은 명제 계산법의 만족성은 가능한 진리값 지정 방법 가운데 많은 부분을 시험해 보도록 요구한다는 걸 보여 주었다.

가능한 지정 방법은 얼마나 존재하는가? 명제 변수 (x 와 같은) 가 단 하나라면 가능한 방법은 두 가지 (x 는 참이다 혹은 x 는 거짓이다) 이다. 두 개의 변수 (x 와  y) 가 있을 경우에는 다음과 같이 네 가지 방법이 가능하다. x 참, y 참 ; x 참, y 거짓 ; x 거짓, y 참 : x 거짓, y 거짓. 일반적으로 n 개의 변수가 있을 경우 가능한 지정 방법의 수는 2ⁿ 개이다. 이는 결국 10 개의 변수가 있을 경우 1000 가지, 20 개의 변수라면 1 백만 가지, 30 개의 변수라면 1십억 가지, 40 개의 변수라면 1 조 가지가 된다는 의미이다. 그 가짓수는 변수가 10 개씩 늘어날 때마다 계속해서 1000 배씩 증가하는 것이다.

가능성의 수는 변수 n 의 갯수에 대해 지수함수적으로 증가한다고 한다. n 이 바로 그 지수 부분에 해당되기 때문이다. 어떤 알고리즘이 각각의 가능성을 따로 따로 검사할 경우 그 알고리즘을 실행하는 시간 역시 지수함수적이라고, 즉 그 알고리즘에는 지수 시간이 걸린다고 한다. 이와 대조적으로, 다항식 시간 (polynomial-time) 알고리즘에서는 시간 요구량이 어떤 고정된 차수로 거듭제곱되는 n 의 식에 따라 증가한다. 여기서 n 은 문제의 크기를 나타낸다.

예를 들어, 다항식 시간의 식 n³ 은 n 이 10 일 때 1000 의 값을 가진다. n = 20 일 때에는 그 값이 겨우 8000 에 불과하며, n = 30 일 경우 27,000, 그리고 n = 40 일 경우엔 64,000 이 된다. 이것을 40 개의 변수가 있을 때 1 조 가지의 지정 방법이 가능하게 되는 지수함수적 증가와 비교해 보라!

비다항식-완전의 정의

쿡은 하버드에서 박사 논문을 마친 후 토론토 대학으로 옮겨가기 전에 잠시 UC 버클리 대학에 머물렀다.

그의 만족성에 대한 발상들은 1971 년 컴퓨팅의 이론을 주제로 열린 ACM (컴퓨팅 기계 협회) 의 제 3 차 연례 심포지엄에서 발표할 논문에서 통합되었다. 쿡은 가능한 해법, 즉 '후보' 해법이 다항식 시간 내에 검토될 수 있는 문제들을 다루었다. 어떤 후보가 시험하기에 좋은 것인지를 결정하는 일이 항상 가능한 것은 아니기 때문에, 어떤 프로그램은 그 해법을 추측해야만 하는 경우도 있다. 이러한 이유에서 쿡은 그 문제들에 비결정 다항식 (nondetermnistic polynomial) 혹은 NP 문제라는 이름을 붙였다. 추측 부분은 비결정적이고 검사 부분은 다항식이라는 의미이다. 세일즈맨의 여행 문제와 만족성 문제는 양자 모두 이러한 속성을 가진다. 여행 계획의 어떤 후보가 그 세일즈맨의 예산을 충족시키는지, 혹은 어떤 진리값 지정의 후보가 참인 공식을 만들어 낼 것인지를 빠른 시간 내에 적당한 후보를 찾아 내는 것이 과연 가능한가하는 것이다.

쿡은 만족성 문제가 NP 가운데 가장 어려운 문제에 속한다는 것을 보여 주었다. 특별히 그는 만족성이 다항식 시간 알고리즘을 가지고 있을 경우, NP 의 모든 문제가 다 그러하다는 사실을 보여 주었다. 그것은 만족성을 하나의 NP-완전 문제로 만들었다. 그리고, 실제로 어떤 문제가 NP-완전임을 보여 주는 것은 곧 그 문제가 만일 한 가지 해법을 찾기만 하면 그 해법을 빠르게 인식할 수 있음에도 불구하고 실상 해결하기는 어려운 문제라는 사실을 암시한다. 만일, 운좋게 상황이 급변하여 누군가가 하나의 NP-완전 문제를 위한 효율적인 알고리즘을 발견한다면, 그 알고리즘은 모든 NP-완전문제에 사용될 수 있다.

쿡의 논문이 발표되고 얼마 안 있어, UC 버클리의 리처드 카프 (Richard Karp) 가 또 다른 21 가지 문제가 NP-완전임을 보여 주었다. 그 중엔 세일즈맨의 여행 문제와 긴밀하게 연관된 문제도 포함되어 있었다. 그는 '축소 가능성 (reducibility)' 이라는 방법에 의해 다음과 같이 주장하였다. 즉, 만일 이 가운데 어떤 문제가 빠른 시간에 해결될 수 있다면 만족성 문제 역시 그러하다는 것이다. 따라서, 이 문제들은 최소한 만족성만큼 어려운 것이 되며, 그 역도 마찬가지이다. 과학의 입장에서 보면 불행하게도, 이 가운데 어떤 것도 그 문제들이 사실상 어렵다는 것을 증명하지는 못하고 있다.

유전자를 사용한 최단 경로 찾기 최근 UCLA 의 레오나드 에이들먼 (Leonard Adleman) 은 DNA 나선구조를 사용하여 세일즈맨의 여행 문제를 푸는 방법을 발견하였다. DNA 는 뉴클레오티드라는 화학적 성분들로 이루어진 두 가닥의 나선 구조이다. 거기엔 흔히 A, C, T, G 로 표시되는 4 가지 종류가 있다. 이들이 특정한 쌍을 이루면서 서로 결합하여 (구체적으로 A 와 T, 그리고 C 와 G) DNA 에 독특한 이중 나선형 형태를 부여한다. 에이들먼은 각각의 도시를 단일한 나선 구조상의 순서로 표시하였다. XinXout 은 도시 X 에 대한 나선 구조이고, YinYout 은 도시 Y 에 대한 나선 구조일 경우, X 에서 Y 로 가는 항공편은 xoutdyin 으로 표시될 것이다. 여기서 xout 은  Xout 과 짝을 이루고, yin 은 Yin 과 짝을 이룬다. d 는 X 에서 Y 까지 가는 비용에 비례하는 길이를 가진다. 도시의 가닥과 여행의 가닥들을 함께 섞으면서 그는 잘 정립된 생물 실험의 기술들을 사용해 모든 도시를 포함하는 최단 이중 나선 구조를 찾아 내었다. 이것이 바로 세일즈맨이 택해야 하는 경로이다. 아주 명쾌한 이 접근 방식은 크기가 극히 작고 성능이 낮은 계산 장치를 생각할 수 있게 해 준다. 그렇다면 이 접근 방식이 모든 NP-완전 문제에 일반적으로 적용되는 해법을 제공하는 것인가? 불행히도 그렇지는 못하다. 1000 개의 도시를 방문해야 하는 세일즈맨의 여행 문제를 풀려면 우리가 알고 있는 우주에 존재하는 원자의 수보다 훨씬 더 많은 미립자들이 필요하게 될 것이다.

(거의) 영구적인 토론 기계

따라서, 독자들은 만일 어떠한 문제도 실제로 어렵다는 것이 증명되지 않았다면 과연 무엇을 해낸 것이냐는 질문을 던질 수 있다. 여기서 하나의 유사한 예를 살펴 보는 것이 도움이 될 것이다. 특허청에서는 어떤 특허 신청이 영구적인 움직임을 약속할 경우 즉시 그 신청을 기각할 것이다. 특허 심사관들은 축소 가능성 주장을 사용한다. 즉, 그 기계가 약속된 대로 작동할 경우 에너지 보존의 문제는 틀리게 되는 것이다. 심사관들은 그 전제에 대해 큰 믿음을 가지고 있다.

영속적인 운동 기계는 NP-완전 문제와 유사한 특성을 가진다. 그러한 종류의 어떤 문제가 바르게 (다항식 시간 내에) 해결될 수 있다면, 모든 문제가 빠른 시간에 해결될 수 있는 것이기 때문에, 현재 연구 중인 'NP-완전 문제는 철저한 조사를 필요로 한다' 고 하는 가설은 잘못된 것이 된다. 컴퓨터 과학자들은 NP-완전 문제가 정말로 어렵다는 가설에 큰 믿음을 가지고 있다. 따라서, 만일 어떤 컴퓨터 과학자가 스스로 신속한 알고리즘을 제공할 수 없는 문제를 만나게 되면, 그는 NP-완전 문제들이 정말로 어렵다는 가설을 암시적으로 상기시키면서 그 문제가 바로 그러한 문제라는 것을 보이려 할 것이다. 쿡은 그 견해를 이렇게 요약하였다.

NP-완전 문제들은 아마도 다항식 시간의 해법을 가지지 않을 것입니다. 우리는 모든 NP 문제가 지수 시간 해법을 가진다는 사실을 알고 있습니다. 그 문제들은 다항식 시간의 해법도 가질 수 있지만, 그것은 해결되지 않은 큰 문제입니다. 만족성과 같은 NP-완전 문제 하나가 다항식 시간의 해법을 가진다면 그 문제들 모두가 마찬가지일 것입니다. 그 문제들은 모두 상호 축소가 가능합니다. 그것이 바로 이 문제가 지니는 중요성이지요.

카프의 연구 이후 세계 각지의 연구자들은 수천 가지의 문제가 NP-완전임을 보여 주었다. 전형적인 예는 전화망의 최적 기하학적 레이아웃, 또는 체커같은 게임을 하는 가장 좋은 방법 등이다. 쿡은 NP-완전 문제의 수에 당황하였다.

난 그저 NP-완전이 흥미로운 발상이라고만 생각하였습니다. 그것의 잠재적 영향력은 제대로 인식하지 못했던 것이지요.

레오니드 레빈 : 콜모고로프의 전통

1960 년대 쿡이 하버드에서 복잡성 이론을 주의 깊게 살피고 있는 동안, 구소련에서는 한 고등학교 학생이 페레보와 콜모고로프의 복잡성에 관해 배우고 있었다.

레오니드 레빈은 1948 년 우크라이나의 심장부에 위치한 공업 도시인 드네프로페트로프스크에서 태어났다. 그의 아버지 아나톨리 (Anatoly) 레빈은 처음엔 고등학교에서 러시아어와 문학을 가르치다가 이후 대학 강의를 하기 위해 교육학 박사 과정을 마쳤다. 레오니드의 어머니 안나 에렌버그 (Anna Erenburg) 는 다리를 설계하는 산업 건축기사였다. 일찍부터 레빈은 과학과 수학에 관심을 가지게 되었다.

난 멘델레예프 (Mendeleyev) 의 표 (원소들의 주기율표) 를 배우면서 실망을 느꼈습니다. 그것은 내가 원하는 만큼 정규적이지 않았기 때문이지요. 난 열심히 연구하여 몇 차례나 그 표를 다시 작성해 보려했습니다. 난 대체로 그것을 훗날 내가 미국에서 보게 된 것에 보다 근접하게 만들고자 했던 것입니다.

레빈은 침식이 하나 뿐이었던 자기집 아파트의 욕실에서 조제약품들을 섞는 화학 실험을 하기도 했다. 그의 아버지는 그에게 러시아의 인기있는 과학 서적 저자인 야코프 페렐만 (Yakov Perelman) 의 연작물을 사다 주었고, 또 그에게 올림피아드에 참가할 것을 권하기도 하였다. 올림피아드는 소비에트 정부가 수학과 과학에 특별한 재능을 가진 학생들을 발굴하기 위한 목적으로 고안해 낸 경쟁의 장이었다. 우승자들은 그 지역에서 한 단위 높은 행정 구역으로 진출한 다음 과학에 특화된 기숙학교에 선발되었다.

러시아에는 50 년대 후반에서 60 년대 전반에 걸쳐 전국적으로 한바탕 과학의 열풍이 불었습니다. 올림피아드는 대단한 인기를 얻었지요. 지방 출신의 아이들은 대부분이 대회에 참가했습니다. 우승자는 유대인만 아니라면 국제 올림피아드에도 출전할 수 있었습니다.

레빈은 키예프 시 올림피아드의 물리학 부문에서 1 등을 하여 키예프 대학에서 물리학과 수학을 전공하는 기숙학교로 보내졌다. 하루는 소비에트에서 과학이 지니는 그 '왕위 (royalty)' 에 걸맞게 성대한 의식이 치러지면서 콜모고로프가 직접 그 학교를 방문하였다. 레빈이 15 살 나던 해의 일이었다.

콜모고로프의 방문은 대단한 행사였습니다. 그는 모든 관리자들을 만난 후 아이들과도 자리를 가졌지요. 그 만남이 이루어진 장소는 거대한 방이었습니다. 그는 강의를 하고 나서 한 문제를 제출하도록 되어 있었는데, 우리에게 손을 들라는 말이 떨어졌을 때 그것은 곧 나와 다른 한 소년의 경쟁이 되었습니다.

어린 레빈에게 콜모고로프가 냈던 문제들은 그가 훗날 컴퓨터 과학에서 부딪히게 되는 문제들을 대비하는 데 유익한 경험이 되었다. 레빈이 제시한 해법 가운데 하나가 223 쪽의 박스에 예로 다루어져 있다.

콜모고로프는 그 때 퍼즐에 답하던 레빈의 능력을 잊지 않고 있다가 훗날 그를 모스크바 대학에 있는 자신의 학교로 초빙하였다.

콜모고로프의 퍼즐에 대한 레빈의 해법 문제 모든 단어, 모든 문자의 순서가 두 가지 등급, 즉 인쇄에 맞는 [적당한 (decent)] 것과 맞지 않는 [부적당한 (indecent)] 것 가운데 어느 하나에 속한다고 가정하자. 어떤 무한한 문자의 순서가 주어졌을 때 항상 그것을 유한한 순서로 쪼개어, 아마도 첫 번째 것만 제외하고는 모든 단어들이 같은 부류에 속하도록 만들 수 있겠는가? 해법 가능하다. 초기의 세그먼트들이 모두 적당하다면 그 문자의 순서들을 '접두부 적합 (prefix-decent)' 이라고 부른다. 어떤 유한 순서 A = a¹, a², … 가 n 을 상한으로 가지며, 따라서, n 개 이상의 문자로 이루어진 접두부를 잘라 내면 항상 A 의 비접두부 적합 무한 접미사가 남게 된다고 (즉, 그 접미사에서 최소한 하나의 접두부가 부적당한 것) 가정한다. 그리고는 n+1 개의 문자들로 첫 번째 세그먼트를 잘라 낸다. 남아 있는 (접두부 적합이 아닌) 순서는 부적당한 접두부를 가진다. 그것을 잘라 버린다. 앞의 문장을 영속적으로 반복하면, A 는 모두가 부적합인 유한 접두부들로 분해될 것이다. 이것을 무한히 반복할 수 있다는 것을 확인하려면, 우선 그것이 불가능하다고 가정하라. 그러면 k 번째 부적합 접두부 이후에는, 남아 있는 순서 가운데 모든 후속 접두부가 적합이 되어야만 할 것이다. 따라서, 우리는 그 시점까지 접두부를 잘라 내고 나서 접두부 적합 순서를 (가정과는 상반되게) 얻을 수 있을 것이다. 그러한 n 이 전혀 존재하지 않는다면, 접두부 적합 무한 접미사를 남기고 접두부를 잘라 버린다. 앞문장을 영구히 반복할 수 있으며, 그렇지 않으면 처음 몇 개의 접두부들이 결합된 길이가 바로 우리가 존재하지 않는다고 가정하는 n 의 한계가 될 것이다. 이것이 곧 후속절단이 임의적일 수 있다는 것을 의미하는 것은 아니다. 그 경우 접두부 적합 접미사를 남겨 두게 될 것이기 때문이다. 그러나 그것을 잘라내 매번 접두부 적합 접미사가 있도록 만드는 것은 분명히 가능하다 (그러한 n 은 전혀 존재하지 않으므로). 이제 A 는 모두가 (아마도 첫 번째 것을 제외한) 적합인 유한 접두부들로 분할된 상태가 된다. 그것들이 접두부 적합 순서의 접두부들이기 때문이다.

 

그는 스무명 남짓 되는 소그룹의 아이들을 가르쳤습니다. 우리를 위해 음악회를 마련하기도 했지요. 음악을 아주 좋아했거든요. 그는 또 시를 분석하기도 했습니다. 정말로 아는 것이 아주 많았고 그 대부분이 전문적인 수준이었습니다. 콜모고로프는 역사가로 인생의 첫발을 내디딘 후, 내가 기억하기론 어디선가 자신이 어떤 특정한 추측을 증명했다는 언급을 했습니다. 이어서 자신의 연구를 발표하였는데, 그것은 뛰어나다는 평을 받긴 했지만 우린 그에 대해 보다 많은 증명을 필요로 합니다. 이 후 그는 단 하나의 증명만으로도 충분한 수학자가 되기로 결심하였습니다.

레빈은 다른 것엔 거의 등을 돌릴만큼 수학에만 몰두하였다. 체스 게임은 하였지만 피아노 공부는 거부하였다.

난 러시아 소설을 읽는 걸 무척 좋아했습니다. 기억력이 아주 좋아 엄청난 편수의 시를 그저 장난삼아 암송하곤 했지요. 하지만 나중엔 그러한 기억력을 잃어 버려, 상상력에 제한을 받지 않을까 두려움을 갖기도 했습니다.

소비에트 체제는 수학과 물리학 분야의 어린 과학자들을 길러 내긴 했지만, 컴퓨터 과학에 대해선 적대적인 역사를 가지고 있었다.

50 년대 초 모든 것이 마르크스의 가르침 (원전보다 훨씬 더 어리석은 말로 해석되는 경우가 많았던) 에 일치해야 했던 구소련에서 컴퓨터 과학은 다소 불법적인 주제였습니다. 난 소비에트의 일부 철학자들이 노베르트 바이너 (Norbert Wiener) 에게 화가 나 있었다고 생각합니다. 그는 젊은 시절엔 위대한 수학자였지만 나이가 들면서 컴퓨터 과학에 대한 넌센스에 정신을 잃었던 인물입니다. 그가 후반에 내놓은 '대중 과학 (pop-science)' 의 발상 가운데 하나는 사이버네틱스 (cybernetics) 였습니다. 그것은 러시아어로 컴퓨터 과학을 의미하게 된 전문적 어감의 유행어였지요. 이것은 그저 무해한 넌센스의 일종이었음에도, 소비에트의 철학자들은 여하튼 그것이 마르크스주의와 맞서는 것이라고 인식하였습니다.

하지만 1960 년대에 이르자 소비에트 군대에서는 컴퓨터 과학이 명백한 실용성을 가지기 때문에 그것을 가르쳐야 한다고 주장하였다. 그들은 심지어 어린 학생들에게까지 컴퓨터 사용을 훈련시키기 시작했고, 레빈이 처음으로 컴퓨터와 접하게 되었던 것 역시 모든 학부생들에게 의무화되어 있는 준군사훈련에 참가했을 때였다.

우리는 … 아주 구식의 컴퓨터를 몇 대 가지고 천공 테이프와 많은 조명, 패널 등을 사용해 작업을 했습니다. 그것은 아주 인상적이었지요. 뿐만 아니라, 우리는 어느 정도 가망성에 입각한 것들을 배웠습니다. 로켓이 비행을 하고 있다고 가정해 봅시다. 그것이 이것저것에 영향을 미칠 가능성은 무엇이겠습니까? 난 군사학 과정을 몹시 싫어했지요. 하지만 우리가 연구하고 있었던 수학은 단지 언어에 불과한 알골에 대해 연구하는 대학 정규 과정의 컴퓨터 과목보다 더 흥미를 느끼게 했습니다.

콜모고로프 복잡성

1971 년의 박사 논문으로 레빈은 콜모고로프의 복잡성에 관한 내용을 다루었다. 콜모고로프는 그의 조언자 역할을 했으며, 다른 위대한 러시아 수학자들도 포함되어 있었던 레빈의 검토 위원회에서 받아들인 것처럼 그 논문을 인정하였다. 그럼에도 불구하고 레빈은 박사 학위를 거절당했다.

당시 소비에트의 젊은이들은 거의 모두가 콤소몰에 소속되어 있었습니다. 그것은 공산당같은 하나의 조직이었지만 아이들을 위한 것이었지요. 거기서는 다양한 활동을 통해 우리에게 정부를 사랑하도록 가르쳤습니다. 난 그 중 일부에 대해 사보타주를 일으키곤 했습니다. 내가 저지른 일들에 대한 처벌 규정이 있긴 했지만, 그것은 그들에게도 역시 좋지 않은 결과를 가져 올 것이었습니다. 결국 상관들에게 무언가 잘못이 있다는 것을 보여 주는 셈이었으니까요. 그래서 그들은 아무 일도 없었던 것처럼 보이려 했고, 난 처벌을 면할 수 있었습니다. 그러나 나는 체코슬로바키아 이후 시대가 변하고 있다는 사실을 인식하지 못했습니다. 어느 정도는 그 사실을 깨닫게 되길 원하지 않는 측면도 있었지요. 시끄럽고 오만했던 나야말로 당시 대학의 공산당 당국이 필요로 하고 있었던 희생양이었습니다. 가장 큰 타격은 (박사 학위를) 거부당한 것 자체가 아니라, 그 결정을 공식적으로 정당화하는 과정에서 아주 드물 게 명백한 정치적 단어들이 사용되었다는 점이었습니다. 그 표현으로 인해 난 다시는 박사 학위 취득을 시도할 수 없게 되어 결국 이민을 결정하기에 이르렀습니다.

레빈은 미국으로 이민을 가기에 앞서, 1973 년 소비에트의 한 잡지인 『Problemy Perdachi Informatsii』를 통해 전체 순차 검색 문제 (Universal Sequential Search Problems) 에 대한 논문을 발표하였다. 그는 페레보 문제와 콜모고로프 정보 이론 사이의 공식적 관계를 개략적으로 설명하였다. 콜모고로프 정보 이론은 어떤 문자들의 순서 (0 과 1 로 이루어진) 가 지니는 '임의성 (randomness)' 과 그 설명 (description) 의 길이 간의 관계를 연구한 것이었다. 예를 들어, 몇 안 되는 단어들로 백만 개의 1 이 연속되는 문자열을 기술하는 것은 쉽다. (우리는 바로 그렇게 하였다.) 마찬가지로, 00111 이 백만 번 반복되는 것과 같이 간략한 방법으로 반복되는 패턴을 기술하는 것도 가능하다.

콜모고로프의 술어학에서 짧은 설명을 가진 긴 패턴들은 임의적이지 않다. 콜모고로프가 행한 연구의 기본적인 결론은 임의성의 정도가 그것에 사용된 수학적 언어에는 거의 의존하지 않는다는 것이었다. 어떠한 정의든 대부분의 순서는 '임의적' 이다. 그것들은 최소한 그 순서 자체만큼의 길이를 가지는 서술을 필요로 하는 것이다.

(계수 인자를 사용해서 혼자힘으로 이것을 증명할 수 있다. 얼마나 많은 숫자들이 n 개의 이진수로 구성될 것인가? 그 답은 2n 개이다. 얼마나 많은 상이한 숫자들이 m < n 개의 이진수로 부호화될 수 있는 프로그램에 의해 설명될 수 있는가? 그것은 2m 개에 불과하다. 예를 들어, 만일 m = n - 10 이라면 2m 은 2n 의 1/1000 밖에 되지 않는다. 따라서, 길이가 n 인 모든 숫자들 가운데 99.9 퍼센트는 그것을 서술하는 데 n - 10 개보다 많은 이진수를 필요로 한다.)

레빈은 긴 문자열을 서술할 수 있는 프로그램을 찾는 것이 얼마나 어려울 것인가하는 문제를 검토하였다.

이것은 주어진 문자열을 생성하는 짧고 신속한 프로그램을 찾아내는 문제가 본래부터 지니고 있는 어려움에 필적하는 것이었습니다. 난 거기에 타일을 붙이는 작업 (공간 메우기의 문제) 을 줄이기 위한 아이디어를 얻었지만 결국은 실패하고 말았습니다. 그래도 비슷하게 보이는 문제의 범용성을 증명하는 데에는 성공하였지요. 그것은 공간의 불 함수 (boolean function) [회로 설계의 문제] 를 위한 깊이 - 2 의 작은 회로들을 찾아내는 것이었지요. 나는 만족성, 집합 커버, 사상 (mapping) 위의 그래프, 임베딩 (embedding) 등을 포함하는 다섯 가지 다른 문제들에 대해서도 그것을 수행하였습니다.)

구소련 내에 고립되어 있었던 레빈은 쿡과 카프가 그들 독자적으로 동일한 문제들이 대부분 '범용' 이라는 것, 즉 그들이 NP-완전이라 표현한 것이라는 걸 보여 준 사실을 알지 못하였다.

러시아에는 여러 해 동안 쿡과 카프의 논문들이 알려지지 않았습니다. 러시아의 어떠한 도서관이나 기관에서도 그 논문을 실은 학회지들을 받아들이지 않았기 때문이었지요. 여행이나 통화에 대한 규제 때문에 그러한 연구가 사적인 통로를 거쳐 러시아로 들어오는 것도 불가능하였습니다. 훗날 나는 카프의 연구를 보고 놀라움을 금치 못했습니다. 그렇게 많은 수의 훌륭한 문제들이 NP-완전일 것이라고는 예상하지 못했기 때문입니다.

구소련에서 레빈의 논문에 대해 보인 반응은 쿡의 연구에 대한 반응과는 대조적으로, 긍정적이지만 제한적이었다.

일부 사람들은 관심을 보였습니다. 난 그것이 진정한 관심인지 아니면 내가 정치적으로 곤경에 처한 데 대한 동정인지 알 수가 없었습니다. 사람들은 때때로 내가 대접받을 자격이 있다고 여겨지는 수준보다 더 친절한 태도를 보였거든요. 홍보 활동은 전혀 없었습니다. 이후 1970 년대 후반에 이르면서 러시아에서는 사람들이 카프의 연구에 관해 듣고 흥분하기 시작했습니다.

쿡과 레빈 : NP-완전 이후

1970 년대 중반, 레빈이 소비에트 당국과 문제들을 처리하고 있는 동안, 쿡은 새로운 문제에 주목하기 시작하였다. 그것은 시간과 메모리 사이의 모순은 무엇인가하는 문제였다.

사무실이나 방이 잡동사니로 어지럽혀져 있는 사람이라면 누구든 작은 공간 내에서 물건을 찾는 일 혹은 논문들을 체계적으로 정돈하는 일이 얼마나 어려운지를 알 것이다. 쿡은 토론토 대학의 보로딘 (A. Borodin) 과 함께 컴퓨터에서 그와 유사하게 나타나는 문제를 연구하였다.

국세청 (IRS) 에서 1 억의 세입에 대한 파일을 분류하려 한다고 생각해 봅시다. 속도가 빠른 방법은 많은 양의 컴퓨터 메모리를 필요로하는 반면, 속도가 느린 방법은 메모리 요구량이 아주 적다고 알려져 있습니다. 우리는 어떠한 방법도 시간과 메모리가 동시에 효율적인 것은 없다는 사실을 증명하였습니다.

[다음 내용은 수학에 숙달된 독자들을 위한 것이다 : 소요되는 시간의 곱과 사용되는 메모리 공간은 최소한 (n²)/(log n) 에 비례해야 한다. 여기서 n 은 정렬을 위해 되돌려지는 횟수를 나타낸다.]

문외한인 사람이 듣기에는 만일 한 과학자가 어떤 문제를 두고 그것을 해결하는 것이 불가능하다거나 실행할 수 없다고 말할 경우, 그것은 곧 희망이 없는 상황이라는 말과 마찬가지일 것이다. 쿡은 청소년기부터 그의 믿을 만한 의논 상대가 되어 준 발명가였던 독실한 장로교 신자 윌슨 그레이트배치 (Wilson Greatbatch) 가 종종 그의 선택 분야와 관련해 귀찮을 만큼 졸라댔다고 말한다.

내가 불가능성을 증명하는 것으로 이름을 얻게 되면서부터 그는 항상 몹시 회의적이었습니다. 그는 이렇게 말하곤 했지요. "무언가가 불가능하다는 것을 증명하는 것으로 어떤 진전을 기대할 수 있을까?" (하지만) 그것이 내가 풀고자 하는 문제가 불가능하다는 의미는 아닙니다. 언제나 길은 있습니다. 보다 적은 것으로 만족하십시오. 여러분이 정말로 영구히 작동하는 기계를 원하는 것은 아닙니다. 이럭저럭 넘기는 것을 꺼리지 않으면서, 반드시 어떤 에너지의 원천이 생기게 해야 합니다. 그것이 전부입니다. NP-완전 문제에 대해 여러분은 발견적 학습법 (heuristics), 지름길, 추정 등과 그에 입각한 모든 종류의 방법을 사용할 것입니다. 사람들은 계속해서 그에 대한 연구를 해 왔습니다. 난 NP-완전을 보임으로써 얻어지는 효과는 바로 유효하게 작용할 문제를 해결하는 데 사람들의 에너지가 쏠리도록 만드는 것이라고 생각합니다. 난 그것이 긍정적이며 건설적이라고 생각합니다. 여기서 강조해야 할 것은 기술이 빠른 속도로 변화하고 있음에도 불구하고 그 바탕에 깔린 원칙들은 여전히 그대로 남아 있으며 한계를 가지고 있다는 사실입니다.

쿡은 명제 논리의 알고리즘에 대한 기본적인 연구를 계속하였다. 현재 그의 관심 영역은 명제 논리 공식에 대한 짧은 (다항식 길이의) 증명을 찾아 내는 것이다.

현재 레빈은 보스튼 대학에서 컴퓨터 과학을 담당하는 교수이다. 그 곳에서 그는 시카고 대학의 마리오 세게디 (Mario Szegedy), 라슬로 바바이 (Laszlo Babai), 랜스 포트나우 (Lance Fortnow) 등과 공동 연구를 하면서 '투명한 (transparent)' 증명의 이론을 개발하는 작업을 돕고 있다. 그 수학자들은 다음과 같은 이상한 속성을 가진 증명을 작성하는 방법을 개발하였다. 즉, 그것은 만일 증명에 오류가 있을 경우, 그 증명의 어떤 아주 작은 부분에 대한 수학적 테스트가 특정한 비율의 시간에 오류를 검출해 낼 것이라는 점이다. 논의를 진전시키기 위해, 그것이 시간당 1/2 의 확률로 오류를 발견할 것이라고 해 보자. 그리고 이제는 그러한 방법의 증명을 모두 작성하고 그것의 정확성을 테스트하려 한다고 가정해 보자.

만일, 각기 다른 부분에 40 회의 테스트를 수행해 아무런 오류도 발견하지 못한다면 잘못된 증명을 작성했을 확률은 10¹² 분의 1 에도 못 미친다.

그것은 홀로그래피 사진과 다소 비슷합니다. 홀로그래피에서는 사진의 모든 부분이 다른 모든 부분에 관한 정보를 포함합니다. 그 증명의 모든 부분들도 이와 마찬가지입니다.

커다란 문제

최근 프린스턴의 앤드류 와일즈 (Andrew Wiles) 는 페르마의 대정리 (Fermat's last theorem) 를 해결하기 위한 하나의 가능성 있는 접근방식을 제시하였다. 그것은 바로 그 프랑스 수학자가 자신의 증명들 가운데 하나의 한계 내에서 어떤 집요한 골칫거리를 끄적거렸던 18 세기 이래로 학자들을 끊임없이 괴롭혀 온 문제이다. 혹시 그것과 동일한 것이 NP=P 를 증명할 수 있지 않을까? 다시 말해, 다항식 시간 내에 그 해법이 '해결' 될 수 있는 문제가 다항식 시간 내에 '검토' 될 수도 있을까? (그림 2 참조)

그림 2  어떤 문제가 어느 정도의 시간 내에 해결될 수 있다면, 그것의 해법은 그 시간 내에 검토될 수 있다. 따라서, P 는 NP 내에 포함된다. 컴퓨터 과학에서 아직 미해결 상태인 이론상의 한 가지 큰 문제는, NP-완전에 속하는 수천 가지 중요한 문제들이 실제로 다항식 시간 내에 해결될 수 있는지 아니면 지수 시간을 필요로 하는지 여부이다. 다시 말해, P 가 NP 와 일치하는가의 문제인 것이다.

 

쿡	이 분야의 수학이 처해 있는 슬픈 상황은 우리가 이것들을 증명할 수 없다는 것입니다. 우리는 P 가 NP 와 일치하지 않는다는 것을 증명할 수가 없습니다. 따라서, 결국엔 누군가가 NP-완전 문제를 다항식 시간 내에 해결할 어떤 명쾌한 병렬 알고리즘을 고안해 낼 수 있을 것입니다.

이와 같은 사례에서 어떤 진전이 있는지를 말하기는 어렵습니다. 그것은 곧 임박한 것이 아니라, 단지 부분적인 결과들이 있을 뿐입니다. 사람들은 각기 다른 수많은 영역에서 그 문제를 공략하고 있습니다. 그리고 어찌되었든 P = NP 가 되는 것은 가능합니다.

레빈	여러 세기에 걸쳐 유명한 추측으로 알려져 온 거의 모든 수학적 추측들이 해결되었다는 사실은 그 해법이 다항식이 아니라 지수적이라는 강력한 증거입니다. 수학자들은 흔히 그 역사적 증거가 바로 NP 는 지수적이라는 사실이라고 생각합니다. 역사적 증거는 그 반대 방향에서도 아주 강력합니다.

 

출처 : http://www.aistudy.com/pioneer/Cook_Levin.htm