당신이 계산의 본질을 이해하려고 노력하고 있다고 상상해 보십시오. 당신은 어떤 길도 없는 깊은 광야에 있습니다. 헤아릴 수 없는 메시지 당신 주변의 나무 줄기에 새겨져 있습니다 — BPP, AC⁰[m], Σ₂P, YACC 외 수백 가지. 글리프는 당신에게 무언가를 말하려고 하는데, 어디서부터 시작해야 할까요? 그것들을 모두 똑바로 유지할 수도 없습니다.

만큼 많은 일을 한 연구자는 거의 없습니다. 러셀 임팔리아조 이 혼란스러운 상황을 헤쳐나가기 위해. 40년 동안 Impagliazzo는 다양한 문제의 본질적인 어려움을 연구하는 계산 복잡성 이론의 최전선에서 일해 왔습니다. 이 분야에서 가장 유명한 공개 질문인 P 대 NP 문제는 겉보기에 어려워 보이는 많은 계산 문제가 올바른 알고리즘을 사용하면 실제로 쉬운지 여부를 묻습니다. 대답은 과학과 현대 암호화의 보안에 광범위한 영향을 미칠 것입니다.

1980년대와 1990년대 임팔리아조는 유럽 통일에 주도적인 역할을 했다. 암호화의 이론적 기초. 1995년에 그는 P 대 NP에 대한 가능한 솔루션과 소수의 관련 문제를 언어로 재구성한 상징적인 논문에서 이러한 새로운 개발의 중요성을 분명히 밝혔습니다. 다섯 가지 가상의 세계 우리는 Algorithmica, Heuristica, Pessiland, Minicrypt 및 Cryptomania라는 기발한 이름으로 거주할 수 있습니다. Impagliazzo의 5개 세계는 한 세대의 연구자에게 영감을 주었으며, 계속해서 번창하는 하위 분야의 연구를 안내하고 있습니다. 메타 복잡성.

그리고 이것이 그가 꿈꾸는 유일한 세계는 아닙니다. Impagliazzo는 평생 동안 Dungeons and Dragons와 같은 테이블탑 롤플레잉 게임을 즐겨 왔으며, 새로운 규칙 세트 탐색할 새로운 설정이 있습니다. 동일한 장난기 넘치는 정신이 30년간의 즉흥 코미디 연습에도 활력을 불어넣었습니다.

Impagliazzo는 또한 계산에서 무작위성의 근본적인 역할을 설명하는 기초 작업을 수행했습니다. 1970년대 후반에 컴퓨터 과학자들은 무작위성이 때때로 알고리즘 개선 본질적으로 결정론적인 문제를 해결하기 위한 것입니다. 이는 수년간 연구자들을 당황하게 했던 직관에 반하는 발견입니다. Impagliazzo와 복잡성 이론가의 연구 아비 위그더슨 그리고 1990년대의 다른 연구자들은 특정 계산 문제가 정말로 근본적으로 어렵다면, 항상 가능 무작위성을 사용하는 알고리즘을 결정론적 알고리즘으로 변환합니다. 그리고 반대로 모든 알고리즘에서 무작위성이 제거될 수 있음을 증명합니다. 또한 증명할 것이다 정말 어려운 문제가 존재한다는 것입니다.

콴타 Impagliazzo와 함께 어려운 문제와 어려운 퍼즐의 차이, 신탁 상담, 즉흥 코미디의 수학적 교훈에 대해 이야기했습니다. 인터뷰 내용은 명확성을 위해 압축 및 편집되었습니다.

언제 처음으로 수학에 관심을 갖게 되었나요?

나는 수학이 무엇인지 알기 전부터 수학에 관심이 있었습니다. 3학년이 되자 구구단을 외워야 한다는 이유로 수학 성적이 떨어지기 시작했고, 나는 이를 거부했습니다. 어머니는 “그런데 러셀, 너는 수학을 좋아하는데 왜 이 일을 안 해?”라고 말씀하셨습니다. 그리고 저는 말했습니다. “그건 수학이 아니라 암기예요. 진짜 수학에는 암기가 필요하지 않습니다.” 그 시점에서 내가 배운 것은 산술뿐이어서 수학이 추상적인 개념에 관한 것이라는 개념을 어디서 얻었는지 잘 모르겠습니다.

컴퓨터 과학은 어떻습니까? 해당 분야의 일부는 매우 추상적이지만 대부분의 사람들이 처음 접하는 부분은 아닙니다.

