📚 지식 노트

문제를 언어로 보기

계산 이론은 "문제"를 아주 좁게 정의하는 데서 시작한다. 입력은 글자들을 늘어놓은 문자열이고, 답은 예/아니오 하나다. 이런 문제를 판정 문제라 한다. "이 이진수는 3의 배수인가", "이 괄호는 짝이 맞는가", "이 프로그램은 멈추는가" 모두 판정 문제다. 그러면 문제 하나는 "예"가 나오는 문자열을 모두 모은 집합과 같아진다. 이 집합을 언어라 부른다. 문제를 푼다는 것은 주어진 문자열이 그 언어에 속하는지 판정하는 것이다.

너무 좁아 보이지만 대부분의 문제가 이 꼴로 바뀐다. "최단 경로의 길이는?"은 "길이 k 이하의 경로가 있는가?"를 k를 바꿔 가며 물으면 된다. 이렇게 정해 두면 서로 다른 기계(유한 오토마타, 스택 달린 기계, 튜링 기계)를 "어떤 언어까지 판정할 수 있나"라는 한 잣대로 비교할 수 있다. 이 노트는 약한 기계에서 강한 기계로 올라간다.

유한 오토마타: 3의 배수 판정기

결정적 유한 오토마타(DFA)는 가장 단순한 기계다. 상태가 유한 개 있고, 입력을 왼쪽부터 한 글자씩 읽으며 "지금 상태 + 읽은 글자 → 다음 상태" 표대로 옮겨 간다. 다 읽었을 때 받아들이는 상태에 있으면 예다. 되돌아가 다시 읽거나 따로 적어 둘 메모리가 없다. 기억은 오직 "지금 어느 상태인가"뿐이다.

그래도 꽤 많은 일을 한다. 이진수가 3의 배수인지 보려면 수 전체를 기억할 필요가 없다. 지금까지 읽은 수를 3으로 나눈 나머지 r만 알면 된다. 이진수 뒤에 비트 b를 붙이면 값이 2배가 되고 b가 더해지므로, 새 나머지는 (2r + b) mod 3이다. 나머지 0·1·2가 곧 상태 세 개다. 입력이 백만 자리여도 기계는 상태 셋으로 끝까지 읽는다.

DFA는 실제로 흔하다. 렉서가 토큰을 자르는 규칙, 네트워크 프로토콜의 상태, 자판기·신호등 제어, 게임 캐릭터의 상태 기계가 모두 이 꼴이다. 받아들이는 언어가 DFA로 판정되는 언어를 정규 언어라 한다.

NFA와 부분집합 구성

비결정적 유한 오토마타(NFA)는 한 상태에서 같은 글자로 갈 수 있는 곳이 여럿이어도 되고, 갈 곳이 없어도 된다. 갈림길마다 기계가 복제되어 모든 길을 동시에 가 본다고 생각하면 된다. 그 가운데 한 길이라도 받아들이는 상태에서 끝나면 예다. "01로 끝나는 문자열"이라면 NFA는 q0에서 맴돌다가 "여기서부터가 끝의 01이다"라고 추측해 q1로 건너가면 된다. 추측이 틀린 복제본은 그냥 사라진다.

추측하는 기계가 더 강할 것 같지만 그렇지 않다. 부분집합 구성은 "지금 살아 있는 NFA 상태들의 집합"을 DFA의 상태 하나로 삼는다. NFA 상태가 n개면 집합은 최대 2ⁿ개라 DFA는 유한하다. 이 예에서는 가능한 집합 8개 가운데 시작에서 닿는 것이 3개뿐이다. 그래서 NFA와 DFA는 같은 언어를 판정한다. NFA는 사람이 짜기 쉽고, DFA는 기계가 돌리기 쉽다는 차이만 있다. 다만 최악에는 DFA 상태가 정말 2ⁿ개까지 불어난다.

정규 표현식과 실제 regex

정규 표현식은 정규 언어를 글로 적는 방법이다. 재료는 셋뿐이다. 이어 붙이기(ab), 고르기(a|b), 0번 이상 반복(a*). 정규 표현식으로 적을 수 있는 언어와 유한 오토마타로 판정할 수 있는 언어가 정확히 같다(클레이니 정리). 그래서 regex 엔진은 식을 NFA로 바꾼 뒤, 살아 있는 상태 집합을 들고 글자마다 한 번씩 갱신하는 방식(톰프슨 방식)으로 입력 길이에 비례하는 시간에 맞출 수 있다.

