Avi Wigderson은 40년 넘게 문제를 연구해 왔습니다. 그러나 계산 복잡도 이론가로서 그는 이러한 문제에 대한 답에 반드시 관심을 두지는 않습니다. 그는 종종 문제가 해결 가능한지 여부와 알려주는 방법을 알고 싶어합니다. "상황이 말도 안 된다"고 말했다. 위그더슨, 뉴저지 주 프린스턴 고등연구소의 컴퓨터 과학자입니다. 질문이 아무리 어려워 보이더라도 이에 답하는 효율적인 방법은 손이 닿지 않는 곳에 숨어 있을 수 있습니다. “우리가 아는 한, 우리가 직면하고 해결하려고 노력하는 모든 문제에 대해 이를 해결할 수 있는 알고리즘이 있다는 사실을 배제할 수 없습니다. 이것이 나에게 가장 흥미로운 문제입니다.”

오늘 Wigderson이 우승자로 선정되었습니다. AM 튜링 상는 계산 이론에 대한 근본적인 공헌으로 컴퓨터 과학 분야 최고의 영예 중 하나로 널리 알려져 있습니다. Wigderson의 작업은 해당 분야의 거의 모든 영역에 영향을 미쳤습니다. 그의 동료, 협력자, 멘티는 그가 서로 다른 영역 사이에서 예상치 못한 연결점을 지속적으로 발견한다고 말합니다. 그리고 1990년대부터 시작된 무작위성과 계산에 대한 그의 연구는 오늘날 연구의 기초가 되는 수학과 컴퓨터 과학 사이의 깊은 연관성을 드러냈습니다.

마두 수단2002년 Rolf Nevanlinna 상(현재 Abacus 상이라고 함)을 수상한 Harvard University의 컴퓨터 과학자인 그는 Wigderson이 이 분야에 미친 영향력을 놓칠 수 없다고 말했습니다. “실제로 Avi의 작업과 교차하지 않고 컴퓨터 과학 분야에서 작업하는 것은 매우 어렵습니다.”라고 Sudan은 말했습니다. "그리고 어디에서나 매우 깊은 통찰력을 찾을 수 있습니다." 예를 들어, 1980년대 후반에 수단은 Wigderson과 함께 특정 수학적 함수와 다항식 사이의 연관성을 조사하는 논문을 작성했습니다. 그 작업은 수단의 전체 경력을 시작했습니다. “이것은 Avi의 전형적인 모습입니다.” 수단이 말했습니다. "그는 어떤 공간에 들어가서 올바른 질문을 한 다음 계속 나아갑니다."

Wigderson은 이스라엘 하이파에서 홀로코스트 생존자인 간호사와 전기 기술자의 세 아들 중 하나로 자랐습니다. 그의 아버지는 퍼즐을 좋아했고 수학의 근본적인 아이디어에 깊은 관심을 갖고 이를 자녀들과 공유했습니다. 위그더슨은 “그 사람이 내가 이 바이러스에 감염된 사람이다”라고 말했다. 1970년대 하이파의 Technion에서 대학을 시작했을 때 그는 수학을 전공하고 싶었지만 그의 부모님은 그를 대신 컴퓨터 과학으로 이끌었습니다. “그들은 내가 일을 마치면 일자리를 갖는 것이 좋은 생각이라고 생각했습니다.”라고 그는 말했습니다.

그는 본질적으로 수학적이지만 답이 없는 심오한 질문들로 가득 찬 분야를 발견했습니다. 그의 초기 획기적인 노력 중 하나는 모순처럼 보이는 것에 초점을 맞추었습니다. 즉, 방법을 보여주지 않고 수학적 명제가 증명되었다는 것을 다른 사람에게 납득시키는 것이 가능한지 여부였습니다.

“증명을 보는 사람은 증명 자체에 대해 아무것도 배우지 못합니다.”라고 말했습니다. 란 라즈, 프린스턴 대학의 컴퓨터 과학자. 1985년 Shafi Goldwasser, Silvio Micali, Charles Rackoff는 이 개념을 도입했습니다. 영지식 대화형 증명, 몇 가지 명령문에 대한 사용법을 보여줍니다. Wigderson은 Micali 및 Oded Goldreich와 함께 나중에 그 아이디어를 자세히 설명하면서 어떤 진술이 증명될 수 있다는 것을 보여주는 조건을 제시했습니다. 영지식 증명도 있어요.

“이것은 암호화의 핵심 결과입니다. 그것은 매우 핵심입니다.”라고 Raz는 말했습니다. 영지식 증명을 사용하면 누군가가 메시지에 대한 정보를 공개하지 않고도 비밀 키를 사용하여 메시지를 올바르게 암호화했거나 서명했음을 증명할 수 있습니다. "Avi는 암호화 분야에서 매우 중요한 결과를 얻었으며 이것이 그 중 가장 중요할 수 있습니다."

