Leonid Levin
(러시아 태생 미국 컴퓨터과학자, 1948 ~)
레오니드 레빈은 1948 년 우크라이나의 심장부에 위치한 공업 도시인 드네프로페트로프스크에서 태어났다. 그의 아버지 아나톨리 (Anatoly) 레빈은 처음엔 고등학교에서 러시아어와 문학을 가르치다가 이후 대학 강의를 하기 위해 교육학 박사 과정을 마쳤다. 레오니드의 어머니 안나 에렌버그 (Anna Erenburg) 는 다리를 설계하는 산업 건축기사였다. 일찍부터 레빈은 과학과 수학에 관심을 가지게 되었다. ......
1971 년의 박사 논문으로 레빈은 콜모고로프의 복잡성에 관한 내용을 다루었다. 콜모고로프는 그의 조언자 역할을 했으며, 다른 위대한 러시아 수학자들도 포함되어 있었던 레빈의 검토 위원회에서 받아들인 것처럼 그 논문을 인정하였다. 그럼에도 불구하고 레빈은 박사 학위를 거절당했다. .... 시끄럽고 오만했던 나야말로 당시 대학의 공산당 당국이 필요로 하고 있었던 희생양이었습니다. 가장 큰 타격은 (박사 학위를) 거부당한 것 자체가 아니라, 그 결정을 공식적으로 정당화하는 과정에서 아주 드물 게 명백한 정치적 단어들이 사용되었다는 점이었습니다. 그 표현으로 인해 난 다시는 박사 학위 취득을 시도할 수 없게 되어 결국 이민을 결정하기에 이르렀습니다. ........
현재 레빈은 보스튼 대학에서 컴퓨터 과학을 담당하는 교수이다. 그 곳에서 그는 시카고 대학의 마리오 세게디 (Mario Szegedy), 라슬로 바바이 (Laszlo Babai), 랜스 포트나우 (Lance Fortnow) 등과 공동 연구를 하면서 '투명한 (transparent)' 증명의 이론을 개발하는 작업을 돕고 있다.......
러시아에는 여러 해 동안 Stephen Cook 과 Richard Karp 의 논문들이 알려지지 않았습니다. 러시아의 어떠한 도서관이나 기관에서도 그 논문을 실은 학회지들을 받아들이지 않았기 때문이었지요. 여행이나 통화에 대한 규제 때문에 그러한 연구가 사적인 통로를 거쳐 러시아로 들어오는 것도 불가능하였습니다. 훗날 나는 카프의 연구를 보고 놀라움을 금치 못했습니다. 그렇게 많은 수의 훌륭한 문제들이 NP-완전일 것이라고는 예상하지 못했기 때문입니다. .......
국세청 (IRS) 에서 1 억의 세입에 대한 파일을 분류하려 한다고 생각해 봅시다. 속도가 빠른 방법은 많은 양의 컴퓨터 메모리를 필요로하는 반면, 속도가 느린 방법은 메모리 요구량이 아주 적다고 알려져 있습니다. 우리는 어떠한 방법도 시간과 메모리가 동시에 효율적인 것은 없다는 사실을 증명하였습니다. ........
내가 불가능성을 증명하는 것으로 이름을 얻게 되면서부터 그는 항상 몹시 회의적이었습니다. 그는 이렇게 말하곤 했지요. "무언가가 불가능하다는 것을 증명하는 것으로 어떤 진전을 기대할 수 있을까?" (하지만) 그것이 내가 풀고자 하는 문제가 불가능하다는 의미는 아닙니다. 언제나 길은 있습니다. 보다 적은 것으로 만족하십시오. 여러분이 정말로 영구히 작동하는 기계를 원하는 것은 아닙니다. 이럭저럭 넘기는 것을 꺼리지 않으면서, 반드시 어떤 에너지의 원천이 생기게 해야 합니다. 그것이 전부입니다.
NP-완전 문제에 대해 여러분은 발견적 학습법 (heuristics), 지름길, 추정 등과 그에 입각한 모든 종류의 방법을 사용할 것입니다. 사람들은 계속해서 그에 대한 연구를 해 왔습니다. 난 비결정적 다항식 완전 (NP-complete) 을 보임으로써 얻어지는 효과는 바로 유효하게 작용할 문제를 해결하는 데 사람들의 에너지가 쏠리도록 만드는 것이라고 생각합니다. 난 그것이 긍정적이며 건설적이라고 생각합니다. 여기서 강조해야 할 것은 기술이 빠른 속도로 변화하고 있음에도 불구하고 그 바탕에 깔린 원칙들은 여전히 그대로 남아 있으며 한계를 가지고 있다는 사실입니다. ........ (스티븐 쿡과 레오니드 레빈 : 컴퓨터를 만든 15 인의 과학자 : Dennis Shasha. Cathy Lazere)
term :
Leonid Levin 계산 복잡도 이론 (Computational Complexity Theory) 비결정적 다항식 완전 (NP-complete) Stephen Cook 튜링 상(Turing Award)
site :
Leonid Levin's home page : Boston 대학 컴퓨터과학과
video :