강의 12

시간 복잡도 — 결정 가능과 실용성 사이

우주의 나이만큼 걸리는 알고리즘은, 사실상 알고리즘이 아니다.

1. 결정 가능만으로는 부족하다

지난 강의들에서 우리는 어떤 언어가 결정 가능한지(decidable)를 끈질기게 따졌다. 그러나 결정 가능하다는 사실은 언젠가는 끝난다는 약속일 뿐, 그 끝이 다음 화요일인지 우주의 열사망 이후인지에 대해서는 한 마디도 하지 않는다. 이론적으로 풀 수 있다는 것과 실제로 답을 받아볼 수 있다는 것 사이에는 천지 차이가 있다.

예컨대 입력 길이 n에 대해 2ⁿ단계가 걸리는 알고리즘이 있다고 하자. n = 100이면 2¹⁰⁰ ≈ 10³⁰이다. 1나노초에 한 단계씩 처리한대도 약 10¹³년이 걸린다. 우주의 추정 나이가 1.4 × 10¹⁰년이니, 우주가 천 번쯤 다시 태어나는 동안 답을 기다려야 한다. 이런 알고리즘을 가지고 “문제가 풀린다”고 말하는 건 윤리적으로 곤란하다.

그래서 이번 강의부터는 자원(resource), 그중에서도 시간이라는 자원을 정량적으로 다룬다. 핵심 질문은 단순하다. 입력이 커질 때 실행 시간이 얼마나 빨리 자라는가?

“실행 시간이 입력에 비례한다”는 말은 충분히 모호하다. 어떤 모델에서, 어떤 입력 크기 척도로, 어떤 점근적 의미로 비례한다는 것인가? 이 강의에서는 이 모호함을 하나씩 정확히 잠가 둔다.

2. 점근 표기법: 빅-O와 그 친척들

알고리즘의 실행 시간을 정확한 단계 수로 비교하는 일은 헛수고에 가깝다. 컴파일러, 기계, 테이프 알파벳에 따라 상수 배수는 얼마든지 달라지기 때문이다. 우리가 신경 쓰는 것은 큰 입력에서의 성장률이다. 그래서 점근 표기(asymptotic notation)가 등장한다.

정의 12.1 (빅-O). 함수 f, g: ℕ → ℝ_≥0에 대해, f(n) = O(g(n))이라는 것은 어떤 양의 상수 c와 자연수 n₀가 존재하여 모든 n ≥ n₀에 대해 f(n) ≤ c · g(n)인 것이다. 즉 “f는 충분히 큰 n에서 g의 상수배 이하”이다.
정의 12.2 (작은-o). f(n) = o(g(n))이란 lim_n→∞ f(n)/g(n) = 0이라는 것이다. f가 g보다 엄격히 느리게 자란다.
정의 12.3 (빅-Ω). f(n) = Ω(g(n))은 g(n) = O(f(n))과 같은 말. 하한이다.
정의 12.4 (빅-Θ). f(n) = Θ(g(n))은 f = O(g)이면서 동시에 f = Ω(g)인 경우. 같은 차수다.

예를 들어 3n³ + 5n + 12 = O(n³) = Θ(n³)이다. n log n = o(n²)이지만 n log n ≠ O(n)이다. 점근 표기에서 로그의 밑은 보통 표시하지 않는다 — 밑이 바뀌면 상수 배수만 달라지므로 빅-O 안에서는 차이가 사라진다.

예 12.5. f(n) = ⌈n/2⌉, g(n) = n이라 하자. 모든 n ≥ 1에 대해 f(n) ≤ n이므로 f = O(n). 반대로 f(n) ≥ n/2 = (1/2)g(n)이므로 f = Ω(n). 따라서 f = Θ(n)이다. 절반을 자르거나 두 배로 늘리는 것은 점근적으로 “같은 일”이다.

3. TIME 클래스와 P

점근 표기를 무기로 들고 시간 복잡도 클래스를 정의한다. 모델은 일단 결정적 단일 테이프 튜링 기계(deterministic single-tape Turing machine)로 못 박는다.

