Stephen  Cook  &  Leonid  Levin

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

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

만족성 (satisfiability)

비다항식-완전 (NP-complete) 의 정의

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

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

콜모고로프 복잡성

쿡과 레빈-NP-완전 이후

커다란 문제

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

그것을 풀어 낼 알고리즘은 없을 것이라고 하는 결코 변하지 않을 어떤 기본적인 발상, 바로 그 발상이 나의 마음을 끈다. - Stephen Cook

때로는 어떤 것이 불가능하다는 사실이 좋을 때도 있다. 난 누구도 내게 해 줄 수 없는 것이 많다는 데 행복을 느낀다. - Leonid Levin

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

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

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 이 되는 식으로 계속 이어진다. 물론, 컴퓨터는 많은 가능성을 다루는 데 훌륭한 능력을 발휘하지만, 급격히 증가하는 가능성의 수가 모든 계산 자원의 용량을 압도한다. 스티븐 쿡은 이러한 점을 지적한다.

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

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

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

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

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

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

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

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

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

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

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

쿡과 한 친구는 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)' 이라는 방법에 의해 다음과 같이 주장하였다. 즉, 만일 이 가운데 어떤 문제가 빠른 시간에 해결될 수 있다면 만족성 문제 역시 그러하다는 것이다. 따라서, 이 문제들은 최소한 만족성만큼 어려운 것이 되며, 그 역도 마찬가지이다. 과학의 입장에서 보면 불행하게도, 이 가운데 어떤 것도 그 문제들이 사실상 어렵다는 것을 증명하지는 못하고 있다.

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

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

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

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

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

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

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

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

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

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

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

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

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

하지만 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 개보다 많은 이진수를 필요로 한다.)

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

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

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

쿡과 레빈 : NP-완전 이후

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

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

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

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

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

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

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

커다란 문제

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

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