고등학교 때 BASIC 프로그래밍 과정을 수강했지만 아무것도 끝내기가 정말 어려웠습니다. 프로그램은 종이 테이프로 전송되어야 했고, 종종 오작동을 일으키고 종이가 반으로 찢어지는 이 아주 오래된 컴퓨터를 통해 실행되어야 했습니다. 그래서 저는 컴퓨터 공학이 정말 지루하다고 생각했어요.

논리학을 공부하려고 했어요. 그러나 많은 개념을 실제로 형식화하려고 하면 계산이 포함되고 특히 계산에 대한 제한이 발생합니다. "수학의 내용이 참인지 어떻게 알 수 있나요?"와 같은 질문입니다. 그리고 “수학의 어려움을 어떻게 이해합니까?” 특히 이론적 컴퓨터 과학, 복잡성 이론으로 이어졌습니다.

당신의 가장 유명한 작품 중 일부는 암호화와 계산 복잡성 이론 사이의 연관성을 탐구합니다. 두 분야가 왜 연관되어 있나요?

암호화 시스템을 설정할 때 합법적인 사용자(액세스 권한을 부여하려는 사람)와 다른 모든 사람을 구별해야 합니다. 계산적으로 어려운 문제는 그들이 알고 있는 것을 기반으로 이러한 그룹을 구별하는 방법을 제공합니다. 그러나 두 그룹의 사람들을 구별하는 방법으로 문제에 대한 답을 알고 싶다면 어려운 문제만 사용할 수는 없습니다. 어려운 퍼즐이 필요합니다.

문제와 퍼즐의 차이점은 무엇인가요?

일반적으로 문제를 제기하는 사람은 답을 모를 수도 있습니다. 퍼즐은 답을 염두에 두고 고안된 문제입니다. 그렇다면 왜 퍼즐이 필요한가요? 왜냐하면 문제를 풀었다고 추정되는 사람이 실제로 풀었는지를 판단할 수 있어야 하기 때문입니다. 일상생활에서 우리는 오락을 위해 퍼즐을 사용하지만 교실에서도 사람들이 내용을 이해했는지 테스트하기 위해 퍼즐을 사용합니다. 암호화에서는 이런 일이 발생합니다. 우리는 누군가의 지식을 테스트하기 위해 퍼즐을 사용하고 있습니다.

다섯 세계의 차이점은 “어려운 문제가 있나요?”라는 질문에 대답하는 방식입니다. 그리고 “어려운 퍼즐이 있나요?”

그 서로 다른 대답은 어떻게 작용합니까?

첫 번째 세계인 알고리즘에서는 어려운 문제가 없습니다. 누군가가 문제를 어떻게 설계했는지 알 필요는 없습니다. 언제든지 문제를 해결할 수 있습니다. 휴리스티카는 “글쎄, 어쩌면 몇 가지 문제는 어려울 수도 있다”고 말합니다. 그런 다음 많은 문제가 어렵지만 대부분의 퍼즐은 그렇지 않은 Pessiland에 도달합니다. 내가 해결책을 알고 있는 거의 모든 문제는 당신도 해결할 수 있을 것입니다. 이 모든 세계는 암호화에 적합하지 않습니다.

Minicrypt에서는 해결 방법을 알고 있지만 여전히 여러분에게는 어려운 퍼즐을 만들 수 있습니다. 그리고 마지막으로, 크립토매니아(Cryptomania)는 도청자가 들을 수 있는 공공장소에 두 사람이 서서 여전히 도청자에게는 어려운 퍼즐을 함께 만들어내는 세계입니다.

다섯 세계 논문을 쓰게 된 동기는 무엇입니까?

당시에는 P와 NP에 대한 질문에 대한 서로 다른 대답이 우리가 어떤 문제를 해결할 수 있는지, 어떤 종류의 보안을 기대할 수 있는지에 큰 영향을 미친다고 알려져 있었지만, 다양한 형태의 용이성과 형태의 질적 차이는 경도는 실제로 명확하지 않았습니다.

불과 몇 년 전에는 20가지의 가능한 답변과 함께 상호 연관된 많은 질문을 사용하여 차이점을 제시한 매우 통찰력 있는 논문이 있었습니다. 내가 20개 세계에 관한 논문을 쓰고 싶었던 이유 중 하나는 우리가 그 몇 년 동안 엄청난 진전을 이루었기 때문입니다. XNUMX개의 가능한 세계에 대한 이름을 찾는 것은 어려웠을 것입니다.

