Turing Award 수상자에게는 모든 것이 계산이며 일부 문제는 해결할 수 없습니다.

무작위성에 대한 Avi Wigderson의 선구적인 연구는 어떤 문제는 가장 강력한 컴퓨터의 성능을 뛰어넘을 수도 있다는 생각을 발전시켰습니다.

P=NP 문제와 관련하여 2024 ACM Turing Award를 수상한 Avi Wigderson은 "이것은 지금까지 제기된 가장 근본적인 지적 질문 중 하나입니다."라고 말합니다. "모든 사람이 틀리고 P가 NP와 같다면 놀라운 결과가 초래됩니다."

ACM(Association for Computing Machinery)은 수요일에 올해의 A.M. 컴퓨팅 분야의 노벨상이라고도 불리는 튜링상은 뉴저지주 프린스턴 고등연구소의 컴퓨터 과학자이자 수학자인 아비 위더슨(Avi Wigderson)에게 수여되었습니다.

ACM은 위그더슨이 "계산에서 무작위성의 역할에 대한 이해를 재편하는 것"과 "이론적 컴퓨터 과학에서 수십 년간의 지적 리더십"이라는 점에서 특히 뛰어난 계산 이론을 발전시킨 근본적인 공헌으로 인정받았다고 말했습니다.

영국의 수학자이자 컴퓨터 과학자인 Alan M. Turing의 이름을 딴 이 상은 Google의 재정 지원과 함께 100만 달러의 상금이 수여됩니다.

연구소의 Herbert H. Maass 교수인 Wigderson은 수십 년 동안 단순한 기계 이상의 의미로 계산에 대한 심오한 이해를 보여왔습니다. 계산은 우주 전체에서 발견되는 현상입니다.

Wigderson은 ZDNET과의 인터뷰에서 "계산은 정말 기본적인 개념입니다."라고 말했습니다. "단지 컴퓨터의 알고리즘이 아닙니다. 모든 것이 계산됩니다."

"해변에서 아주 간단한 단계로 계산된 놀라운 패턴을 가진 조개껍데기를 보면, 그것은 하나의 알갱이에서 자랐고, 지역적으로 이 알갱이들은 이웃 알갱이들을 계산하고 연결되었습니다. 이 정말 간단한 과정은 그것을 진화시키면 놀라운 패턴을 얻을 수 있습니다."

위그더슨은 "우리가 매우 잘 알고 있는" 국지적이고 점진적인 변화에 대한 이러한 단순한 규칙은 "매우 복잡한 현상을 만들어낼 수 있다"고 말했습니다. 계산적인 예가 풍부합니다. 계산은 수정란이 어떻게 인간이 되는가, 혹은 인간의 세포가 일생 동안 어떻게 분열하는지를 의미합니다. "그리고 가십도요." Wigderson이 덧붙였습니다. "당신이 자신에게 또는 페이스북에서 들은 내용을 말할 때 정보가 진화하는 방식은 완전한 계산 모델로 구성될 수 있는 계산 질문입니다."

Wigderson에게 Turing 상을 수여하는 것은 특히 적합합니다. 그의 분야인 계산 이론은 Turing의 획기적인 논문인 "On Computable Numbers, With an Application to the Entscheidungsproblem"으로 1936년 Turing에 의해 시작되었기 때문입니다.

튜링은 국부적이고 점진적인 변화를 통한 환경의 진화로서 계산에 대한 극도로 광범위한 정의를 위한 토대를 마련했습니다. 여기서 "환경"은 인간, 은하계, 해변의 조개껍데기, 정보 또는 다양한 현상이 될 수 있습니다.

Wigderson과 동료들이 수십 년에 걸쳐 발전한 Turing의 렌즈를 통해 보면 모든 자연 현상은 계산입니다. 위그더슨은 “흰개미가 어떻게 이런 성을 짓는지, 즉 어디로 가서 꿀을 찾을지 아는 꿀벌은 실제로는 만들기 위해 진화했습니다. 아주 작은 뇌 세포를 가지고 있음에도 불구하고 말입니다.”라고 Wigderson은 설명했습니다.