그러나 아마도 Wigderson의 가장 근본적인 결과는 다른 영역에 있을 것입니다. 무작위성. 1970년대 후반에 컴퓨터 과학자들은 많은 어려운 문제의 경우 확률 알고리즘이라고도 불리는 무작위성을 사용하는 알고리즘이 결정론적 대안보다 훨씬 더 경쟁력이 있다는 사실을 깨달았습니다. 안에 1977 증명예를 들어, Robert Solovay와 Volker Strassen은 당시 최고의 결정론적 알고리즘보다 숫자가 소수인지 여부를 더 빠르게 결정할 수 있는 무작위 알고리즘을 도입했습니다.

일부 문제의 경우 확률적 알고리즘이 결정적 알고리즘을 가리킬 수 있습니다. 1980년대 초 Wigderson은 University of California, Berkeley의 Richard Karp와 협력하여 무작위성의 개념을 계산적으로 어려운 것으로 간주되는 문제에 연결했습니다. 이는 알려진 결정론적 알고리즘이 합리적인 시간 내에 문제를 해결할 수 없음을 의미합니다. Wigderson은 "우리는 그것이 어렵다는 것을 어떻게 증명할 수 있는지 모릅니다."라고 말했습니다. 그러나 그와 Karp는 나중에 비무작위화할 수 있는 특정 어려운 문제에 대한 무작위 알고리즘을 발견하여 이에 대한 결정론적 알고리즘을 효과적으로 발견했습니다. 비슷한 시기에 다른 연구자들은 암호화 문제에서 계산 경도 가정이 어떻게 일반적으로 역무작위화를 가능하게 할 수 있는지 보여주었습니다.

무작위성의 불합리한 효과로 인해 그는 무작위성 자체의 본질에 대해 생각하게 되었습니다. 그는 당시의 다른 연구자들과 마찬가지로 효율적인 문제 해결을 위해 그것이 얼마나 필요한지, 어떤 조건에서 그것을 완전히 없앨 수 있는지에 대해 의문을 제기했습니다. “처음에는 이것이 단지 우리 자신의 어리석음인지, 무작위성을 제거할 수 없는 것인지 확실하지 않았습니다.”라고 그는 말했습니다. "그러나 더 큰 문제는 무작위성이 항상 효율적으로 제거될 수 있는지 여부였습니다." 그는 무작위성의 필요성이 문제의 계산 난이도와 밀접하게 연관되어 있음을 깨달았습니다.

1994 용지, 그와 컴퓨터 과학자 Noam Nisan은 그 연관성을 조명했습니다. 그들은 대부분의 컴퓨터 과학자들이 의심하는 것처럼 자연적인 어려운 문제가 존재한다면 모든 효율적인 무작위 알고리즘이 효율적인 결정론적 알고리즘으로 대체될 수 있음을 증명했습니다. Wigderson은 "언제든지 무작위성을 제거할 수 있습니다."라고 말했습니다.

중요한 것은 결정론적 알고리즘이 무작위로 보이지만 그렇지 않은 데이터 문자열인 "의사 무작위" 시퀀스를 사용할 수 있다는 점입니다. 그들은 또한 의사 난수 생성기를 구축하기 위해 어려운 문제를 어떻게 사용할 수 있는지 보여주었습니다. (무작위 비트 대신) 의사 난수 비트를 확률적 알고리즘에 공급하면 동일한 문제에 대해 효율적인 결정적 비트가 생성됩니다.

수단은 이 논문이 컴퓨터 과학자들이 어려운 문제의 복잡성과 이를 해결하는 방법을 밝히는 데 도움이 될 수 있는 무작위성의 정도를 인식하는 데 도움이 되었다고 말했습니다. “단지 무작위성이 아니라 무작위성에 대한 인식이 중요합니다.”라고 그는 말했습니다. “그게 핵심이에요.”

수단은 무작위성은 어디에서나 나타나는 것처럼 보이지만 실제로는 찾기가 매우 어렵다고 지적합니다. “사람들은 파이의 숫자가 무작위로 보인다거나 소수인 숫자의 순서가 무작위로 보인다고 말합니다.”라고 그는 말했습니다. "그들은 완전히 결정되어 있지만 우리에게는 무작위로 보입니다." 그는 무작위성에 대한 인식이 오늘날 컴퓨터 과학의 핵심이라고 말했습니다. "그리고 그것은 Avi가 대대적으로 홍보한 것입니다."

무작위성은 복잡성 이론에서 강력한 자원이 되었지만 파악하기 어렵습니다. Wigderson은 동전 뒤집기와 주사위 굴림이 실제로 무작위가 아니라고 지적합니다. 물리적 시스템에 대한 충분한 정보가 있으면 결과를 완전히 예측할 수 있습니다. 완벽한 무작위성은 파악하기 어렵고 검증하기 어렵다고 그는 말했습니다.

그러나 Wigerson의 경우 컴퓨팅의 사례는 스마트폰, 노트북, 암호화 알고리즘뿐만 아니라 생물학적, 물리적 시스템 등 어디에나 있습니다. 최근 수십 년 동안 계산 이론의 발견은 새 떼와 선거 결과부터 신체의 생화학 반응에 이르기까지 예상치 못한 다양한 문제에 대한 통찰력을 제공했습니다. “기본적으로 모든 자연 과정은 계산으로 볼 수 있는 진화이므로 그렇게 연구할 수 있습니다. 거의 모든 것이 계산됩니다.”