·수학

복잡도는 운명인가? P-NP와 시스템 전반의 한계

P vs NP 문제는 단순한 이론적 호기심이 아니다. 암호화, AI, 금융, 그리고 우리가 만드는 모든 시스템의 근본 한계를 묻는다.

#수학#컴퓨터과학#복잡도이론

복잡도는 운명인가?

어떤 문제는 쉽게 풀립니다. 두 수를 더하는 일, 리스트를 정렬하는 일, 최단 경로를 찾는 일. 그런데 어떤 문제는 아무리 빠른 컴퓨터를 동원해도 답을 구하는 데 우주의 나이보다 오랜 시간이 걸립니다. 체스판 위의 모든 경우의 수, 수백 개 도시를 잇는 최소 비용 경로, 수억 비트의 암호키.

이 차이는 단순히 하드웨어의 문제일까요? 아니면 그보다 더 근본적인, 계산 자체의 한계일까요?

컴퓨터과학에서 가장 오래된, 그리고 여전히 미해결인 질문이 바로 여기서 출발합니다. P vs NP 문제. 클레이 수학연구소가 선정한 밀레니엄 7대 난제 중 하나이며, 해결자에게 100만 달러의 상금이 걸려 있습니다. 하지만 그 의미는 상금보다 훨씬 심대합니다. 이것은 우리가 만들 수 있는 모든 시스템의 근본 한계를 묻는 질문입니다.

제1장. P와 NP: 풀 수 있다는 것의 두 가지 의미

1. 복잡도 클래스란 무엇인가?

복잡도 이론(Complexity Theory)은 문제를 "얼마나 어려운가"에 따라 분류하는 학문입니다. 여기서 "어렵다"는 것은 풀기 위해 필요한 시간(혹은 공간)이 입력 크기에 따라 어떻게 증가하는가로 정의됩니다.

입력 크기를 nn이라 할 때, 알고리즘의 시간복잡도가 다항식(polynomial) 이내라면

T(n)=O(nk)for some k>0T(n) = O(n^k) \quad \text{for some } k > 0

이 알고리즘은 효율적이라고 간주합니다. 반대로, 지수 시간

T(n)=O(2n)T(n) = O(2^n)

이 필요하다면, nn이 조금만 커져도 계산은 사실상 불가능해집니다.

2. P 클래스: 다항 시간에 풀리는 문제

**P(Polynomial time)**는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 결정 문제들의 집합입니다. 쉽게 말해, "빠르게 답을 찾을 수 있는" 문제들입니다.

대표적인 예:

  • 정렬(Sorting): O(nlog⁡n)O(n \log n)
  • 최단 경로(Dijkstra): O((V+E)log⁡V)O((V + E) \log V)
  • 소수 판별(AKS): O((log⁡n)12)O((\log n)^{12})
  • 선형 프로그래밍(Simplex): 평균적으로 다항 시간

3. NP 클래스: 다항 시간에 검증할 수 있는 문제

**NP(Nondeterministic Polynomial time)**는 주어진 답이 옳은지를 다항 시간 내에 검증할 수 있는 문제들의 집합입니다. 찾기는 어려워도, 답을 보여주면 맞는지 확인하는 건 쉬운 문제들입니다.

직관적인 예: 1000개의 도시를 거치는 외판원 경로가 "1만 km 이하인가?"라는 질문. 답을 구하는 건 어렵지만, 누군가 경로를 보여주면 거리를 더해서 확인하는 건 빠릅니다.

형식적으로는, 인증자(verifier) VV가 존재하여

x∈L  ⟺  ∃y:∣y∣≤poly(∣x∣) and V(x,y)=1x \in L \iff \exists y : |y| \leq \text{poly}(|x|) \text{ and } V(x, y) = 1

을 만족하는 언어 LL의 집합이 NP입니다. 여기서 yy는 "증거(witness)" 혹은 "인증서(certificate)"입니다.

분명한 것은, P⊆NP\mathbf{P} \subseteq \mathbf{NP}입니다. 빠르게 풀 수 있다면 당연히 빠르게 검증도 할 수 있으니까요. 핵심 질문은 그 역, NP⊆P\mathbf{NP} \subseteq \mathbf{P}, 즉 P=NP\mathbf{P} = \mathbf{NP}인지입니다.

제2장. NP-완전과 NP-하드: 가장 어려운 문제들

1. 환원(Reduction): 문제의 상대적 난이도

복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 **다항 시간 환원(polynomial-time reduction)**을 사용합니다. 문제 AA가 문제 BB로 환원된다는 것(A≤pBA \leq_p B)은, BB를 풀 수 있다면 AA도 다항 시간에 풀 수 있다는 의미입니다.

A≤pB  ⟹  difficulty(A)≤difficulty(B)A \leq_p B \implies \text{difficulty}(A) \leq \text{difficulty}(B)

이 관계를 통해 "모든 NP 문제만큼 어려운" 문제들을 정의할 수 있습니다.

2. NP-완전(NP-Complete): NP의 가장 어려운 문제

