컴퓨터는 정말 모든 경우를 다 계산해야 할까?
원본 영상: 컴퓨터는 정말 모든 경우를 다 계산해야 할까?
채널: 안될과학 Unrealscience
모든 조합을 확인하는 데 걸리는 시간
컴퓨터가 답을 찾으려면 가능한 경우를 모두 시험해야 할까? 영상은 스위치의 켜짐과 꺼짐을 조합하는 문제에서 출발한다. 조건 하나에 스위치가 최대 세 개까지 걸리는 문제를 컴퓨터 과학에서는 3SAT라고 부른다는 설명이다.
가장 단순한 방법은 모든 조합을 시험하는 것이다. 하지만 스위치가 하나 늘 때마다 경우의 수는 두 배가 된다. 영상은 스위치가 100개라면 초당 100경 번을 따지는 컴퓨터로도 약 4만 년이 걸린다는 예를 든다. 계산 한 번이 빨라도, 확인해야 할 조합이 거듭 두 배로 늘어나면 전체 계산 시간은 감당하기 어려워진다.
그렇다고 모든 조합을 하나씩 확인하는 방법만 있는 것은 아니다. 화자는 스위치가 하나 늘 때 계산 시간이 대략 1.3배씩 증가하는 알고리즘도 소개한다. 여기서 질문은 “모든 경우를 계산해야 하는가?”에서 **“문제가 커질 때 계산량이 늘어나는 속도를 어디까지 낮출 수 있는가?”**로 이어진다.
계산의 한계에 도전하는 발표
화자는 10월 26일 오픈AI의 발표를 소개하며, 그중 하나가 컴퓨터 과학에서 오랫동안 받아들여 온 계산의 한계에 도전한다고 설명한다. 핵심은 스위치가 많아질수록 스위치 하나당 계산 시간의 증가 배수가 1에 가까워지는 방법에 관한 주장이다.
다만 화자는 이 결과를 실용적인 지름길보다는 이론적인 결과라고 구분한다. 문제의 크기에 따라 계산 시간이 어떻게 늘어나는지를 밝히는 것과, 실제로 사용하는 컴퓨터에서 당장 더 빠르게 답을 얻는 것은 별개의 문제라는 취지다.
물리학의 이론은 어디까지 증명됐는가
물리학 사례에서는 이론이 실험 결과를 잘 설명한다는 사실과, 그 이론의 수학적 토대를 확립하는 문제를 구분한다. 화자는 오랫동안 실험 결과를 정확하게 설명해 온 이론을 소개하면서, 공간과 시간을 모눈종이처럼 잘게 나누어 계산하는 방식을 설명한다. 격자를 끝없이 촘촘하게 하더라도 이론이 성립하는지를 묻는 것이다.
이 대목에서 화자는 “AI가 밀레니엄 난제를 풀었다”는 표현은 틀렸다고 명확히 말한다. 발표가 주장하는 성과의 범위와 난제 전체의 해결에 필요한 조건을 구분해야 한다는 것이다. 관련 결과가 제시됐다는 사실만으로 더 큰 문제까지 모두 해결됐다고 받아들여서는 안 된다는 설명이다.
파동의 겹침과 바늘 문제의 연결
수학 사례에서 화자는 파동과 바늘 문제의 관계를 가느다란 빗줄기에 빗대어 설명한다. 파동을 아주 가는 여러 빗줄기로 나누어 생각하면, 서로 다른 방향으로 뻗는 빗줄기들이 얼마나 겹치는지를 물을 수 있다. 영상은 이 겹침의 문제가 여러 방향의 바늘을 담는 문제와 연결된다고 설명한다.
AI의 증명을 언제 받아들일 수 있을까
영상 후반부의 질문은 계산 능력에서 검증의 기준으로 옮겨간다. 화자는 Lean 같은 증명 검사 도구와 인간 검토의 역할을 함께 다룬다. 검사 도구가 있다는 사실만으로 검증에 관한 질문이 모두 사라지는 것은 아니라는 맥락이다.
이를 관통하는 질문은 **“AI가 내놓은 증명을 우리는 언제 맞다고 받아들일 수 있을까?”**이다. AI가 답을 제시하는 것과 그 답을 신뢰할 근거를 갖추는 일은 구분해서 살펴야 한다.
화자는 이러한 논의가 AI를 여러 영역에 도입할 때에도 참고가 될 수 있다고 본다. 영상의 마지막에 남는 질문 역시 같다. AI가 내놓은 답을 어떤 근거로 믿고, 어떻게 검증할 것인가.
출처
안될과학 Unrealscience — 컴퓨터는 정말 모든 경우를 다 계산해야 할까?