이 상은 특별히 계산에서 무작위성이 수행하는 역할을 이해하는 데 기여한 Wigderson의 공로를 인정합니다. 메인프레임에서 iPhone에 이르기까지 기존 컴퓨터는 "결정적"입니다. 즉, 예측 가능한 단계 패턴을 따릅니다. 그러나 자연에서 가장 흥미로운 계산 사례 중 상당수는 조개껍데기부터 중얼거림으로 알려진 찌르레기 떼에 이르기까지 무작위성 요소와 관련이 있습니다.

Wigderson과 공동 작업자는 무작위성 탐색을 사용하여 어떤 문제를 "효율적으로" 계산할 수 있고 계산할 수 없는지에 대한 이해를 발전시켰습니다. 세상에는 과학, 수학, 공학 분야에서 알려진 효율적인 알고리즘이 없는 수많은 문제가 있습니다. 즉, 지수적 시간이 아닌 "다항식 시간"에서 작동할 수 있는 알고리즘을 의미합니다.

예를 들어, 큰 정수를 소인수로 분해하는 데는 지수 시간 미만으로 실행될 수 있는 알려진 알고리즘이 없습니다. 그러나 그러한 알고리즘을 찾는 것만으로는 충분하지 않습니다. 컴퓨터 과학자와 수학자들은 그러한 "어려운" 문제에 대한 해결책이 존재할 수 있는지 어떤 식으로든 확실히 알고 싶어 증명합니다.

ACM이 인용한 세 가지 주요 논문은 순서, 진행을 형성한다고 Wigderson은 ZDNET에 말했습니다.

"문제는 알고리즘에서 무작위성이 얼마나 강력한가였습니다."라고 Wigderson은 말했습니다. 80년대부터 컴퓨터 과학자들은 무작위성을 효율적인 알고리즘에 대한 경로로 사용하는 여러 가지 방법을 찾아냈습니다. "그래서 무작위성이 매우 강력한 것처럼 보였습니다."

"이 작품들은 무작위성이 그렇게 강력하지 않다는 것을 보여주는 것을 목표로 했습니다."라고 그는 말했습니다. 대신 Wigderson과 동료들은 효율적이고 결정론적인 방식으로 일부 어려운 문제를 해결할 수 있는 의사 난수 생성기를 개발했습니다.

"이 모든 논문에서 어려운 문제를 다루고 무작위로 보이는 비트를 결정론적으로 생성할 수 있는 의사 난수 생성기를 만들고 확률 알고리즘 [및 패션]의 무작위 입력을 결정론적인 알고리즘으로 대체할 수 있습니다."

무작위성을 제거하고 이를 결정론적 접근 방식으로 대체하는 작업은 가장 정교한 의사 난수 생성기를 사용하는 최종 논문에서 정점에 달했습니다. Wigderson은 이 수업에서 다음과 같이 말했습니다. "우리는 모든 다항식 시간 확률 알고리즘이 다항식 시간 결정론적 알고리즘으로 만들어질 수 있다는 결론을 내릴 수 있습니다."

이러한 발견의 놀라운 부작용은 알고리즘에서 임의성을 제거할 수 있으면 문제의 난이도를 증명할 수 있다는 것입니다. 이는 문제가 어려운지 여부에 대한 질문을 해결하는 놀라운 백도어 방법입니다. .

"어떻게든 매우 다른 이 두 가지 개념(무작위성과 경도)은 밀접하게 연결되어 있습니다"라고 Wigderson은 말했습니다. "그들은 거의 같은 것입니다. 확률 알고리즘에서 무작위성을 제거하고 계산 문제의 견고성을 증명하는 것은 일종의 이중 문제입니다."

무작위성에 대한 작업을 더 깊이 탐구하려는 사람들을 위해 아래에 논문이 나열되어 있습니다. 그러나 무료로 다운로드할 수 있는 Wigderson의 대용량 "수학과 계산"에서 무작위성에 관한 장을 읽을 수 있습니다. 그 책을 훑어보면 다음 칵테일 파티에서 대부분의 사람들보다 머리와 어깨가 더 높을 것입니다.

