컴퓨터 과학의 미해결 문제들

개요

수학에는 많은 난제들이 있습니다. 전세계적으로 유명한 밀레니엄 문제가 대표적입니다. 인지도 있고 학술적 가치가 높은 난제는 하나를 해결하는 것이 평생의 업적이 되기도 합니다. 많은 난제들이 꾸준히 풀리고 있지만, 새로운 문제가 창조되는 것에도 역시 끝이 없습니다.

난제의 범위를 컴퓨터 과학으로 좁혀봅시다. 대표적인 것으로는 밀레니엄 문제의 일부이기도 한 P-NP 문제가 있습니다. P-NP 문제는 너무나 유명해서 이 글을 읽을 사람이라면 누구나 한 번쯤은 들어보았을 것입니다. 하지만 그 외에 다른 컴퓨터 과학 난제는 그다지 널리 알려진 것이 없는 것 같습니다. 이 글에서는 비교적 이해하기 쉬우면서 흥미로운, 아직까지 해결되지 못한 난제들을 몇 가지 소개하겠습니다.

Minimum Spanning Tree를 구하는 최적 알고리즘의 시간 복잡도는 얼마인가?

널리 알려진 MST 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘 등이 있습니다. 크루스칼 알고리즘이나 프림 알고리즘은 정점의 개수가 $n$, 간선의 개수가 $m$개인 그래프에서 $\mathcal{O}(m\log{n})$¹ 시간이 소요되므로 그 자체로 이미 충분히 빠르기도 하고, 구현도 쉽기 때문에 알고리즘 문제를 해결할 때 주로 사용되지만, 시간 복잡도상 가장 효율적인 풀이는 아닙니다.

간선의 가중치를 알 수 없는 (비교만 가능한) 그래프에서, 시간 복잡도상 가장 효율적인 풀이로 증명된 것은 다음과 같은 알고리즘입니다.

$r = \log{\log{\log{n}}}$으로 두고, 정점이 $r$개인 트리에 대한 최적의 MST decision tree를 전부 계산합니다. 이 과정은 $\mathcal{O}(n)$에 되는 것을 증명할 수 있습니다.
그래프를 soft heap을 사용하여 최대 $r$개의 정점을 가진 컴포넌트들로 분할합니다. 이 과정에서 일부 간선이 제거될 수 있습니다.
Decision tree들을 사용하여 각 컴포넌트에 대한 MST를 계산합니다.
MST에 의해 span된 각 컴포넌트를 하나의 정점으로 축소시키고 dense graph에 대해 $\mathcal{O}(m)$에 동작하는 알고리즘을 적용합니다.
위에서 제거했던 간선들을 결과 포레스트에 추가하여 MST를 포함하도록 하는 서브그래프를 만듭니다. 이 그래프에 대해 재귀적으로 알고리즘을 적용합니다.

이 알고리즘의 전체 시간 복잡도는 decision tree를 사용하는 부분을 제외하고 $\mathcal{O}(m)$입니다. 문제는 이 decision tree를 사용하는 것의 시간 복잡도가 증명되지 않았다는 점입니다. 하지만 decision tree가 최적의 시간 복잡도를 낸다는 것만큼은 증명이 되어있기 때문에 비록 정확한 시간 복잡도를 알지는 못하더라도 이 알고리즘이 최적이라는 것 자체는 명확합니다.

Fast Fourier Transform의 최적 알고리즘의 시간 복잡도는 얼마인가?

영상 처리에서 많이 활용되며 합성곱을 빠르게 구하기 위해 PS의 고인물 영역에서도 자주 쓰이는 FFT는 $\mathcal{O}(n\log{n})$ 시간에 구하는 것이 가능하다는 사실이 잘 알려져 있습니다. 이 알고리즘 역시 이 정도면 충분히 빠르기 때문에 굳이 더 효율적인 것을 찾는 사람이 없지만, 과연 이보다 빠른 알고리즘은 존재하지 않는가에 대한 답은 여전히 미지수입니다.

P-NP 문제처럼 더 빠른 알고리즘의 존재 가능성 자체가 감이 잡히지 않는 상태이기 때문에 일반적으로 FFT 알고리즘의 최적화는 시간 복잡도보다는 절대적인 연산 횟수를 최적화하는 데에 초점이 맞추어져 있습니다.

