POSTECHIAN 기사 보기

[2021 가을호] 현대 수학의 중심으로, 계산 복잡도 이론

  • POSTECHIAN
  • 2021-11-26 07:00:43

2021 AUTUMN Hello Nobel
노벨상
현대 수학의 중심으로, 계산 복잡도 이론
- NP와 P, 그리고 BPP와 P

2021 아벨상


컴퓨터공학과 오은진 교수님

에이비 위그더슨 Avi Wigderson

미국 프린스턴고등연구소

로바스 라슬로 Laszlo Lovasz

헝가리 알프레드레니수학연구소

추측 1. 본질적으로 어려운 문제가 있을까?

주어진 수 $n$을 인수 분해하는 방법을 생각해봅시다. $2$부터 $n-1$까지의 수를 하나씩 살펴보면서 이 중에서 $n$을 나누어 떨어지게 하는 수가 있는지를 찾아봄으로써 $n$의 인수를 모두 찾을 수 있습니다. 또한 이를 통해 주어진 수가 소수인지도 판별할 수 있습니다. 그렇다면 $267- 1$은 소수일까요? 17세기 수학자인 Marin Mersenne는 이 수가 소수라고 발표하였지만, 사실 $267- 1$은 합성수였습니다. Mersenne의 주장에 오류가 있다는 것이 밝혀지기까지는 200여 년의 시간이 걸렸습니다. 그리고 이 수의 인수를 찾는 데는 더 오랜 시간이 걸렸습니다. 이후 인수를 찾아낸 Frank Cole은 이 결과를 발표하기 위한 세미나에서 말을 한마디도 하지 않고 칠판에 다음과 같이 적었습니다.

$$267- 1 = 147573952589676412927 = 193707721 × 761838257287$$

증명을 찾기까지는 300여 년이 걸렸지만, 청중들이 증명을 이해하는 데는 몇 분이 채 걸리지 않은 것입니다. 이는 많은 수학 문제들의 공통적인 특징입니다. 수학 문제를 풀기는 쉽지 않지만, 주어진 답과 풀이를 검증하는 것은 간단합니다. 이를 계산 복잡도 이론의 언어로 표현하면 다음과 같습니다. 주어진 답과 풀이를 효율적으로 검증할 수 있는 문제의 집합을 $NP$라고 합니다. 예를 들자면, 주어진 수를 인수 분해하는 문제는 $NP$에 속합니다. 반면에 효율적으로 풀이를 찾는 방법이 존재하는 문제의 집합을 $P$라고 합니다. 정의에 의해 $P$는 $NP$의 부분집합입니다. 그렇다면 $P$는 $NP$의 진부분집합일까요? 다시 말해, $NP$에는 속하지만, $P$에는 속하지 않는 문제가 있을까요? 언뜻 생각해보면 그럴 것 같습니다. 그렇지 않다면, 검산을 쉽게 할 수 있다면 풀이 역시 쉽게 찾을 수 있다는 뜻으로 우리의 경험에 반대됩니다.

하지만 이를 수학적으로 증명하기는 쉽지 않습니다. 계산 복잡도 이론의 가장 중요한 난제가 바로 $P=NP$를 증명하거나 반증하는 문제입니다. 여기서 계산 복잡도 이론이란 문제들을 난이도에 따라 여러 개의 클래스로 구분하고 각 클래스 사이의 관계를 분석하는 학문입니다. 다시 $P=NP$ 문제로 돌아오면, 이 문제는 1970년대에 처음 제기되었으며, 2000년 미국 클레이 연구소에서 21세기의 수학의 방향을 제시하기 위해 선정한 7개의 난제 중 하나로 선정되기도 하였습니다. 많은 수학자와 컴퓨터공학자들은 $P$와 $NP$가 다를 것으로 생각하고 있지만, 아직 문제의 실마리를 찾지 못했습니다. 이와 관련한 또 하나의 계산 복잡도 이론 난제는 본질적으로 어려운 문제가 존재하는지에 대한 질문입니다.

추측 2. 약간의 오류를 허용한다면 문제를 쉽게 해결할 수 있을까?

이제 계산 복잡도 이론의 다른 난제인 무작위성에 대한 문제로 주제를 바꾸어 보겠습니다. 동전을 던지면 절반의 확률로 앞면이, 다른 절반의 확률로 뒷면이 나올 것입니다. 물론 여러 가지 물리적인 이유로 완벽하게 앞면과 뒷면이 같은 확률로 나오지는 않겠지만, 물리적인 이유를 무시하고 이상적인 상황을 생각해 보겠습니다. 이런 이상적인 동전을 이용하는 알고리즘을 무작위성Randomized 알고리즘이라고 합니다. 무작위성 알고리즘은 언제나 옳은 답을 내는 것은 아니지만, 높은 확률로 옳은 답을 내게 됩니다. 이에 반해서 무작위성을 사용하지 않는 알고리즘은 결정론적Deterministic 알고리즘이라고 합니다. 효율적인 무작위성 알고리즘을 갖는 문제의 집합을 $BPP$라고 정의합니다. 앞서 이야기했듯 계산 복잡도 이론은 문제들을 분류하고 각각의 클래스 사이의 관계를 다루는 학문이며, $P$는 효율적으로 풀이를 찾는 방법이 존재하는 문제의 집합입니다.