그렇다면 왜 기발한 이름을 가진 다른 세계로 그렇게 구성할까요?

나는 회의를 위해 이 논문을 쓰기로 동의했습니다. 나는 무슨 말을 할지 고민하며 밤늦게까지 깨어 있었는데, 새벽 1시쯤에 다른 세계의 프레임을 보는 것이 좋은 생각인 것 같았습니다. 그리고 다음날 아침에 읽었는데 여전히 괜찮은 아이디어처럼 보였습니다. 이는 양적 세부 사항에 얽매이지 않고 이러한 아이디어가 실제로 세상에 어떻게 영향을 미칠지 보여주는 방법이었습니다. 이 논문에서 가장 행복한 점은 복잡성에 대한 연구를 수행하는 사람들로부터 학부생으로서 해당 분야에 관심을 갖게 된 논문이었다는 소식을 들었다는 것입니다.

연구자들은 다섯 가지 가능한 세계 중 하나라도 배제했습니까?

우리는 실제로 더 많은 것을 추가하고 있습니다. 사람들이 이에 대해 이야기하기 시작했습니다. 난독증 더욱 강력한 암호화 도구의 세계로. 우리가 1980년대 후반에 그렇게 많은 진전을 이루었고 그 이후로 어떤 세계도 제거하지 않았다는 것은 조금 우울합니다. 그러나 반면에 우리는 세계 간의 연결에 대해 더 많이 알고 있으며 훨씬 선명한 사진 각 세계가 어떤 모습일지.

가상 세계는 또한 "신탁"의 존재를 가정하는 증명에서 복잡성 이론에서 또 다른 역할을 합니다. 그렇다면 먼저 오라클이란 정확히 무엇일까요?

누군가가 문제를 해결하기 위한 알고리즘을 알지 못한 채 어떤 문제를 해결할 수 있는 독창적인 장치를 만든다고 상상해 보십시오. 오라클이 바로 그것이다. 우리가 그러한 기적적인 장치를 갖고 그것을 컴퓨터 안에 넣으면 계산 가능한 것과 계산 불가능한 것 사이의 경계가 바뀔 수 있습니다.

연구자들은 이러한 마술 상자가 실제로 존재할 수 있다고 생각합니까?

아니요, 아마도 존재하지 않을 것입니다. 초기에 Oracle 결과는 너무 가설적이어서 다소 논란의 여지가 있었습니다. 그러나 그들이 매우 깨달을 수 있는 한 가지 방법은 오라클을 사용하여 이상적인 상황을 모델링하는 것입니다. A가 반드시 B를 암시하는 것은 아니라는 점을 보여주려고 한다고 가정해 보겠습니다. 가장 극단적인 A가 있는 설정에서 시작하여 그것이 B를 보장하기에는 여전히 충분하지 않음을 보여줍니다. 모든 가능성이 있다고 하더라도 이를 보여줄 수 있다면 당신에게 유리하게도 당신은 여전히 ​​무언가를 증명할 수 없습니다. 그것은 증명하기 어려울 것이라는 정말 강력한 증거입니다.

또한 계산의 견고성과 무작위성 사이의 연관성을 발견했습니다. 그 연결은 어떻게 작동하나요?

이는 실제로 무언가를 이해하지 못하면 무작위로 보일 수 있다는 것을 말하는 방식입니다. 내가 1에서 1000 사이의 숫자를 생각하고 있다고 가정해보자. 내가 무작위로 숫자를 선택하면 당신이 추측할 확률은 1/1000입니다. 그리고 제가 Monty Python에 이어 "시간당 마일 단위로 유럽 제비의 평균 비행 속도는 얼마입니까?"라고 묻는다면, 당신에게도 같은 기회가 있습니다. 아마도 시속 1마일 이상은 갈 것이고, 아마도 시속 1,000마일 이상은 가지 않을 것입니다.

이것은 실제로 무작위가 아닙니다. 결정적으로 대답할 수 있는 질문입니다. 우리는 날아다니는 모든 제비를 측정할 수 있지만 제비 속도를 측정할 예산이 없고 제비의 무한한 공급이 없는 등 제한된 자원으로 결정하기가 다소 어렵습니다.

따라서 통찰력은 우리가 모르는 해결 방법이 있는 어려운 문제가 무작위로 보이는 "의사 난수" 숫자의 소스를 제공할 수 있다는 것입니다.