최적화하고자 하는 부분에는 실수 곱셈의 연산 횟수, 덧셈 연산의 횟수, 그리고 두 연산의 총 횟수를 줄이는 것 등이 있습니다. 곱셈의 경우 $N=2^m$ 꼴일 때 $4N-2\log_2^2(N)-2\log_2(N)-4$ 만큼의 곱셈으로 FFT 연산이 가능하지만 이 경우 현실적으로 덧셈이 너무 많이 필요하다는 문제가 있습니다. 덧셈의 경우 알고리즘에 특정한 제한이 걸린 상태에서 $\Omega(n\log{n})$ 시간이 tight한 lower bound라는 사실이 몇 가지 밝혀진 것은 있으나 모든 경우에 대해 일반화될 수 있는지는 증명되지 않았습니다. 덧셈과 곱셈을 합한 경우 $2$의 거듭제곱 꼴인 $N$에 대해 약 $\cfrac{34}{9}N\log_2{N}$번 정도의 연산만이 필요한 알고리즘이 존재합니다.

$X+Y$ 정렬을 $\mathcal{O}(N^2\log{N})$보다 빠르게 할 수 있는가?

$X+Y$ 정렬은 일반적으로 생각하는 정렬이 아닌 조금 특이한 문제입니다. 크기가 $N$인 두 개의 집합 $X$와 $Y$가 있을 때 각 집합에서 하나씩의 원소를 뽑은 모든 순서쌍에 대해 그 합이 작은 순서로 정렬을 수행하는 것을 말합니다. 예를 들어 다음과 같은 두 집합이 있다면,

\[X = \{1, 5, 11\}, Y = \{2, 7, 14\}\]

이를 $X+Y$ 정렬한 결과는 다음과 같아야 합니다.

\[(1,2), (5,2), (1,7), (5,7), (11,2), (1,14), (11,7), (5,14), (11,14)\]

각 순서쌍의 두 수의 합이 다음과 같이 오름차순이 되기 때문입니다.

\[3, 7, 8, 12, 13, 15, 18, 19, 25\]

이 문제를 해결하는 가장 직관적이고 쉬운 방법은 조건 그대로 모든 순서쌍을 뽑은 뒤 합의 대소 관계를 기준으로 정렬을 수행하는 것이고, 이 자체로 현재까지 알려진 가장 좋은 시간 복잡도 $\mathcal{O}(N^2\log{N})$²이 달성됩니다. 하지만 이렇게 단순한 방법보다 정말 더 효율적인 방법은 존재하지 않는 걸까요? 이것이 아직도 밝혀지지 않았습니다.

다른 미해결 문제들과 마찬가지로 여러 부분 문제에 대한 최적화나 approximation에 대한 연구는 여럿 진행된 바가 있습니다. 우선 일반적인 비교 정렬로 $N^2$개의 원소를 정렬하기 위한 최소 비교 횟수는 $\mathcal{O}(N^2\log{N})$인 것에 비해 $X+Y$ 정렬의 최소 비교 횟수는 $\mathcal{O}(N^2)$만으로 가능하다는 것이 증명되어 있고, 실제로 이를 달성하기 위한 알고리즘도 제시된 것이 있습니다. 하지만 이것은 단순히 비교 횟수만이 그렇다는 것이지, 원소의 이동 등을 포함한 알고리즘 전체의 수행 시간은 여전히 $\mathcal{O}(N^2\log{N})$이기 때문에 과연 총 시간 복잡도를 이 밑으로 내릴 수 있는가는 여전히 미해결 문제입니다.

원소가 $0$ 이상 $M$ 이하의 정수들로만 이루어진 경우, 기수 정렬과 비슷하게 $M$의 크기에 대한 시간 복잡도로 정렬하는 방법을 사용할 수도 있습니다. FFT 알고리즘을 사용하면 $\mathcal{O}(N+M\log{M})$ 시간에 정렬이 가능합니다.

One-way Function은 존재하는가?

이 문제는 암호학계에서는 유명한 난제로, 만일 이것이 존재한다면 매우 안전한 암호화 알고리즘을 만드는 것이 가능하기 때문에 예로부터 학계의 큰 관심사였지만 아직까지 해결되지 못한 문제입니다. 문제를 간단히 설명하자면 어떤 함수 $f$는 다항 시간에 동작하지만 그 함수의 역함수를 다항 시간에 구하는 것이 불가능하게 할 수 있는가 하는 것이 이 문제입니다.³ 현재 존재하는 암호화 알고리즘들도 뚫리지 않고 있으니 one-way function이 아닌가 생각할 수 있지만, 이것은 어디까지나 역함수를 구하는 알고리즘들이 발견되지 않아서 아직까지는 안전할 뿐 이 알고리즘들이 미래에도 그대로 안전할 것이라는 보장이 된 것은 아닙니다.

만일 one-way function이 존재한다면 $f$의 역함수의 출력은 계산하기 어렵지만 검증하는 것은 쉬우므로 $P \ne NP$임이 증명되기 때문에 학술적으로도 엄청난 가치가 있는 문제임에는 틀림없습니다.

Graph Isomorphism Problem을 다항 시간에 판별할 수 있는가?