그렇다면 $BPP$와 $P$는 어떤 관계가 있을까요? 정의에 의하면 $P$는 $BPP$의 부분집합입니다. 그렇다면 $P$는 $BPP$의 진부분집합일까요? 다르게 이야기하자면, 효율적인 결정론적 알고리즘은 존재하지 않지만, 효율적인 무작위성 알고리즘이 존재하는 문제가 있을까요?

무작위성 알고리즘을 적용할 수 있는 예로 주어진 두 개의 $n$ 변수를 갖는 $d$차 다항식 $P(x_1, … , x_n)$ 과 $Q(x_1, … ,x_n)$가 같은 식인지를 판별하는 문제를 생각해 볼 수 있습니다. 두 다항식을 전개하여 각각의 항이 서로 동일한지 확인하면 되겠지만, 이 경우 지수 번의 연산이 필요합니다. 반면에 무작위성을 이용하면 다음과 같이 효율적인 알고리즘을 얻을 수 있습니다. $1$부터 $100d$ 까지의 수를 무작위로 $n$ 번 선택합니다. 선택한 수를 각각 $x_1, … , x_n$에 대입하여 두 다항식 $P$와 $Q$의 값을 비교합니다. 만약 두 다항식의 값이 서로 다르다면 이는 두 다항식이 다르다는 의미입니다. 만약에 두 다항식의 값이 같다면 우리는 어떤 결론을 내릴 수 있을까요? 두 다항식이 다르더라도, 어떤 입력값에 대해서는 같은 결과를 가질 수도 있습니다. 하지만 $P - Q$가 0이 아니라면, $P - Q$는 최대 $d$차 다항식이기 때문에 $P - Q$의 해는 최대 $d + 1$개가 있습니다. $100d$ 중에서 $d + 1$개만 피해서 고른다면, 그 입력값에 대한 $P$와 $Q$의 값은 서로 다르게 나올 것입니다. 따라서 $P$와 $Q$가 서로 다항식인데, 이 둘이 같다고 우리가 잘못 판단할 확률은 $1 / 100$ 이하입니다.

이 외에도 효율적인 무작위성 알고리즘은 알려졌지만, 효율적인 결정론적 알고리즘이 알려지지 않은 문제들이 많이 있습니다. 하지만 그렇다고 해서 $P$가 $BPP$의 진부분집합이라고 이야기할 수는 없습니다. 효율적인 결정론적 알고리즘이 존재하지만, 우리가 아직 찾지 못했을 가능성이 있기 때문입니다. 실제로 많은 컴퓨터 공학자와 수학자는 $P$와 $BPP$가 같은 집합이라고 추측합니다. 즉, 무작위성을 도입하여 약간의 오류를 허용하더라도 문제를 더 효율적으로 해결할 수는 없다고 추측하고 있습니다.

추측 1과 추측 2는 동시에 참일 수 없다

앞서 이야기한 첫 번째 추측과 두 번째 추측은 서로 무관해 보이기도 합니다. 첫 번째 추측은 본질적인 어려움Hardness에 대한 문제이고, 두 번째 추측은 무작위성에 대한 문제입니다. 그리고 2021년 아벨상 수상자 중 한 명인 Avi Wigderson의 대표적인 연구 결과 중 하나는 추측 1과 추측 2가 동시에 참일 수 없다는 것을 증명한 것입니다. 즉, 본질적으로 어려운 문제가 존재한다면, 무작위성을 도입하더라도 문제를 더 효율적으로 해결하기는 힘들다는 의미입니다. 이렇게 서로 무관해 보이는 두 성질을 Wigderson과 그의 동료 Impagliazzo는 ‘의사 난수 생성기Pseudorandom Generator’라는 개념을 도입하여 연결하였습니다. 결정론적으로 얻은 어떤 수열이 주어져 있을 때, 컴퓨터가 이를 무작위로 얻은 수열과 구분할 수 없다면 무작위성 알고리즘을 결정론적 알고리즘으로 바꿀 수 있습니다. 이렇게 무작위로 얻은 수열과 구분하기 힘든 수열을 만드는 알고리즘을 ‘의사 난수 생성기’라고 합니다. 본질적으로 어려운 문제가 있다면, 그 문제를 이용하여 ‘의사 난수 생성기’를 설계할 수 있고, 이를 통해서 무작위성 알고리즘을 결정론적 알고리즘으로 바꿀 수 있다는 것이 증명의 핵심입니다. Wigderson의 이러한 발견으로 우리는 문제의 본질적인 어려움과 무작위성에 대한 이해를 넓힐 수 있었습니다. 계산 복잡도 이론과 컴퓨터 이론의 궁극적인 목표는 계산과 효율성에 대한 이해를 넓히는 것입니다. 컴퓨터 이론의 기틀을 마련하고 여러 가지 중요한 결과를 발표했다는 점에서 올해 아벨상은 Avi Wigderson과 Laszlo Lovasz2에게 수여되었습니다. 컴퓨터 이론 분야는 1970년대부터 발전하기 시작하여 많은 성과를 얻었지만, 아직 연구해야 할 주제가 많은 분야입니다. 이번 아벨상을 계기로 컴퓨터 이론에 많은 학생들이 관심을 가지기를 바랍니다.

ALIMI 기 POSTECHIAN

기사 모아 보기
공유하기
목록