정의 12.6 (실행 시간). 결정적 TM M이 모든 길이 n의 입력에 대해 정확히 t(n)단계 안에 멈춘다면, M의 실행 시간(running time)이 t(n)이라고 한다.
정의 12.7 (TIME 클래스). 자연수 위 함수 t(n)에 대해, TIME(t(n)) = { L | 어떤 결정적 TM이 L을 O(t(n)) 시간에 결정한다 }.

정의 12.8 (다항식 시간 클래스 P). P = ⋃_{k ≥ 1} TIME(n^k). 즉 P는 어떤 상수 k에 대해 O(n^k) 시간에 결정 가능한 언어들의 모임이다.

P가 대단해 보이는 이유는 단순하다. n², n³, 심지어 n¹⁰⁰도 모두 P 안에 있다. 학부생이 보기에 n¹⁰⁰은 끔찍해 보이지만, 이 코스의 관점에서는 “문제는 풀렸다”의 카테고리에 들어간다. 다항식 시간이 곧 “합리적”이라는 약속은 다소 과감하지만, 후술하듯 모델 변경에 강건한(robust) 정의이기 때문에 경계선으로 채택된다.

4. 단일 테이프와 다중 테이프 — 시간의 환율

여기서 자연스러운 의심이 든다. 다중 테이프 TM은 단일 테이프보다 일을 훨씬 효율적으로 한다. 그러면 P의 정의가 모델 선택에 휘둘리는 것 아닌가?

정리 12.9 (시뮬레이션 비용). t(n) ≥ n인 다중 테이프 TM의 모든 t(n) 시간 계산은 동치인 단일 테이프 TM에서 O(t(n)²) 시간 안에 시뮬레이션할 수 있다.

증명 스케치. 다중 테이프의 k개 테이프 내용을 단일 테이프 위에 구분자로 나란히 적어 둔다. 각 테이프의 헤드 위치는 해당 칸 위에 점을 찍어 표시한다. 다중 테이프의 한 단계를 시뮬레이션하려면, 단일 테이프 위를 처음부터 끝까지 한 번 훑어 모든 헤드 위치의 기호를 읽고, 다시 한 번 훑어 갱신한다. 한 번의 훑기는 현재 사용 중인 테이프 길이 — 최대 O(t(n)) — 만큼 걸린다. 다중 테이프의 t(n)단계 시뮬레이션은 O(t(n)) × t(n) = O(t(n)²)단계가 든다. 갱신할 때 칸이 부족하면 뒤 칸들을 한 칸씩 밀어내는데, 이 비용 또한 O(t(n))으로 합산되어 차수를 바꾸지 않는다. ∎

핵심 결과: 다중 테이프에서 다항 시간이면, 단일 테이프에서도 다항 시간이다(차수만 두 배 정도 커진다). 그래서 P의 정의는 테이프 개수에 무관하다. P는 모델의 미세한 차이에 흔들리지 않는, 묵직한 클래스다.

5. 다항식 동치성 — 어떤 모델이든 P는 P

이 강건함은 단지 테이프 개수에 그치지 않는다. 합리적인 모든 결정적 계산 모델은 서로 다항식 시간 동치(polynomial-time equivalent)이다. 즉 한 모델에서 t(n) 시간에 풀리면, 다른 모델에서 t(n)^c 시간 안에 풀린다(c는 상수).

합리적이지 않은 모델? 예컨대 비결정적 모델이나, 한 단계에 무한 비트를 비교하는 가상 모델은 이 동치성에서 빠진다. 비결정성은 다음 강의의 NP 정의에서 등장한다.

대표적인 합리적 모델들:

다중 테이프 TM — 단일 테이프와 다항식 동치 (위 정리).
RAM(랜덤 접근 기계) — C 언어 비슷한 모델. TM과 다항식 동치이며, 이 덕분에 “알고리즘 책의 의사 코드”와 “TM 정의”가 같은 P를 묘사한다.
람다 계산(λ-calculus) — 함수 언어의 수학적 토대. 여전히 다항식 동치(단, 평가 전략에 따라 자세한 차수는 달라진다).
2차원 테이프 TM, 셔블 TM, 큐 기계 — 모두 다항식 동치.