그런데 Perl·PCRE·Python·Ruby 같은 많은 엔진은 갈림길에서 한쪽을 먼저 끝까지 가 보고 실패하면 되돌아오는 백트래킹을 쓴다. 보통은 빠르지만, 갈림길이 겹겹이 쌓인 식에서는 시도할 경우가 지수로 는다. 아래 그림의 a?ⁿaⁿ을 aⁿ에 맞추면 n = 20에서 백트래킹은 12,582,911걸음, NFA 동시 추적은 441걸음이다. 서버가 사용자 입력에 regex를 돌리다 멈추는 ReDoS가 이 현상이다.

실제 regex에는 이론의 정규 표현식에 없는 기능도 있다. 대표가 역참조다. (a+)b\1은 "앞에서 잡은 a 묶음과 똑같은 것이 b 뒤에 다시 나온다"는 뜻인데, 이것은 같은 길이를 기억해야 해서 유한 상태로는 판정할 수 없다. 역참조가 들어간 식은 더 이상 정규 언어가 아니고, 역참조가 있는 regex 맞추기는 일반적으로 NP-완전이다. 역참조를 아예 지원하지 않는 엔진(RE2 계열)이 있는 이유다.

펌핑 보조정리: 괄호 짝은 DFA로 못 센다

DFA가 못 하는 일도 있다. 괄호 짝 맞추기가 대표다. 여는 괄호를 몇 개 열었는지 세어야 닫는 괄호와 맞춰 볼 수 있는데, 연 개수에는 상한이 없다. 상태가 k개인 DFA에 여는 괄호 k개를 넣으면, 시작 상태까지 k + 1개의 상태를 지나므로 비둘기집 원리에 따라 어떤 상태를 두 번 지난다. 깊이 i일 때와 깊이 j일 때 같은 상태라면, 뒤에 닫는 괄호 i개를 붙인 두 문자열을 기계는 구별할 수 없다. 하나는 짝이 맞고 하나는 안 맞는데도 같은 답을 낸다.

이 논리를 일반화한 것이 펌핑 보조정리다. 정규 언어라면, 충분히 긴 문자열에는 상태 반복이 만든 고리 구간이 있고 그 구간을 0번, 2번, 3번… 되풀이(펌핑)해도 여전히 언어에 속해야 한다. aⁿbⁿ(같은 수의 a 뒤에 b)이나 괄호 짝 언어는 a 구간만 늘리면 짝이 깨지므로 정규가 아니다. "정규 표현식으로 HTML을 제대로 파싱할 수 없다"는 말도 같은 이유다.

문맥 자유 문법과 푸시다운 오토마타

괄호를 세려면 기억이 더 필요하다. 가장 적게 더한 것이 스택 하나다. 푸시다운 오토마타(PDA)는 유한 오토마타에 스택을 붙인 기계다. 여는 괄호를 읽으면 스택에 넣고 닫는 괄호를 읽으면 하나 뺀다. 빈 스택에서 빼려 하면 거부하고, 끝까지 읽었을 때 스택이 비었으면 받아들인다. 스택은 깊이가 무한할 수 있어 DFA의 벽을 넘는다.

PDA가 판정하는 언어를 글로 적는 방법이 문맥 자유 문법(CFG)이다. S → (S)S | ε처럼 기호 하나를 다른 줄로 바꿔 쓰는 규칙의 모음이다. 왼쪽이 기호 하나뿐이라 주변(문맥)과 상관없이 바꿀 수 있다는 뜻에서 "문맥 자유"다. 프로그래밍 언어의 문법(식, 문장, 중첩된 블록)이 거의 다 이 꼴이고, 파서가 CFG로 소스 코드를 구문 트리로 만든다. 렉서는 정규 언어, 파서는 문맥 자유 언어를 맡는 셈이다. 실제 파서 이야기는 컴파일러 노트에 있다.

촘스키 계층

지금까지의 언어들은 포함 관계로 줄을 선다. 언어학자 노엄 촘스키가 문법의 꼴로 나눈 네 층이라 촘스키 계층이라 부른다. 안쪽부터 정규 언어(유한 오토마타), 문맥 자유 언어(푸시다운 오토마타), 문맥 의존 언어(입력 길이만큼의 테이프만 쓰는 튜링 기계, 선형 유계 오토마타), 재귀 열거 언어(튜링 기계)다. 각 층은 바로 안쪽 층보다 엄격히 크다. aⁿbⁿ은 문맥 자유지만 정규가 아니고, a·b·c의 개수가 모두 같은 aⁿbⁿcⁿ은 스택 하나로는 두 개를 함께 셀 수 없어 문맥 자유가 아니다.

튜링 기계: 이진수에 1 더하기