Monty Python 얘기가 나와서 말인데, 당신은 오랫동안 즉흥 코미디를 해왔다고 알고 있는데, 어떻게 시작하게 됐나요?

저는 1991년에 샌디에이고에서 조교수로 일을 시작했습니다. 그러다가 94년쯤에 '학과 밖에서의 생활이 별로 없구나'라고 생각했습니다. 그래서 무료 주간지를 구하고, 클럽과 활동 목록을 살펴보았습니다. 나는 즉흥 코미디를 제외한 모든 것을 제거했습니다. 적어도 내가 괜찮을 것이라는 것이 그럴듯하다고 생각했습니다. 나는 그 초급 수업에서 아내를 만났습니다.

그녀는 어떻게 생각했습니까?

그녀는 내가 정말 끔찍했다고 말했습니다. 당신이 논리학자라면 항상 모든 단어의 뉘앙스를 생각하도록 훈련받았습니다. 당신은 잘못된 것을 말하고 싶지 않습니다. Improv는 이를 뒤집는다는 점에서 훌륭합니다. 요점은 완벽한 것을 말하는 것이 아니라 무언가를 빠르게 구성하는 것입니다. 그것은 내 남은 인생과 정반대였습니다.

지금의 아내는 수업을 잠시 쉬었고, 30년 후 그녀가 돌아왔을 때 나는 그녀에게 깊은 인상을 남겼습니다. 그것은 XNUMX년 전이었습니다. 지금도 같은 선생님에게 같은 수업을 듣고 있어요.

즉석에서 연구에 접근하는 방식이 바뀌었나요?

당신이 갖고 있는 모든 생각에 대해 지나치게 비판적이지 않는 것이 좋은 습관입니다. 특히 협업에 도움이 됩니다. 저는 다른 사람들과 함께 일할 때 “그런데 다음과 같은 이유로 그 아이디어가 안 먹힐 것 같아요. 그것은 말 그대로 사실이 아니다.” 즉석에서는 항상 파트너가 말하는 것을 받아들여야 합니다. 그리고 저는 그것이 좋은 태도라고 생각합니다. 특히 학생들과 연구를 할 때 그렇습니다. 단지 그것이 틀렸다는 것을 안다는 이유만으로 그들이 말하는 것을 무시하지 마십시오. 100% 정확하지 않은 좋은 아이디어도 많이 있습니다.

무엇처럼?

문제에 대한 직관을 얻으려고 할 때 도움이 되는 한 가지 방법은 몇 가지 단순화된 가정부터 시작하는 것입니다. 이러한 가정은 일반적으로 사실이 아니지만 로드맵을 작성하는 데 도움이 될 수 있습니다. “코끼리가 있었다면 산을 넘어갈 수 있었을 거에요. 물론 코끼리는 없어요. 하지만 만약 그렇게 했다면 이렇게 했을 것입니다.” 그리고 나서 여러분은 “음, 어쩌면 이 단계에서는 코끼리가 필요하지 않을 수도 있습니다. 노새라도 괜찮을 것 같아요.”

롤플레잉 게임에 대한 당신의 사랑은 어떻습니까? 그것이 당신의 작업에 전혀 영향을 미쳤나요?

그것이 내 연구 전체에 영향을 미치지는 않았을지 모르지만, 내 5대 세계 논문에는 확실히 영향을 미쳤습니다. 나는 항상 판타지와 SF에 대한 일반적인 관심을 갖고 있었고 다양한 가능 세계를 생각해 냈습니다. 모든 것이 다르다면 어떤 모습일까요?

롤플레잉 게임이 가상의 세계를 탐험하는 데 그토록 매력적인 방법인 이유는 무엇입니까?

추측성 소설에 빠져 있는 사람들은 항상 세계를 만들어 왔습니다. Tolkien은 그것으로 가장 유명하며, 그는 그의 세계가 실제로 살고 있다고 느낄 만큼 엄청난 상상력을 가지고 있었습니다. 상상력이 부족한 우리를 위한 가장 좋은 방법은 사람들을 당신의 환경에 초대하고 게임을 하는 것입니다. 그렇게 하는 방법입니다. 이제 나만의 세상이 아니다. 제가 상상했던 대로 시작되었을 수도 있지만, 다른 협업과 마찬가지로 다른 모든 사람의 기여로 인해 그 이상으로 발전했습니다.