이 동치성은 표면적으로는 코딩 연습처럼 보이지만, 그 결과는 묵직하다. 다항식 시간이라는 개념은 모델에 의존하지 않는 수학적 대상이다. 양자 모델까지 포함하면 이야기가 달라지지만, 고전 결정적 모델 안에서는 이 동치성이 P를 진정한 “자연 클래스”로 만든다.

6. P 안에 사는 친구들

구체적인 예를 셋 보자. 모두 P에 속함을 알고리즘으로 보인다.

예 12.10 (PATH). PATH = { ⟨G, s, t⟩ | G는 방향 그래프이고 s에서 t로 가는 경로가 존재한다 }. 결정 알고리즘은 너비 우선 탐색(BFS): s에서 시작해 도달 가능한 정점을 차례로 마킹한다. 정점이 새로 마킹될 때마다 그 이웃을 큐에 넣는다. t가 마킹되면 수락, 큐가 비면 거부. 각 간선은 상수 번 검사되므로 시간은 O(|V| + |E|) — 충분히 다항이다. 따라서 PATH ∈ P.

예 12.11 (RELPRIME). RELPRIME = { ⟨a, b⟩ | a와 b는 서로소 }. 유클리드 알고리즘은 gcd(a, b) = gcd(b, a mod b)를 반복한다. 한 단계마다 작은 수가 적어도 절반 이하로 줄어든다는 사실(피보나치 수열의 마술)을 보이면, 단계 수는 O(log min(a, b))이다. 입력 길이 n은 a와 b의 비트 수의 합이므로, 단계 수는 O(n)이고, 각 단계의 나머지 연산도 다항. 따라서 RELPRIME ∈ P.

예 12.12 (CFL 인식). 임의의 문맥 자유 언어 L에 대해 L ∈ P이다. 증명 스케치: L의 문법을 촘스키 표준형(CNF)으로 변환한 뒤, CYK 동적 계획법을 돌린다. 길이 n 입력 w의 모든 부분 문자열 w[i..j]에 대해 그것을 유도할 수 있는 변수 집합을 표 한 칸에 채운다. 부분 문자열은 O(n²)개이고, 각 칸을 채우려면 분할점 j − i + 1가지를 보아야 하므로 총 시간은 O(n³)이다. 그러므로 모든 CFL은 P에 속한다.

세 예의 공통점은 단순하다. 알고리즘이 입력 크기에 대해 다항 차수 안에 끝나면 P. 우리가 “알고리즘”이라고 부를 때 흔히 떠올리는 것이 사실 P를 슬쩍 가리키고 있던 셈이다.

7. P는 “합리적 시간 안에 풀리는” 문제

실용적 명제(thesis)로서, P는 다음과 같이 받아들여진다.

실용 명제 (코브햄–에드몬즈). 합리적 결정적 계산 모델에서 P는 “현실적으로 풀 수 있는” 문제 클래스와 거의 일치한다.

이 명제는 정리가 아니다. n¹⁰⁰은 다항식이지만 현실적이지 않고, 1.0001ⁿ은 지수지만 작은 입력에서는 빠르다. 그럼에도 이 등식이 50년 넘게 살아남은 데는 두 가지 이유가 있다. 첫째, P 안의 자연 문제들은 거의 예외 없이 작은 차수의 다항식 알고리즘을 가진다 — n¹⁰⁰는 인공적이다. 둘째, P 바깥인 문제들은 반대로 비현실적인 시간을 요구하는 경우가 압도적이다. 경계선의 좌우는 실제로 잘 갈라져 있다.

그래서 우리는 다음 강의로 자연스레 넘어간다. P 바깥에 무엇이 있는가? 결정 가능하지만 다항 시간이 아닌 듯한 문제 — 만족 가능성, 클리크, 해밀턴 경로 — 가 줄지어 등장한다. 이들을 묶는 클래스가 NP이며, NP의 본성을 묻는 P = NP? 질문이 다음 강의의 무대를 연다.