d라이브러리

제 박사과정 지도교수인 마크 브레이버먼 교수님은 컴퓨터가 할 수 있는 연산의 한계에 관한 날카로운 질문을 던지고 답하는 연구를 합니다.

그런 연구를 토대로 2014 서울 ICM에서 초청강연자로 초대 받았고, 2016년에는 전산학 분야에서 성과를 낸 만 35세 이하 수학자에게 주는 ‘프레스버거상’과 ‘유럽수학회상’을, 2019년 과학과 공학 분야에서 업적을 낸 만 40세 미만 또는 박사 학위를 받은지 10년 미만 미국 과학자에게 주는 ‘워터맨상’을 받았습니다.

전산학 분야에서는 누구든 알고 있는 연구 실적을 지닌 분이지만, 겸손이라는 미덕까지 갖춘 훌륭한 학자입니다. 대부분 대학교의 교수 임용 과정은 조교수로 시작해 정년 심사를 거친 뒤 부교수, 정교수로 승진합니다. 그런데 브레이버먼 교수님은 뛰어난 연구와 강의 실력을 인정받아 2015년 조교수에서 바로 정교수로 임용됐습니다. 누구도 교수님의 정교수 임용을 놀라지 않았지만, 정작 본인은 학생들에게 “스스로 굉장히 놀랐다”고 이야기하셨어요.

컴퓨터과학은 알고리듬, 계산 및 정보에 관한 이론적 연구를 하는 분야입니다. 컴퓨터가 이해하는 세상과 실제 세상의 큰 차이는 ‘숫자를 어떻게 이해하느냐’입니다. 예를 들어 컴퓨터는 0 혹은 1로 세상을 이해하지만 실제는 0에서 1 사이에 무수히 많은 수가 존재하지요.

그래서 컴퓨터는 실수를 계산할 때 0과 1로 나타낼 수 있는 근사치로 계산합니다. 하지만 근사치로 계산할 때, 어떤 숫자가 계산이 가능하고 불가능한지를 따지는 것은 컴퓨터과학 분야의 대표적 난제입니다.

이 문제가 어려운 이유는 컴퓨터과학자와 수학자마다 컴퓨터에게 실수를 계산하게 하는 방법이 다르기 때문이에요. 그런데 브레이버먼 교수님은 대학원 시절 컴퓨터과학 분야에서 많이 응용되는 실수 연산 모형 두 개가 일치한다는 것을 증명했습니다. 그리고 이를 토대로 컴퓨터가 연산할 수 없는 ‘프랙털 집합’이 존재한다는 것도 밝혔습니다. 그 전까지는 컴퓨터가 프랙털 집합을 연산할 수 있다고 여겼습니다.

전산학에서 가장 근본적인 문제 중 하나는 여러 컴퓨터가 같이 문제를 풀 때 서로 얼마나 통신해야 하는지 파악하는 ‘통신복잡도 이론’입니다.

예를 들어서 한 컴퓨터에 X = (0 1 0 1)라는 정보가, 다른 컴퓨터에 Y = (0 0 0 0)라는 정보가 있습니다. 이때 X와 Y가 일치하는지 확인하려면 서로 얼마나 많은 데이터를 보내야 할까요?

가장 간단한 답은 한 컴퓨터가 다른 컴퓨터에 값을 통째로 보내 비교하는 겁니다. 가장 정확한 방법이지만 효율적인 방법은 아닙니다. 그럼 ‘좋은 확률’로 답을 구해도 괜찮다면 어떨까요?

예를 들어 3분의 2 이상의 확률로 맞는 걸 목표로 삼아봅시다. 놀랍게도 이 경우엔 4자리 행렬 값 즉, 2비트만 보내면 됩니다. 컴퓨터는 무작위의 행렬 E를 뽑아 X, Y와 곱해서 값을 비교합니다. 이때 E가 될 수 있는 경우의 수는 16가지입니다. 이중 EX와 EY가 실제 X, Y처럼 다른 경우의 수는 총 12가지로 3/4확률로 정답을 맞힐 수 있습니다.

이렇게 주어진 함수를 연산하기 위해 필요한 최소의 통신을 연구하는 분야를 통신복잡도 이론이라 합니다. 이 결과를 응용해서 많은 알고리듬이나 네트워크가 최적화 되어있다는 걸 보일 수 있지요.

통신에 필요한 정보의 총량 구해

정보복잡도 이론 개척

통신복잡도 이론처럼 데이터의 양을 재는 것이 아니라 가치 있는 정보의 총량을 계산한다면 어떨까요? 이를 연구하는 분야가 ‘정보복잡도 이론’입니다. 정보복잡도는 통신을 하는데 드는 최소한의 정보의 총량을 구하는 것으로, 브레이버먼 교수님은 정보복잡도의 여러 중요한 정리들을 푸셨습니다.

또 경매시스템 디자인이나 장기기증 매칭 등의 알고리듬을 제작하고, 이 알고리듬이 어떤 영향을 끼치는지 연구하고 있습니다. 예를 들어 컴퓨터 간 게임을 할 때 균형점을 찾기 위해 필요한 시간을 구하고 인공지능 학습에 필요한 표본 크기와 정보복잡도 이론을 접목하는 등 개척하신 기술들을 여러 방면으로 활용합니다.

직관적으로 생각할 때 어떤 연산이 가능하다는 것을 보이기 위해선 그 알고리듬이 존재한다는 것을 보이면 됩니다. 하지만 연산이 불가능하다는 것을 보이는 것은 어떻게 할 수 있을까요?

조건적으로 불가능하다는 것은 최근 2~30년간 많은 발전이 있었습니다. 하지만 무조건적으로 불가능하다고 보이는 것은 교과서 하나 정도의 분량이 나올만큼 연구된 내용이 적습니다. 브레이버먼 교수님의 연구는 이 교과서의 새로운 장을 열었습니다.