• "Hardness vs. Randomness"(Noam Nisan과 공동 저작)
  이 논문에서는 새로운 유형의 의사 난수 생성기를 도입했으며 이전에 알려진 것보다 훨씬 약한 가정 하에서 무작위 알고리즘의 효율적인 결정론적 시뮬레이션이 가능하다는 것을 입증했습니다.

• "EXPTIME에 게시 가능한 증명이 없는 한 BPP에는 하위 지수 시간 시뮬레이션이 있습니다."(László Babai, Lance Fortnow 및 Noam Nisan과 공동 저작)
  이 문서에서는 '경도 증폭'을 사용하여 BPP(제한 오류 확률 다항식 시간)가 다음과 같은 결과를 가져올 수 있음을 보여주었습니다. 더 약한 가정 하에서 무한히 많은 입력 길이에 대해 지수하수 이하의 시간으로 시뮬레이션됩니다.

• "E에 지수 회로가 필요한 경우 P=BPP: XOR 정리의 무작위화 해제"(Russell Impagliazzo와 공동 저작)
  이 문서에서는 본질적으로 최적의 경도와 무작위성 절충점을 갖춘 더 강력한 의사 난수 생성기를 소개합니다.

67세의 위더슨(Wigderson)에게는 놀라운 연결을 찾아내는 기쁨이 어려서부터 원동력이었습니다.

Wigderson은 "저는 어릴 때부터 항상 수학을 좋아했습니다."라고 말했습니다. "아버지는 나에게 퍼즐 같은 것에 관심을 가지셨어요."

Wigderson은 이스라엘의 Technion(기술 연구소)을 졸업하고 프린스턴 대학교에서 컴퓨터 공학 석사 및 박사 학위를 취득했습니다. 그의 경험에 대한 감동적인 이야기는 작년에 Technion에서 명예 박사 학위를 받았을 때 Wigderson의 수락 연설에서 제공되었습니다.

Wigderson은 자신의 관심을 끄는 것에 대해 "나는 계산 모델을 공식화하는 데 정말 관심이 있습니다. 예를 들어 일부 암호화 프로토콜이 안전하거나 일부 알고리즘의 실행 시간이 그런 것인지 등입니다."라고 말했습니다.

"이런 근본적인 개념을 다루고 있지만 실제로는 수학적 분야라는 사실이 나에게는 매우 소중합니다."

그가 가장 자랑스러워하는 성과 중 하나는 정보를 비밀로 유지할 수 있지만 그럼에도 불구하고 두 명의 상대방이 합의에 도달할 수 있는 "영지식 증명"을 발전시키는 그의 작업이라고 Wigderson이 말했습니다. "내가 뭔가를 알고 있고, 누가 선거에서 이길지 알고 있는데 당신은 나를 믿지 않고, 나는 당신에게 [내가 정말로 알고 있다는 것을] 설득하려고 노력하고 있다고 가정해 봅시다. 당신에게 말하지 않고 당신을 설득할 수 있는 방법이 있습니다. 당신이 아직 몰랐던 것."

실제로 이러한 상황은 공개 키 암호화의 근원입니다. 예를 들어 각 당사자는 개인 키를 숨기고 있지만 상대방이 전자 계약에 정식으로 서명했다고 확신할 수 있습니다. 위그더슨은 이러한 영지식 증명에 대해 “완전히 역설적인 개념이다”라고 말했습니다. "이런 것이 존재할 수 있다고 생각하면 마음이 깜짝 놀라게 되는 종류입니다."

Wigderson의 지성은 즐거움과 근본적인 의미에 대한 예리한 감각 사이의 균형을 유지합니다. 예를 들어, 어떤 문제가 확실히 어려운지에 대한 질문은 사회에 큰 이해관계를 갖습니다.

1970년대 공식화된 "P=NP입니까?"라는 문구는 해가 검증될 수 있는 문제가 궁극적으로 다항식 시간 방정식으로 해결될 수 있는지 여부를 묻습니다. 즉, 효율적으로 해결됩니다. 그렇다면, 실제적인 시간 내에 겉보기에 해결하기 어려운 것처럼 보이는 세계의 일부 문제를 해결하기 위해 컴퓨터를 구축할 수 있을 것입니다.