1936년 앨런 튜링은 "사람이 종이와 연필로 기계적으로 계산하는 모습"을 그대로 본뜬 기계를 내놓았다. 튜링 기계는 칸으로 나뉜 끝없는 테이프, 한 칸을 읽고 쓰는 머리, 유한 개의 상태, 규칙표로 이루어진다. 규칙은 "상태 q에서 기호 s를 읽으면 s'를 쓰고, 왼쪽이나 오른쪽으로 한 칸 가고, 상태 q'가 된다"는 꼴이다. PDA와 달리 테이프를 마음대로 오가며 읽고 고칠 수 있다.

이진수에 1을 더하는 기계는 상태 둘과 규칙 네 줄이면 된다. 먼저 오른쪽 끝까지 가고, 돌아오면서 1은 0으로 바꾸며 올림을 넘기다가, 처음 만난 0(또는 왼쪽 끝의 빈칸)을 1로 바꾸고 멈춘다. 손으로 하는 덧셈과 똑같다.

이렇게 단순한데도 튜링 기계는 지금의 어떤 컴퓨터가 하는 계산도 흉내 낼 수 있다. 더 나아가 다른 튜링 기계의 규칙표를 테이프로 받아 그대로 실행하는 보편 튜링 기계도 있다. 프로그램을 데이터로 읽어 실행하는 오늘날 컴퓨터의 발상이 여기서 나왔다.

처치–튜링 논제

튜링과 같은 해(1936년)에 알론조 처치는 람다 계산으로, 다른 이들은 재귀 함수로 "계산할 수 있다"를 정의했다. 생김새는 전혀 다르지만 이 모형들이 계산하는 함수의 집합은 모두 같다고 증명됐다. 서로가 서로를 흉내 낼 수 있기 때문이다. 메모리가 끝없다고 치면 실제 프로그래밍 언어도 같은 힘을 가진다(튜링 완전).

처치–튜링 논제는 한 걸음 더 나아가, 사람이 생각하는 "기계적 절차로 계산할 수 있다"는 직관적 개념이 바로 이 집합이라고 주장한다. 직관을 수학으로 증명할 수는 없으니 정리가 아니라 논제다. 그래도 지금까지 반례는 없다. 양자 컴퓨터도 계산할 수 있는 것의 범위는 넓히지 못하고, 넓힐 수 있다고 기대되는 것은 속도다(아래 마지막 절).

계산 가능성: 정지 문제, 환원, 라이스 정리

튜링 기계로도 판정할 수 없는 문제가 있다. 가장 유명한 것이 정지 문제다. "프로그램 P에 입력 x를 주면 언젠가 멈추는가?"를 모든 P와 x에 대해 바르게 답하는 프로그램 H는 없다. 증명은 칸토어의 대각선 논법과 같은 모양이다. H가 있다고 하자. 그러면 프로그램 D를 만들 수 있다. D는 프로그램 P를 받아 H로 "P에 P 자신을 주면 멈추는가"를 묻고, 멈춘다고 하면 일부러 무한 루프에 빠지고, 안 멈춘다고 하면 바로 멈춘다. 이제 D에 D를 주면, 멈추면 안 멈춰야 하고 안 멈추면 멈춰야 한다. 모순이니 H는 없다.

한 문제가 판정 불가능하다는 것을 알면 다른 문제로 번진다. 이것이 환원이다. 문제 B를 푸는 프로그램이 있으면 그것으로 A를 풀 수 있다고 보이면(A를 B로 환원), "A는 못 푼다"에서 "B도 못 푼다"가 나온다. 예컨대 "이 프로그램은 빈 입력에서 언젠가 'hello'를 출력하는가"를 판정할 수 있다면, 임의의 P와 x에 대해 "P를 x로 돌리고 끝나면 hello를 출력하는 프로그램"을 만들어 물어보면 정지 문제가 풀린다. 그러니 이 문제도 판정 불가능하다.

이를 끝까지 밀어붙인 것이 라이스 정리(1951)다. 프로그램이 "무엇을 계산하는가"에 관한 성질 가운데, 모든 프로그램이 가지거나 아무도 안 가지는 뻔한 것을 빼면 전부 판정할 수 없다. "이 함수는 늘 양수를 돌려주는가", "이 프로그램은 바이러스처럼 행동하는가", "두 프로그램은 같은 일을 하는가" 모두 일반적으로는 답할 수 없다. 정적 분석기·백신·컴파일러 최적화가 완벽하지 않은 근본 이유이고, 그래서 이들은 "모르겠다"를 허용하거나 틀린 경보를 감수하는 근사로 일한다.

