최근 조합론과 컴퓨터 과학을 연구하는 학자들의 SNS가 인터넷에 올라온 논문 하나 때문에 떠들썩했습니다. 민감도 추측이라는 컴퓨터 과학 분야의 오랜 추측을 이 분야 연구자라면 누구나 쉽게 이해할 수 있을 정도로 간결하게 증명한 겁니다.

답이 ‘예’ 또는 ‘아니오’ 둘 중 하나로 나오는 질문을 n번 하면, 그 질문의 답을 다 들은 뒤에 최종적으로 ‘예’ 또는 ‘아니오’로 결론을 내리는 컴퓨터 프로그램이 있다고 가정합시다. 예를 들어 ‘열이 있는가?’, ‘목이 아픈가?’, ‘기침은 하는가?’와 같은 질문을 한 뒤, 최종적으로 감기인지 예·아니오로 진단하는 컴퓨터 프로그램이 있는 것이죠.

그런데 답하는 사람이 실수로 질문의 답 하나를 반대로 말했습니다. 고작 실수 한 번인데, 전체 답이 달라지면 이상하겠죠? 학자들은 이 컴퓨터 프로그램이 얼마나 거짓말에 민감한지 재는 척도를 생각했습니다. 몇 번까지 거짓말을 해도 항상 같은 답이 나오는지 그 최댓값을 ‘민감도’라고 정한 거지요.

이 컴퓨터 프로그램은 사실 0과 1이 n개로 구성된 입력 x=(x₁, x₂, …, xn)에서 0 또는 1의 값을 만들어내는 함수라고 할 수 있습니다. 이런 함수를 ‘불 함수’라고 합니다. 어떤 불 함수 f의 민감도는 0과 1을 최대 몇 번까지 바꿔도 항상 답이 같은지 바꾼 횟수를 뜻하며 s(f)라고 씁니다.

불 함수의 오류 민감성을 재는 방법

이론 전산학자들은 민감도 외에도 불 함수가 얼마나 입력값의 오류에 민감한지를 재는 여러 척도를 만들었습니다. 그중 하나로 ‘블록민감도’라는 것이 있습니다. n자리 중 몇 자리의 모든 0을 1로, 1을 0으로 바꿨을 때 그 불 함수의 값이 바뀌면 그것을 ‘블록’이라고 합니다. 입력에서 서로 겹치지 않게 최대한 많은 블록을 고르면 몇 개까지 고를 수 있는지 정할 수 있는데요, 모든 입력에서 항상 최소 몇 개 이상의 블록을 고를 수 있으면 그 수가 바로 이 불 함수 f의 블록민감도 ‘bs(f)’입니다.
정의를 잘 보면, s(f)=k라면 k개의 한 자리 블록을 잡을 수 있으므로, bs(f)≥s(f)인 것은 당연합니다. 물론 이 두 값이 다른 경우도 분명히 있습니다. 예를 들어 x=1111, 1110, 1100, 1000, 0000인 경우에는 f(x)=1, 그 외에는 f(x)=0인 불 함수 f가 있다고 합시다. 이때 1100 때문에 s(f)는 2입니다. 하지만 항상 이 경우에도 블록은 3개(1번째 자리, 2와 3번째 자리, 4번째 자리)를 잡을 수 있습니다. 모든 경우를 잘 살펴보면 항상 3개 이상의 블록을 잡을 수 있어서 bs(f)=3이 됩니다.

이 두 가지 개념은 어떻게 관련이 있을까요? 이스라엘 컴퓨터 과학자 노암 니산과 미국-헝가리 컴퓨터 과학자 마리오 세게디는 bs값이 s의 몇 제곱보다는 작을 것으로 추측합니다.

불 함수가 얼마나 민감한지 재는 척도는 이 두 개 말고도 많이 있습니다. 그런데 이런 척도 대부분은 블록민감도와 다항식 정도 차이로 비슷하게 움직인다는 것이 알려져 있습니다. 더 정확하게 말하면 다른 척도 어떤 것을 보더라도 어떤 다항식이 있어서 블록민감도를 이 다항식에 넣어서 구한 값 이하가 되고, 블록민감도 역시 그 척도를 이 다항식에 넣어서 구한 값 이하가 된다는 것입니다. 따라서 민감도 추측이 옳다면, 불 함수에 관한 간단한 척도인 민감도가 수많은 다른 척도와 다항식 정도 차이로 비슷하게 움직인다는 것이 밝혀지는 셈이지요.

‘그 책’에 있을 2쪽짜리 증명