어떤 문제 CC가 NP-완전이려면 두 조건을 만족해야 합니다.

  1. C∈NPC \in \mathbf{NP} (검증은 다항 시간에 가능)
  2. 모든 A∈NPA \in \mathbf{NP}에 대해 A≤pCA \leq_p C (NP의 모든 문제가 CC로 환원 가능)

즉, NP-완전 문제 하나를 다항 시간에 풀 수 있다면, P=NP\mathbf{P} = \mathbf{NP}가 됩니다.

3. 대표적인 NP-완전 문제들

SAT (Boolean Satisfiability Problem)

쿡-레빈 정리(Cook-Levin Theorem, 1971)로 최초로 NP-완전이 증명된 문제입니다. 변수 x1,x2,…,xnx_1, x_2, \ldots, x_n에 대한 논리식이 주어질 때, 전체를 참으로 만드는 변수 값의 조합이 존재하는가?

φ=(x1∨¬x2∨x3)∧(¬x1∨x2)∧(x2∨¬x3)\varphi = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2) \wedge (x_2 \vee \neg x_3)

위 수식을 참으로 만드는 x1,x2,x3x_1, x_2, x_3의 조합을 찾는 문제입니다. 검증은 쉽지만, nn개 변수의 경우 최대 2n2^n가지 조합을 확인해야 할 수 있습니다.

TSP (Travelling Salesman Problem)

nn개의 도시를 정확히 한 번씩 방문하고 출발지로 돌아오는 경로 중, 총 거리가 kk 이하인 경로가 존재하는가? 도시의 수가 늘어날수록 가능한 경로 수는 (n−1)!/2(n-1)!/2로 폭발적으로 증가합니다. n=20n = 20이면 약 6×10166 \times 10^{16}가지, n=50n = 50이면 우주의 원자 수보다 많습니다.

배낭 문제(Knapsack Problem)

무게 제한 WW의 배낭에 nn개의 물건(각각 무게 wiw_i, 가치 viv_i)을 담을 때, 가치 합이 VV 이상이 되는 조합이 존재하는가?

maximize∑i=1nvixisubject to∑i=1nwixi≤W,xi∈{0,1}\text{maximize} \sum_{i=1}^{n} v_i x_i \quad \text{subject to} \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \{0, 1\}

물류, 금융, 자원 배분 등 산업 전반에 걸쳐 실제로 등장하는 구조입니다.

**NP-하드(NP-Hard)**는 조건 2만 만족하는 경우입니다. NP에 속하지 않을 수도 있어, NP-완전보다 더 어려울 수 있습니다. 최적화 버전의 TSP(최소 거리 경로를 직접 구하는 문제)가 대표적입니다.

제3장. P = NP라면 세상이 어떻게 바뀌는가

1. 암호화 체계의 붕괴

현대 암호학은 NP 문제의 어려움 위에 세워져 있습니다.

RSA 암호는 두 소수의 곱 N=p×qN = p \times q를 공개하되, pp와 qq를 알아내는 것이 극도로 어렵다는 사실에 기반합니다. 정수 분해(Integer Factorization) 문제는 아직 NP-완전임이 증명되진 않았지만, 다항 시간 알고리즘도 알려져 있지 않습니다.

만약 P=NP\mathbf{P} = \mathbf{NP}라면:

  • RSA, ECC, Diffie-Hellman 등 현재 사용 중인 대부분의 공개키 암호가 의미를 잃습니다.
  • HTTPS, 금융 거래, 비밀번호 저장, 디지털 서명 모두 안전하지 않게 됩니다.
  • 인터넷의 보안 인프라 전체가 재설계되어야 합니다.

2. AI와 최적화의 혁명

반대로, P=NP\mathbf{P} = \mathbf{NP}는 놀라운 가능성을 열기도 합니다.

기계 학습의 핵심 작업인 모델 학습(training)은 본질적으로 고차원 최적화 문제입니다. NP-완전 문제를 효율적으로 풀 수 있다면:

  • 완벽한 단백질 구조 예측
  • 최적의 신약 분자 설계
  • 전력망·물류망의 전역 최적화
  • 복잡계 시뮬레이션의 실시간 처리

이 가능해집니다. 특히, 증명 탐색 자체가 NP 문제에 해당하므로, 수학의 모든 미해결 문제를 자동으로 증명하는 시스템이 등장할 수도 있습니다.

3. 그러나 대부분의 전문가는 P ≠ NP를 믿는다

2012년 Scott Aaronson의 조사에 따르면, 컴퓨터과학자의 80% 이상이 P≠NP\mathbf{P} \neq \mathbf{NP}일 것이라 믿고 있습니다. 직관적으로, "답을 찾는 것"과 "답을 확인하는 것"이 근본적으로 다른 행위라고 느끼기 때문입니다. 하지만 이것은 아직 증명되지 않은 직관입니다.

제4장. 현실에서의 대응: 완벽함을 포기하고 충분히 좋은 답을 구하다

NP-완전 문제는 풀 수 없는 문제가 아닙니다. 단지 최적 해를 항상 빠르게 구할 수 없을 뿐입니다. 현실에서는 세 가지 전략으로 대응합니다.

1. 근사 알고리즘(Approximation Algorithms)