복잡도: P, NP, NP-완전

풀 수 있는 문제 안에서도 "얼마나 빨리"가 다르다. 입력 크기 n에 대해 n², n³처럼 다항식 걸음으로 푸는 문제의 모임이 P다. 정렬, 최단 경로, 최대 흐름이 여기 든다(알고리즘 노트). 반면 가능한 경우를 모두 시도해야 하는 2ⁿ걸음 알고리즘은 n이 조금만 커져도 쓸 수 없다. 이론에서 "다항 = 다룰 만함"으로 보는 이유가 아래 표에 있다.

NP는 "답이 맞는지 확인하는 것"이 다항 시간인 문제의 모임이다. 스도쿠를 푸는 것은 어려워 보여도, 누가 채운 판을 주면 맞는지 금방 확인한다. 불 식을 참으로 만드는 변수 배정이 있는가(SAT), 그래프를 세 색으로 이웃끼리 다르게 칠할 수 있는가(3색 칠하기), 길이 k 이하로 모든 도시를 도는 경로가 있는가(외판원 판정판)가 그렇다. P의 문제는 확인도 쉬우니 P ⊆ NP다. 그런데 확인이 쉬운 문제는 모두 푸는 것도 쉬운가? 이것이 P vs NP 문제다. 대부분은 P ≠ NP라고 믿지만 아무도 증명하지 못했다. 클레이 수학 연구소는 2000년에 일곱 개의 밀레니엄 상 문제를 발표하며 문제마다 100만 달러를 걸었고, P vs NP가 그 하나다. 일곱 가운데 풀린 것은 푸앵카레 추측뿐이다.

NP 안에는 "가장 어려운" 문제들이 있다. 1971년 스티븐 쿡은 NP의 모든 문제를 SAT로 다항 시간에 환원할 수 있음을 보였고(레오니드 레빈도 따로 같은 결과를 1973년에 발표했다, 쿡–레빈 정리), 이듬해 리처드 카프가 21개 문제가 같은 성질을 가짐을 보였다. 이런 문제를 NP-완전이라 한다. NP-완전 문제 하나만 다항 시간에 풀어도 NP 전체가 P로 무너진다. NP에 속하지 않아도 NP 문제 전부가 환원되는 문제는 NP-난해라 한다.

새 문제가 NP-완전임을 보이는 방법은 이미 아는 NP-완전 문제를 그 문제로 환원하는 것이다. SAT(정확히는 절마다 변수가 셋인 3-SAT)를 3색 칠하기로 바꾸는 고전적 환원을 보자. 먼저 삼각형 하나를 그려 꼭짓점을 "참", "거짓", "기준"이라 부른다. 세 색이 이 세 이름을 나눠 갖는다. 변수 x마다 x와 ¬x 두 꼭짓점을 서로 잇고 둘 다 "기준"과 이으면, 둘 중 하나는 참 색, 다른 하나는 거짓 색이 될 수밖에 없다. 절마다 작은 부품 그래프를 붙여, 절의 세 글자가 모두 거짓 색이면 칠할 방법이 없도록 만든다. 그러면 "식을 참으로 만드는 배정이 있다"와 "그래프를 세 색으로 칠할 수 있다"가 정확히 같은 말이 되고, 그래프 크기는 식 크기에 비례한다. 3색 칠하기를 빨리 푸는 방법이 생기면 SAT도 빨리 풀린다는 뜻이다.

어려운 문제를 다루는 법

문제가 NP-난해라는 말은 "모든 입력에서 빠르고 정확한 알고리즘은 아마 없다"는 뜻이지 손을 놓으라는 뜻이 아니다. 실무에서는 세 조건(모든 입력, 빠름, 정확함) 가운데 하나를 양보한다.

• 근사 알고리즘: 최적은 포기하되 최적의 몇 배 이내라는 보장을 받는다. 꼭짓점 덮개(모든 간선의 한쪽 끝을 고르기)는 아직 안 덮인 간선을 하나 골라 양 끝을 모두 넣는 일을 반복하면 된다. 고른 간선들은 서로 끝을 공유하지 않으므로 최적해도 간선마다 적어도 하나는 넣어야 하고, 따라서 결과는 최적의 두 배를 넘지 않는다.
• 휴리스틱: 보장은 없지만 대개 잘 되는 방법이다. 외판원에서 "가장 가까운 안 간 도시로 가기"는 빠르지만 아래처럼 꽤 손해를 보기도 한다. 실제 경로 최적화 도구는 이런 초기 해를 국소 탐색(구간 뒤집기 등)으로 다듬는다. 현대 SAT 풀이기도 최악은 지수지만 산업 현장의 수백만 변수짜리 식을 일상적으로 푼다.
• 특수 경우: 입력에 구조가 있으면 쉬워진다. 그래프가 트리면 많은 NP-난해 문제가 동적 계획법으로 다항 시간에 풀린다. 배낭 문제는 무게가 작은 정수면 무게 크기에 비례하는 동적 계획법으로 풀린다. 문제의 어려운 부분이 작은 매개변수 k에만 몰려 있으면 2ᵏ × 다항으로 푸는 고정 매개변수 알고리즘도 있다.

