6.23 계산 복잡도 이론과 인공지능의 자원 제약적 한계

1. 계산 복잡도 이론의 기초

계산 복잡도 이론(computational complexity theory)은 계산 문제를 해결하는 데 필요한 자원—시간과 공간—의 양을 수학적으로 분석하는 이론이다. 계산 가능성 이론(computability theory)이 “무엇을 계산할 수 있는가“를 다루는 것과 달리, 계산 복잡도 이론은 “얼마나 효율적으로 계산할 수 있는가“를 다룬다. 이 구분은 인공지능의 한계를 이해하는 데 핵심적이다. 문제가 원리적으로 계산 가능하더라도, 필요한 자원이 실용적 한계를 초과하면 실질적으로 풀 수 없기 때문이다.

형식적으로, 결정 문제(decision problem)는 입력 문자열에 대해 예/아니오를 판정하는 문제이다. 계산 복잡도 이론은 결정 문제를 입력 크기 n에 대한 필요 자원의 증가율에 따라 복잡도 클래스(complexity class)로 분류한다.

2. 핵심 복잡도 클래스의 정의

P 클래스는 결정론적 튜링 기계(deterministic Turing machine)에 의해 다항 시간(polynomial time) O(n^k) 내에 판정 가능한 문제의 집합이다. P 클래스의 문제는 입력 크기의 증가에 대해 계산 비용이 다항적으로 증가하므로, 실용적으로 효율적으로 풀 수 있는 문제로 간주된다.

NP 클래스는 비결정론적 튜링 기계(nondeterministic Turing machine)에 의해 다항 시간 내에 판정 가능한 문제, 또는 동등하게, 해(certificate)가 주어졌을 때 그 정확성을 다항 시간 내에 검증할 수 있는 문제의 집합이다. 명백히 \text{P} \subseteq \text{NP}이다.

NP-완전(NP-complete) 문제는 NP 클래스에 속하면서, 모든 NP 문제가 이 문제로 다항 시간 환원(polynomial-time reduction) 가능한 문제이다. Cook(1971)은 부울 만족 가능성 문제(Boolean satisfiability problem, SAT)가 NP-완전임을 증명하였으며, Karp(1972)는 21개의 조합 최적화 문제가 NP-완전임을 보였다.

PSPACE 클래스는 다항 공간(polynomial space) 내에 판정 가능한 문제의 집합이다. \text{NP} \subseteq \text{PSPACE}이며, PSPACE-완전 문제는 NP-완전 문제보다 어렵다고 추정된다.

EXPTIME 클래스는 결정론적 튜링 기계에 의해 지수 시간 O(2^{n^k}) 내에 판정 가능한 문제의 집합이다. \text{PSPACE} \subseteq \text{EXPTIME}이며, \text{P} \neq \text{EXPTIME}이 증명되어 있다.

이 클래스들의 포함 관계는 다음과 같다.

\text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXPTIME}

3. 불완전성 정리와 계산 복잡도의 관계

불완전성 정리와 계산 복잡도 이론은 계산의 한계를 다루되, 서로 다른 차원의 한계를 설정한다.

불완전성 정리는 원리적 불가능성을 다룬다. 특정 명제는 주어진 형식 체계 내에서 어떤 알고리즘으로도, 어떤 시간과 공간을 투입하더라도 증명하거나 반증할 수 없다. 이는 절대적 한계이다.

계산 복잡도 이론은 자원 제약적 불가능성을 다룬다. 문제가 원리적으로 풀 수 있더라도, 필요한 자원이 지수적 또는 초지수적으로 증가하면 실용적으로 풀 수 없다. 이는 조건부적 한계이다—무한한 자원이 주어진다면 이론적으로는 풀 수 있다.

그러나 실천적 관점에서 이 두 한계의 구분은 흐려진다. 입력 크기 n = 1000인 NP-완전 문제에 대해 2^{1000} 단계의 계산이 필요하다면, 이는 관측 가능한 우주의 원자 수(\approx 10^{80})보다 많은 단계이며, 물리적으로 수행 불가능하다. 이 의미에서 자원 제약적 한계는 실천적으로 원리적 한계와 동등한 효과를 갖는다.