Graph isomorphism problem이란 두 그래프가 서로 같은 그래프인지를 판별하는 문제입니다. 즉, 두 그래프 $G$와 $H$에 대해 $G$의 각 정점을 $H$의 각 정점에 중복되지 않게 대응시켰을 때 $G$에서 서로 인접한 두 정점은 $H$에서 대응되는 두 정점이 서로 인접할 필요충분조건이 되게 만들 수 있다면 그 두 그래프는 동형 사상이라고 합니다.

트리를 비롯한 일부 특수한 그래프의 경우 다항 시간에 해결하는 알고리즘이 존재합니다. 평행우주 문제가 트리에서의 동형 사상을 판별하는 문제로, 이만큼이나 제한적인 형태에서도 solved.ac 기준 다이아 4를 받을 정도로 쉬운 문제가 아닙니다. 트리 이외에도 평면 그래프, interval 그래프, 순열 그래프 등등 특수 케이스에 대해서는 풀린 문제이지만, 모든 종류의 일반적인 그래프에 대해서도 해결이 가능한지는 아직까지 알려진 바가 없습니다.

행렬 곱셈의 가장 효율적인 시간 복잡도는 무엇인가?

행렬 곱셈의 시간 복잡도는 매우 오랜 기간에 걸쳐 꾸준히 개선되어오고 있습니다. $n \times n$ 행렬에 대해 학교에서 배운 방식대로 행렬 곱셈을 할 경우 $\mathcal{O}(n^3)$의 시간이 걸리고, 이보다 더 나은 시간 복잡도의 알고리즘을 생각해내는 것은 매우 어렵습니다.

시간 복잡도를 조금 개선하여 $\mathcal{O}(n^{\log_2{7}~=2.8074})$에 동작하는 슈트라센 알고리즘은 제법 알려져 실제로도 많이 사용이 되고 있습니다. 그런데 이 알고리즘은 무려 1969년에 만들어진 것으로, 그 이후에도 시간 복잡도상으로는 더 나은 알고리즘들이 여럿 개발되어 1990년에는 $\mathcal{O}(n^{2.3755})$, 이후에도 소수 셋째짜리 밑에서의 자잘한 개선이 이루어져 2020년에는 $\mathcal{O}(n^{2.3728596})$까지 시간 복잡도를 줄여내었습니다.

그럼에도 불구하고 분명히 시간 복잡도상으로는 많이 밀리는 슈트라센 알고리즘이 아직까지도 큰 행렬곱에서 주로 사용되는데, 그 이유는 물론 시간 복잡도의 함정 때문입니다. 즉, 슈트라센 알고리즘 이후로 시간 복잡도를 줄여낸 것들이 비록 시간 복잡도상으로는 더 효율적일지라도, 그에 숨겨진 상수가 너무나도 크기 때문에 웬만큼 큰 $n$이 되지 않는 이상은 슈트라센 알고리즘보다 더 빠르게 동작하지 못하기 때문입니다. 이 ‘웬만큼 큰’ $n$이라는 것은 현대의 컴퓨터에서 현실적인 시간 내에 계산이 불가능한 수준은 되어야 그 상수 차이를 극복할 수 있습니다.

현재까지 알 수 있는 lower bound로는 적어도 $n^2$개의 원소를 다 봐야 하기 때문에 $\mathcal{O}(n^2)$ 이상은 되어야 한다는 것 정도일 뿐, 실제로 이 알고리즘이 어디까지 개선될 수 있을지는 아직까지도 미지수입니다.

모든 정점 쌍에 대한 최단경로를 $\epsilon \gt 0$인 $\epsilon$에 대해 $\mathcal{O}(V^{3-\epsilon})$에 구할 수 있는가?

모든 정점 쌍에 대한 최단경로 문제는 꽤 익숙한 문제입니다. 알고리즘을 공부할 때 배우는 최단경로 알고리즘 3대장으로 다익스트라, 벨만 포드와 함께 모든 정점 쌍을 위한 플로이드-워셜 알고리즘이 널리 알려져 있습니다. 정점의 개수가 $V$, 간선의 개수가 $E$인 그래프에 대해, 이 플로이드-워셜 알고리즘이 바로 $\mathcal{O}(V^3)$에 동작하는 알고리즘으로 간선의 가중치가 양수든, 음수든, 실수든 전혀 관계 없이 $\mathcal{O}(V^3)$에 동작한다는 점이 특징입니다.