다른 복잡도 클래스: PSPACE, BPP, BQP

시간 대신 다른 자원으로 잰 클래스도 있다. PSPACE는 메모리를 다항식만큼만 쓰는 문제의 모임이다. 시간은 얼마가 걸려도 된다. 다항 시간 동안에는 다항 칸만 건드릴 수 있으므로 P ⊆ PSPACE이고, NP 문제도 후보 답을 하나씩 같은 메모리에 써 보며 확인하면 되니 NP ⊆ PSPACE다. "모든 x에 대해 어떤 y가 있어…"처럼 양화사가 번갈아 붙은 불 식이 참인지 묻는 문제(TQBF)가 PSPACE-완전의 대표다. 두 사람이 번갈아 수를 두는 게임에서 "먼저 두는 쪽이 반드시 이기는가"를 묻는 것과 같은 모양이다.

BPP는 동전을 던질 수 있는 알고리즘이 다항 시간에, 틀릴 확률을 1/3 이하로 묶어 두고 푸는 문제의 모임이다. 여러 번 돌려 다수결을 하면 틀릴 확률을 원하는 만큼 줄일 수 있다. 무작위 소수 판정이 오래 대표 예였는데, 결정적 다항 시간 판정법이 나온 뒤로는 BPP = P라고 믿는 사람이 많다. BQP는 같은 일을 양자 컴퓨터로 하는 모임이다. 소인수분해는 쇼어 알고리즘으로 BQP에 들지만 P에 드는지는 모르고, NP-완전 문제가 BQP에 든다는 증거는 없다. 양자 컴퓨터가 "모든 경우를 한꺼번에 시도해 NP를 푼다"는 설명이 틀린 이유다. 자세한 원리는 양자 컴퓨팅 노트에 있다.

흔한 오해

• "정지 문제 때문에 이 프로그램이 멈추는지 알 수 없다": 특정한 프로그램 하나와 입력 하나라면 답은 "멈춘다"와 "안 멈춘다" 가운데 하나로 이미 정해져 있고, 증명할 수 있는 경우도 많다. 판정 불가능하다는 것은 모든 프로그램과 입력에 대해 늘 바르게 답하는 알고리즘 하나가 없다는 뜻이다. 메모리가 유한한 기계는 상태가 유한해 언젠가 멈추거나 같은 상태를 되풀이하므로 원리상 판정할 수 있지만, 상태 수가 천문학적이라 실제로는 별 도움이 안 된다.
• "NP-완전이면 실무에서 못 푼다": 복잡도는 최악의 입력에 대한 말이다. 앞의 "어려운 문제를 다루는 법"처럼 실제 입력은 대개 풀린다. 거꾸로 P에 든다고 빠른 것도 아니다. n¹⁰⁰걸음 알고리즘도 다항 시간이다.
• "NP-난해와 NP-완전은 같은 말이다": NP-완전은 NP-난해이면서 NP에도 드는 문제다. 정지 문제처럼 NP-난해이지만 NP 밖에 있는, 판정조차 안 되는 문제도 있다(위 포함 관계 그림).
• "튜링 완전하면 좋은 것이다": 튜링 완전은 계산할 수 있는 범위가 튜링 기계와 같다는 뜻일 뿐, 빠르거나 쓰기 편하다는 뜻이 아니다. 오히려 튜링 완전한 설정·템플릿 언어는 정지 문제와 라이스 정리를 그대로 떠안아, 주어진 설정이 끝날지, 무엇을 할지를 일반적으로 미리 검사할 수 없게 된다.

NP라는 이름 자체의 오해(N은 non이 아니다)는 알고리즘 › 더 나아가기 노트의 P와 NP 절에 있다. 정지 문제의 흔한 오해는 Wikipedia의 Halting problem 문서에도 따로 정리돼 있다.

핵심 자료

알고리즘 설계와 분석은 알고리즘 노트, 문법과 파서의 실제는 컴파일러 노트, 집합의 크기와 대각선 논법은 이산 수학 노트에 있다.