4. 인공지능의 핵심 과제와 복잡도

인공지능의 핵심 과제 상당수는 계산적으로 난해한(intractable) 복잡도 클래스에 속한다.

계획 수립(planning). STRIPS 형식의 고전적 계획 수립 문제—초기 상태, 목표 상태, 행동 집합이 주어졌을 때 목표를 달성하는 행동 열의 존재 여부 판정—는 PSPACE-완전이다(Bylander, 1994). 이는 계획의 길이가 입력 크기에 대해 지수적으로 증가할 수 있음을 의미한다.

제약 충족 문제(constraint satisfaction problem, CSP). 변수 집합, 정의역, 제약 조건이 주어졌을 때 모든 제약을 만족하는 변수 할당의 존재 여부 판정은 NP-완전이다. 이 문제는 스케줄링, 구성, 자원 배분 등 인공지능의 다양한 응용에서 핵심적이다.

확률적 추론. 베이즈 네트워크에서의 정확한 확률 추론은 #P-어렵이며, 근사 추론도 NP-어렵이다. 은닉 마르코프 모형(hidden Markov model)에서의 최적 상태 열 추정(비터비 알고리즘)은 다항 시간에 가능하나, 일반적 확률적 그래프 모형에서의 추론은 그래프의 나무 너비(treewidth)에 지수적으로 의존한다.

학습 이론. 최소 일관 가설(minimum consistent hypothesis)의 탐색—훈련 데이터와 일관된 가장 단순한 가설의 탐색—은 다수의 가설 클래스에 대해 NP-어렵이다. 신경망의 최적 가중치 탐색 역시 일반적으로 NP-어렵인 비볼록(non-convex) 최적화 문제이다.

5. 시간 복잡도 계층 정리와 자원의 근본적 가치

시간 복잡도 계층 정리(time hierarchy theorem, Hartmanis and Stearns, 1965)는 더 많은 시간이 주어지면 엄격히 더 많은 문제를 풀 수 있음을 증명한다. 형식적으로, 적절한 조건 하에서 f(n) = o(g(n))이면 \text{DTIME}(f(n)) \subsetneq \text{DTIME}(g(n))이다. 유사하게, 공간 복잡도 계층 정리(space hierarchy theorem)는 더 많은 메모리가 더 많은 문제의 해결을 가능하게 함을 보인다.

이 결과는 계산 자원이 근본적 가치를 가짐을 수학적으로 확립한다. 인공지능 시스템의 능력은 가용한 계산 자원에 의해 구조적으로 제한되며, 이 제한은 알고리즘적 혁신만으로는 완전히 극복할 수 없다. 더 어려운 문제를 풀기 위해서는 더 많은 자원이 필수적으로 요구된다.

6. 난해성에 대한 인공지능의 실천적 대응

계산 복잡도의 이론적 한계에도 불구하고, 인공지능은 NP-어려운 문제를 포함하여 다양한 난해한 문제를 실용적으로 처리한다. 이 실천적 성공의 이론적 기반을 분석한다.

평균 사례 복잡도(average-case complexity). 최악 사례(worst case)에서 NP-어려운 문제도 대부분의 실제 인스턴스에서는 효율적으로 풀릴 수 있다. 현대 SAT 풀기는 산업적 규모의 SAT 인스턴스를 효과적으로 처리하며, 이는 실제 인스턴스가 최악 사례와 구조적으로 다르기 때문이다. 상전이(phase transition) 현상—무작위 SAT 인스턴스의 난이도가 절 밀도(clause density)에 따라 급격히 변화하는 현상—에 대한 연구는 난해성의 구조적 원천을 해명하는 데 기여하였다.

고정 파라미터 다루기 용이성(fixed-parameter tractability, FPT). 문제의 파라미터 k가 고정되면, 입력 크기 n에 대해 f(k) \cdot n^{O(1)} 시간에 풀 수 있는 문제가 있다. 이 경우 파라미터 k에 대한 지수적 비용을 입력 크기와 분리할 수 있으므로, k가 작으면 실용적으로 효율적이다.