그런데 2019년 7월 초 갑자기 이 분야 연구자들의 트위터와 블로그가 떠들썩했습니다. 7월 1일 인터넷 논문 공개 사이트인 ‘아카이브’에 민감도 추측을 증명한 것으로 보이는 논문이 올라왔기 때문입니다. 그 논문을 써서 공개한 사람은 중국 수학자 황 하오 미국 에모리대학교 교수였습니다.

증명은 간결했습니다. 논문은 6쪽이지만, 그중 증명은 상세하게 써서 2쪽이었습니다. 캐나다 컴퓨터 과학자 라이언 오도넬은 7월 2일 트위터에 이 증명을 단 5줄로 요약해서 적었을 정도입니다. 저 또한 논문을 잠깐 읽고도 증명을 매우 쉽게 이해할 수 있었습니다.

사실 이런 일은 극히 드뭅니다. 대부분 오래된 추측이 풀린다면 그걸 증명하는 논문이 공개되더라도 실제로 읽고 정확하게 검증하려면 한참 걸립니다. 복잡한 논리 전개 과정 중에 한 군데라도 수학적 오류가 있는지 꼼꼼하게 검증하려면 시간이 꽤 걸리니까요.

이 논문은 민감도 추측을 바로 증명하지 않습니다. 황 교수는 논문에서 다음과 같은 내용을 증명합니다.

그전까지 이 방향의 가장 좋은 결과는 1988년 부부 수학자인 판 청과 로널드 그레이엄, 헝가리 수학자 졸탄 푸레디, 그리고 필자의 지도교수인 폴 세이무어가 쓴 논문인데, 이번에 나온 결과인 대신 0.49logn을 증명했습니다. 로그함수보다 제곱근이 훨씬 크지요.

언뜻 보기에는 이번에 증명한 것이 민감도 추측과는 관련이 없어 보입니다. 하지만 1992년 영국의 저명한 컴퓨터 과학자 크레이그 고츠먼과 이스라엘 수학자 나타 리니알은 이걸 증명하면 민감도 추측이 증명된다는 것을 이미 보였습니다. 그 방법을 쓰면 황 교수의 결과로부터 bs(f)≤2s(f)4라는 부등식이 증명됩니다.

황 교수는 미국 프린스턴 고등연구소(IAS)에서 박사후 연구원으로 지내던 2012년, 미국 수학자 마이클 삭스로부터 이 문제를 알게 됐고, 그때부터 관심을 가졌다고 합니다. 이후 틈틈이 문제를 들여다보았지만 알고 있는 방법으로는 도저히 풀지 못했다고 합니다. 그러던 2018년 말 이번 논문과 유사한 방법으로 다른 문제를 연구하고 나서, 그 방법에 대해 좀 더 깊게 생각했다고 합니다.

그리고 2019년 6월의 어느 날 스페인 마드리드 호텔에서 연구비 신청서를 쓰던 중, 어떤 방향으로 이 문제를 공략할 것인가를 쓰려고 고민하다가 이번 증명을 떠올렸다고 합니다. 이 같은 내용은 미국 컴퓨터 과학자 스콧 애런슨 블로그에 황 교수가 증명 후기를 댓글로 남겨 알려졌습니다.

헝가리의 유명한 수학자 에르되시 팔은 하늘에는 분명 ‘최고의 수학 증명을 모아놓은 책’이 있을 거라며, 그 책에 적힐만한 증명을 ‘The Book Proof(그 책에 있을 증명)’라고 부르곤 했습니다. 황 교수가 찾은 이 증명이야말로 그 책에 반드시 수록될 거라는 평이 많습니다. 어려운 추측을 해결하는 것도 기분 좋은 일이지만, 수많은 사람이 도전해서 실패했던 문제를 아주 간단한 증명으로 해결하는 것이야말로 훨씬 더 기분 좋은 일일 것입니다. 황 교수에게 축하를 보냅니다.

참고자료

황 하오 ‘Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture’, 황 하오 홈페이지 ‘www.mathcs.emory.edu/~hhuan30’, 스콧 애런슨 블로그 ‘www.scottaaronson.com/blog/?p=4229’, 라이언 오도넬 트위터 ‘twitter.com/BooleanAnalysis/status/1145837576487612416’, Quanta Magazine ‘Decades-Old Computer Science Conjecture Solved in Two Pages’

엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대학교에서 박사 학위를 받았습니다. 현재 기초과학연구원과 KAIST에서 연구와 강의를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐습니다.