P=NP의 Wigderson은 "이것은 지금까지 제기된 가장 근본적인 지적 질문 중 하나입니다."라고 말했습니다. 그의 분야에서 합의된 개인적인 추측은 P가 NP와 같지 않다는 것인데, 이는 일부 문제가 효율적으로 해결될 수 없다는 것을 의미합니다.

"모든 사람이 틀리고 P가 NP와 같다면 놀라운 결과가 초래됩니다"라고 Wigderson은 말했습니다. "당신이 해결하고 싶은 거의 모든 문제를 효율적으로 해결할 수 있습니다. 무엇이든 암을 치료할 수 있습니다."

그러나 "P가 NP와 같지 않다면 우리가 할 수 없는 일에 대한 영향은 상당히 중요합니다"라고 Wigderson은 말했습니다. 우선, 창의성과 같은 인간 사고의 일부 요소는 예를 들어 예술 창작에 사용되는 인간의 감각인 경험적 방법을 효율적으로 시뮬레이션할 방법이 없기 때문에 컴퓨터의 범위를 넘어설 수 있음을 의미합니다. .

그러나 다른 의미에서 유리는 반쯤 차 있다. NP 문제를 효율적으로 해결할 수 없다면 현대 경제의 전체 기반인 암호화가 깨지지 않아도 안전하다는 의미라고 위그더슨은 말했다.

P가 NP와 같거나 같지 않은지는 공개된 질문입니다. Wigderson은 "나는 누군가가 내 생애 동안 그것을 증명하는 것을 보기를 바랐지만 지금은 그것을 의심합니다"라고 말했습니다.

양자 컴퓨터도 이러한 난관에 대한 쉬운 대답이 아닙니다. "양자 컴퓨터를 생각해 보세요. 이것은 존재하지 않습니다."라고 Wigderson은 말했습니다. IBM, Google 등이 이를 강력하게 이론화했음에도 불구하고 "우리는 그것이 과연 존재할지 모릅니다."

P=NP가 공개 문제라면, '일반 인공 지능' 기계를 포함한 AI가 인간의 생각과 동등하게 하기 위해 무엇을 할 수 있거나 하지 않을 수 있는지에 대한 순간의 질문도 마찬가지입니다. 확실히, 우주의 모든 것이 계산된다는 개념은 AI가 인간 능력의 어느 정도 측정을 달성할 수 있어야 함을 의미합니다.

"우리는 탄소이고 실리콘이기 때문에 재질은 다르지만 어려움은 운영 수준이 아닌 심리적 수준에 있습니다"라고 Wigderson은 말합니다. 이미 AI는 "우리가 이전에 해결 방법을 몰랐던 많은 문제를 해결할 수 있다"고 Wigderson이 말했습니다. 그는 정리 증명 등에서 "이러한 장치를 공동 작업자로 사용하기 시작한 일부 저명한 수학자"를 알고 있습니다.

"나에게 더 흥미로운 것은 그들이 할 수 없는 일입니다"라고 그는 말했습니다. "이 유형의 컴퓨터의 한계는 무엇입니까?" 이러한 한계 중 하나는 일부 문제에 대해 AI 모델을 훈련하는 데 필요한 데이터가 상대적으로 부족하다는 것입니다.

"예를 들어 상대성 이론이나 맥스웰(맥스웰의 방정식)과 같은 새로운 수학 이론을 설계하는 경우에는 예가 훨씬 적습니다. 그렇죠? 따라서 이러한 유형의 이론적 돌파구는 이러한 기계에 더 어려울 것이라고 생각합니다. 데이터가 너무 없어요."

P가 NP와 같거나 같지 않다는 많은 의미에 대해 Wigderson은 새로운 세대가 주도하도록 하는 데 만족합니다.

"저는 연구소의 박사후 연구원들과 즐거운 시간을 보내고 있습니다. 그들은 모두 훌륭합니다. 그들 중 일부와 협력하고 있으며 젊은 사람들에게서 배우고 있습니다."라고 그는 말했습니다. "계속 배움을 주는 젊은이들에 둘러싸여 이런 상황에 있다는 것은 매우 좋은 일입니다."