근사 알고리즘(approximation algorithm). 최적 해를 정확히 구하는 것이 NP-어렵더라도, 최적 해에 가까운 근사 해를 다항 시간에 구할 수 있는 경우가 있다. 근사 비율 \rho는 알고리즘이 산출하는 해의 품질과 최적 해의 비율을 보장한다. 그러나 PCP 정리(Probabilistically Checkable Proofs theorem)에 의해, 특정 문제에서는 일정 근사 비율 이하의 근사도 NP-어렵다.

확률적 알고리즘(randomized algorithm). 무작위성을 활용하여 기대 시간(expected time)에서 효율적인 알고리즘을 설계한다. BPP(Bounded-error Probabilistic Polynomial time) 클래스는 무작위화에 의해 다항 시간에 풀 수 있는 문제의 집합이며, \text{P} \subseteq \text{BPP} \subseteq \text{PSPACE}이다.

7. 딥러닝의 경험적 성공과 복잡도 이론의 긴장

현대 딥러닝의 경험적 성공은 계산 복잡도 이론의 최악 사례 분석과 외견상 긴장 관계에 있다. 신경망 학습의 일반적 정형화는 NP-어려운 비볼록 최적화이나, 확률적 경사 하강법(SGD)은 실제적으로 좋은 해를 빈번히 달성한다.

이 긴장의 해소에 대한 여러 이론적 가설이 제시되어 있다. 첫째, 심층 신경망의 손실 함수 풍경(loss landscape)이 고차원에서 특수한 구조를 가질 수 있다. Choromanska 등(2015)은 스핀 유리(spin glass) 모형과의 유비를 통해, 고차원 손실 함수의 극솟값들이 유사한 값을 갖는 경향이 있음을 보였다. 둘째, 과잉 파라미터화(overparameterization)된 신경망에서는 전역 최솟값(global minimum)에 도달하는 경로가 다수 존재하여, 비볼록성에도 불구하고 경사 하강법이 좋은 해에 수렴할 수 있다. 셋째, 실제 데이터의 분포가 최악 사례 구성과 구조적으로 다를 수 있다.

그러나 이러한 경험적 성공이 복잡도 이론의 한계를 무효화하는 것은 아니다. 복잡도 이론은 최악 사례에 대한 보장을 제공하며, 실제 인스턴스에서의 효율성은 특정 분포적 가정 하에서의 현상이다. 분포가 변화하거나 적대적 인스턴스가 구성되면, 이론적 한계가 실천적으로 드러날 수 있다.

8. 불완전성 정리와 계산 복잡도의 통합적 조망

불완전성 정리와 계산 복잡도 이론은 인공지능의 한계에 대한 상보적 관점을 제공한다.

불완전성 정리는 무엇이 원리적으로 불가능한가를 설정한다. 특정 문제는 어떤 자원을 투입하더라도 해결할 수 없다.

계산 복잡도 이론은 무엇이 실천적으로 불가능한가를 설정한다. 특정 문제는 원리적으로 풀 수 있으나, 필요한 자원이 물리적으로 이용 가능한 양을 초과한다.

인공지능 시스템은 이 이중의 제약 하에서 작동한다. 원리적으로 풀 수 없는 문제(결정 불가능 문제)와, 원리적으로는 풀 수 있으나 실용적으로 풀 수 없는 문제(난해한 문제)가 인공지능의 능력에 대한 두 겹의 한계를 구성한다.

블룸의 가속화 정리(Blum’s speedup theorem, 1967)는 모든 알고리즘에 대해 본질적으로 더 빠른 알고리즘이 존재하는 문제가 있음을 보이며, 이는 최적 알고리즘의 탐색 자체에 한계가 있음을 시사한다. 이러한 결과들은 인공지능이 처리할 수 있는 문제의 범위에 물리적, 수학적, 논리적 차원의 근본적 한계가 다층적으로 존재함을 확인한다.