하지만 최단경로 알고리즘 역시 간선의 가중치에 제약을 걸면 더 효율적인 알고리즘들이 존재합니다. 무방향 그래프의 경우, 간선의 가중치가 모두 동일하면 Seidel’s algorithm을 사용하여 $\mathcal{O}(V^\omega\log{V})$ ($\omega$는 위에서 행렬곱의 시간 복잡도에 쓰인 $\omega$)을 사용할 수 있고, 간선의 가중치가 정수로 제한된 경우 $\mathcal{O}(V^3 / 2^{\Omega(\log{n}^{1/2})})$이나 $\mathcal{O}(EV)$ 시간이 걸리는 알고리즘을 사용할 수 있습니다. 또한 간선 가중치에 대한 제약이 없더라도 $\mathcal{O}(EV\log{\alpha(E,V)})$ 시간이 소요되는 알고리즘이 존재하나 항상 $\mathcal{O}(V^3)$보다 작다고 볼 수는 없습니다. 방향 그래프의 경우에는 $\mathcal{O}(EV+V^2\log{\log{V}})$라는 조금 더 개선된 알고리즘도 존재하지만, 여전히 $EV$가 $V^3$보다 작은 것은 아닙니다.

궁금한 것은 과연 간선의 개수나 간선의 가중치에 관계 없이, 아무리 밀도가 높은 그래프라도 정점의 개수에만 의존하여 $\mathcal{O}(V^3)$보다 빠른 시간 복잡도를 만들어낼 수 있는가인데, 이것이 가능한지 혹은 불가능한지 여부도 아직까지 밝혀지지 않은 상태입니다. 만일 비약적인 시간 복잡도의 단축이 가능하다면, 실제 데이터상에서 연산할 때에도 더 많은 양의 데이터를 빠르게 계산하는 데에 유용한 일이 많이 있을 것으로 추측됩니다.

두 $n$자리 수의 곱셈의 최적 알고리즘의 시간 복잡도는 얼마인가?

일반적으로 학교에서 배우는 두 수의 곱셈은 $n^2$의 시간 복잡도를 가집니다. 하나의 수의 각 자리에 대해 다른 수의 모든 자리와 개별적으로 곱하기 때문입니다. 널리 알려진 빠른 곱셈 방법에는 $\mathcal{O}(n^{\log_2{3}~=1.58})$에 동작하는 카라츠바 알고리즘이 있습니다. 하지만 카라츠바 알고리즘 이후에도 시간 복잡도가 더 개선된 알고리즘들이 있는데, $\Theta(n^{\log{5}/\log{3}~=1.46})$ 시간에 동작하는 톰-쿡 알고리즘이 그 중 하나이며, 그 이후에는 시간 복잡도를 더욱 줄여 $\mathcal{O}(n \cdot \log{n} \cdot \log{\log{n}})$을 달성한 쇤하게-슈트라센 알고리즘도 존재하며, 이후에는 퓌러 알고리즘이 $\mathcal{O}(n\log{n} \cdot 2^{\mathcal{O}(\log^{\star}{n})})$을 만들었고, 가장 최근인 2019년에는 결국 $\mathcal{O}(n\log{n})$을 성공시켰습니다.

더 빠른 알고리즘이 나올 때마다 더 이상 개선하는 것이 불가능해보일 정도로 치밀해 보이지만, 오랜 기간에 걸쳐 꾸준히 시간 복잡도가 줄어드는 것을 보면 신기하고 대단하게 느껴질 따름입니다. $\mathcal{O}(n\log{n})$은 이미 엄청나게 작은 시간 복잡도인 것 같지만, 이 문제도 역시 수학적인 lower bound가 증명되고 그에 도달한 알고리즘이 나오기 전까지는 앞으로도 수십 년간 더욱 개선이 이루어질지 혹시 모르는 일입니다.

마치며

수학의 한 분야로서, 컴퓨터 과학에도 무수히 많은 미해결 문제들이 아직 남아있습니다. 오로지 컴퓨터를 사용할 수 있기 때문에 중요한 시간 복잡도라는 개념을 중심으로, 불가능할 정도로 무거운 연산을 어디까지 줄여낼 수 있을지 수십 년에 걸쳐 그 한계를 시험하는 것을 보면 인간은 역시 도전하는 존재라는 생각이 듭니다.

참고 자료

프림 알고리즘은 피보나치 힙을 쓰면 $\mathcal{O}(m+n\log{n})$도 가능합니다. ↩
$N^2$개의 원소를 정렬하는데 왜 $\mathcal{O}(N^2\log{N^2})$이 아니냐고 생각할 수 있는데, 로그의 성질상 $\log{N^2}=2\log{N}$이고 상수배는 점근 표기법에서 무시될 수 있기 때문에 $\log{N}$으로 써도 됩니다. 직관적으로 설명하자면 원소의 수가 제곱이 되었을 때 로그에 의해 늘어나는 시간은 두 배밖에 되지 않는다는 뜻입니다. ↩
정확히는 어떤 랜덤화 알고리즘을 사용하더라도 역함수를 구하려는 시도가 성공할 확률이 극도로 낮게 만들어야 합니다. ↩