4.23 계산 복잡도 이론의 기초: P 클래스와 NP 클래스

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

계산 가능성 이론(Computability Theory)이 “무엇이 계산 가능한가?“를 묻는다면, 계산 복잡도 이론(Computational Complexity Theory)은 “얼마나 효율적으로 계산 가능한가?“를 묻는다. 문제가 알고리즘적으로 해결 가능하더라도, 필요한 시간이나 공간 자원이 비현실적으로 크다면 실용적으로 해결 불가능할 수 있다.

2. 시간 복잡도 클래스

2.1 DTIME과 NTIME

$\text{DTIME}(f(n))$ : 입력 길이 $n$ 에 대해 $O(f(n))$ 시간에 정지하는 결정적 튜링 기계(DTM)에 의해 결정되는 언어의 클래스.

$\text{NTIME}(f(n))$ : 입력 길이 $n$ 에 대해 계산 트리의 모든 경로가 $O(f(n))$ 단계 이내에 정지하는 비결정적 튜링 기계(NTM)에 의해 결정되는 언어의 클래스.

3. P 클래스

3.1 정의

$\text{P} = \bigcup_{k \geq 0} \text{DTIME}(n^k)$

P는 결정적 튜링 기계에 의해 다항 시간(Polynomial Time)에 결정되는 언어의 클래스이다.

P 클래스의 의의

P 클래스는 “효율적으로 해결 가능한 문제“의 형식적 정의로 간주된다. 이 동일시(코보엄-에드몬즈 명제, Cobham-Edmonds Thesis)는 완전하지는 않으나 널리 수용되는 관례이다.

P에 속하는 문제의 예

경로 존재(Path Existence): 그래프에서 두 정점 사이에 경로가 존재하는지. BFS/DFS에 의해 $O(\vert V \vert + \vert E \vert)$ .
정렬(Sorting): $n$ 개의 원소를 정렬. $O(n \log n)$ .
소수 판별(Primality Testing): 주어진 수가 소수인지 판별. AKS 알고리즘에 의해 다항 시간. 아그라왈, 카얄, 삭세나(Agrawal, Kayal, Saxena, 2004).
선형 프로그래밍(Linear Programming): 카치얀(Khachiyan, 1979)의 타원체 방법에 의해 다항 시간.
문맥 자유 언어 인식: CYK 알고리즘에 의해 $O(n^3)$ .

NP 클래스

정의

$\text{NP} = \bigcup_{k \geq 0} \text{NTIME}(n^k)$

NP는 비결정적 튜링 기계에 의해 다항 시간에 결정되는 언어의 클래스이다.

3.2 검증자(Verifier) 기반 정의

동등한 정의: 언어 $L \in \text{NP}$ 인 것은 다항 시간 결정적 검증자(Verifier) $V$ 가 존재하여:

$w \in L \iff \exists c \in \{0,1\}^{p(\vert w \vert)}: V(w, c) = 1$

여기서 $c$ 는 증명서(Certificate) 또는 증인(Witness)이며, $p$ 는 다항식이다.

즉, NP 문제는 “해(Solution)를 찾는 것은 어려울 수 있으나, 해가 주어지면 그 올바름을 다항 시간에 검증할 수 있는” 문제의 클래스이다.

NP에 속하는 문제의 예

충족 가능성(SAT, Satisfiability): 명제 논리 식이 만족 가능한지. 만족 가능 할당이 증명서.
해밀턴 경로(Hamiltonian Path): 그래프에서 모든 정점을 정확히 한 번 방문하는 경로가 존재하는지. 경로 자체가 증명서.
정수 분해(Integer Factorization): 합성수의 비자명 인수의 존재. 인수가 증명서.
그래프 착색(Graph Coloring): $k$ -색 착색이 가능한지. 착색 자체가 증명서.
부분합 문제(Subset Sum): 집합의 부분집합 중 합이 목표값과 같은 것이 존재하는지.

P vs NP 문제

물음

$\text{P} \stackrel{?}{=} \text{NP}$

P = NP인가? 즉, 해의 올바름을 다항 시간에 검증할 수 있는 모든 문제가 다항 시간에 해를 찾을 수 있는가?

3.3 현재 상태

P vs NP 문제는 컴퓨터 과학에서 가장 중요한 미해결 문제이며, 클레이 수학 연구소(Clay Mathematics Institute)가 지정한 밀레니엄 문제(Millennium Prize Problems) 7개 중 하나이다. 상금은 100만 미국 달러이다.

대부분의 컴퓨터 과학자는 $\text{P} \neq \text{NP}$ 라고 추측하나, 이를 증명하지 못하고 있다.

3.4 P ≠ NP의 의미

$\text{P} \neq \text{NP}$ 가 참이면, 해의 존재를 효율적으로 검증할 수 있는 문제 중 해를 효율적으로 찾을 수 없는 문제가 존재한다. 이는 “창의적 발견은 기계적 검증보다 본질적으로 어렵다“는 직관을 형식화한 것이다.

4. NP 완전성(NP-Completeness)

4.1 다항 시간 환원(Polynomial-Time Reduction)

언어 $A$ 가 언어 $B$ 로 다항 시간 다대일 환원 가능(Polynomial-Time Many-One Reducible)하다 함은, 다항 시간에 계산 가능한 함수 $f$ 가 존재하여 모든 $w$ 에 대해 $w \in A \iff f(w) \in B$ 인 것이다. 이를 $A \leq_p B$ 로 표기한다.

4.2 NP 완전 문제의 정의

언어 $L$ 이 NP 완전(NP-Complete)이라 함은:

$L \in \text{NP}$
모든 $L' \in \text{NP}$ 에 대해 $L' \leq_p L$

NP 완전 문제는 NP 중에서 가장 “어려운” 문제이며, 어떤 NP 완전 문제라도 다항 시간에 해결할 수 있으면 모든 NP 문제가 다항 시간에 해결 가능하다( $\text{P} = \text{NP}$ ).

4.3 쿡-레빈 정리(Cook-Levin Theorem)

정리(Cook, 1971; Levin, 1973): SAT(명제 논리의 충족 가능성 문제)는 NP 완전이다.

이 정리는 최초의 NP 완전성 결과이며, 이후 카프(Richard Karp, 1972)가 SAT로부터의 환원에 의해 21개의 추가 문제가 NP 완전임을 보였다.

5. 인공지능에 대한 함의

5.1 AI 문제의 NP 완전성

인공지능에서 다루는 다수의 핵심 문제가 NP 완전이다:

제약 만족 문제(Constraint Satisfaction Problem, CSP)
계획 문제(Planning Problem)
진단 문제(Diagnosis Problem)
스케줄링 문제(Scheduling Problem)

$\text{P} \neq \text{NP}$ 가 참이면, 이 문제들에 대한 다항 시간 알고리즘은 존재하지 않으며, 인공지능은 휴리스틱, 근사 알고리즘, 확률적 방법 등의 실용적 전략에 의존해야 한다.

5.2 학습의 계산 복잡도

신경망 학습의 일부 문제—예를 들어 최적 가중치의 탐색—도 NP 난해(NP-Hard)임이 알려져 있다. 현실에서 경사 하강법이 효과적으로 작동하는 이유의 이론적 해명은 활발한 연구 주제이다.

P 클래스와 NP 클래스의 구분은 계산의 효율성에 관한 가장 근본적인 이론적 프레임워크이며, 이 프레임워크가 인공지능을 포함한 모든 알고리즘 기반 문제 해결의 이론적 한계를 규정한다.