최적 해에서 일정 비율 이내로 보장된 해를 다항 시간에 구합니다. 예를 들어, TSP의 크리스토피데스(Christofides) 알고리즘은 최적 해의 32\frac{3}{2} 배 이내인 경로를 O(n3)O(n^3)에 구합니다.

근사비(approximation ratio) ρ\rho에 대해:

ALG(x)≤ρ⋅OPT(x)\text{ALG}(x) \leq \rho \cdot \text{OPT}(x)

를 보장하는 알고리즘이 존재한다면, 그 문제는 ρ\rho-근사 가능(approximable)합니다.

2. 휴리스틱과 메타휴리스틱

최적 해 보장은 없지만, 실제로 잘 동작하는 경험 기반 알고리즘들입니다.

  • 유전 알고리즘(Genetic Algorithm): 진화의 원리를 모방
  • 시뮬레이티드 어닐링(Simulated Annealing): 냉각 과정에서의 에너지 최소화를 모방
  • 개미 군집 최적화(Ant Colony Optimization): 페로몬 경로를 통한 집단 탐색

이들은 이론적 보장은 없지만, 물류·스케줄링·회로 설계 등 산업 현장에서 매일 쓰입니다.

3. 양자 컴퓨팅의 가능성과 한계

양자 컴퓨터는 중첩(superposition)과 얽힘(entanglement)을 활용하여 특정 문제를 극적으로 빠르게 풉니다.

Grover 알고리즘: 비구조적 탐색에서 고전 컴퓨터의 O(N)O(N)을 O(N)O(\sqrt{N})으로 단축. Shor 알고리즘: 정수 분해를 다항 시간에 해결. RSA를 무력화.

하지만 양자 컴퓨팅은 P=NP\mathbf{P} = \mathbf{NP}를 해결하지 않습니다. 양자 컴퓨터가 다루는 복잡도 클래스 BQP(Bounded-error Quantum Polynomial time)는 NP와 교차하지만, NP를 완전히 포함하지 않는 것으로 추정됩니다. 즉, 양자 컴퓨터도 모든 NP-완전 문제를 효율적으로 풀 수는 없습니다.

제5장. 계산 복잡도는 인식론적 한계다

1. 알 수 없음이 아니라, 알 수 없다는 것을 아는 것

P-NP 문제는 단순히 컴퓨터가 빠른지 느린지의 문제가 아닙니다. 이것은 어떤 종류의 진리는 근본적으로 탐색 비용이 크다는 사실의 수학적 표현입니다.

괴델의 불완전성 정리가 수학적 진리의 도달 불가능성을 보였다면, 복잡도 이론은 계산적 진리의 도달 비용을 다룹니다.

어떤 시스템이 그 안에서 최적해를 찾으려면, 시스템 자체의 규모에 비례하는 탐색이 필요할 수 있습니다. 이것은 하드웨어로 극복할 수 있는 한계가 아니라, 문제의 구조 자체에 내재된 한계입니다.

2. 공학적 함의: 우리가 설계하는 모든 시스템

소프트웨어 엔지니어링, 데이터베이스 쿼리 최적화, 신경망 훈련, 컴파일러 설계, 게임 AI. 이 모든 것의 배후에는 NP-완전 혹은 NP-하드 문제가 잠재되어 있습니다.

일정 스케줄링(Job Scheduling), 의존성 해소(Dependency Resolution), 쿼리 플래닝(Query Planning). 우리가 "좋은 설계"라고 부르는 것들의 상당수는 NP-하드 문제를 어떻게 회피하거나 완화하는가에 대한 답입니다.

복잡도를 이해한다는 것은, 내가 만드는 시스템이 어디서 벽에 부딪힐지를 미리 아는 것입니다.

맺으며: 한계를 아는 것이 지혜다

"어떤 것들은 단지 어려운 것이 아니라, 근본적으로 어렵다."

복잡도 이론이 우리에게 가르쳐주는 가장 중요한 교훈은 패배가 아닙니다.

무한한 자원만 있으면 모든 것을 풀 수 있다는 환상을 걷어내고, 문제의 구조 자체를 이해하게 만든다는 것. 그것이 핵심입니다.

어떤 문제는 근사로도 충분합니다. 어떤 문제는 작은 입력에서만 정확해도 됩니다. 어떤 문제는 문제 자체를 재정의해야 합니다.

이 판단을 가능하게 하는 것이 복잡도에 대한 이해입니다. 한계를 모르면, 한계 앞에서 무너집니다. 한계를 알면, 한계를 우회하거나 재정의할 수 있습니다.

P vs NP는 여전히 미해결입니다. 하지만 그 질문이 존재한다는 사실만으로도, 우리는 계산의 세계에 얼마나 깊은 구조가 있는지를 엿볼 수 있습니다. 그리고 그 구조를 이해하려는 노력이, 더 정직하고 더 견고한 시스템을 만드는 출발점이 됩니다.

복잡도는 운명일지 모릅니다. 하지만 운명을 아는 자는 그것과 더 잘 싸울 수 있습니다.

글이 도움이 됐다면 GitHub에서 이야기 나눠요.