복잡도 클래스

복잡도 클래스는 문제를 얼마나 풀기 버거운지에 따라 나눠 줍니다. 계산 이론에서는 정해진 시간이나 메모리 안에 풀리는 문제들을 하나로 묶을 때 이 이름을 씁니다. 알고리즘을 배울 때는 비용이 불어나는 꼴이 같은 것끼리 묶는 뜻으로도 씁니다. 두 뜻 모두 입력이 커질 때 얼마나 버거워지는지를 기준으로 삼습니다.

쉽고 빠른 이해

문제를 얼마나 빨리 풀 수 있는지로 나눈 것이 복잡도 클래스입니다. 예를 들어 정렬은 데이터 개수의 제곱을 넘지 않는 시간 안에 풀리므로 빨리 풀리는 클래스에 듭니다.

이렇게 묶어 두면 알고리즘 하나가 아니라 문제 자체가 얼마나 어려운지 말할 수 있습니다. 어떤 문제가 어려운 클래스에 든다고 밝혀지면 시간이 덜 드는 정답 풀이를 찾는 대신 근삿값이나 입력 크기 제한 쪽으로 방향을 틉니다.

묶는 순서는 이렇습니다.

1. 시간과 메모리 가운데 무엇을 잴지 정합니다
2. 입력 크기에 대한 한도를 정합니다. 입력 크기의 제곱이나 세제곱 같은 한도와, 2 를 입력 크기만큼 거듭 곱한 한도가 대표입니다
3. 그 한도 안에 푸는 방법이 하나라도 있는 문제를 한 클래스로 묶습니다

대가도 있습니다. 클래스는 입력이 한없이 커질 때의 이야기입니다. 그래서 몇 초 걸리는지는 알려 주지 않습니다. 또 답을 받으면 빨리 확인할 수 있는 문제가 빨리 풀리기도 하는지는 아직 아무도 증명하지 못했습니다.

상세

만 원으로 살 수 있는 물건을 한데 모아 봅시다. 십만 원으로 살 수 있는 물건도 따로 모읍니다. 만 원으로 살 수 있는 물건은 십만 원으로도 살 수 있습니다. 그래서 앞 묶음은 뒤 묶음 안에 전부 들어갑니다.

복잡도 클래스는 돈 대신 시간과 메모리를 예산으로 잡습니다. 이 예산을 한도라고 부릅니다. 한도는 입력 크기에 대한 식으로 정합니다. 그 한도 안에 풀리는 것들이 한 클래스가 됩니다.

이 말은 두 뜻으로 쓰입니다. 알고리즘 교재와 실무에서는 선형·이차·지수처럼 비용이 불어나는 꼴 하나하나를 클래스라고 부르곤 합니다. 계산 복잡도 이론에서는 한도 안에 풀리는 문제의 모임을 클래스라고 부릅니다. 앞의 뜻은 알고리즘을 나누고 뒤의 뜻은 문제를 나눕니다.

이 절은 익숙한 앞의 뜻에서 출발해 문제를 묶는 뒤의 뜻으로 넘어갑니다.

비용이 불어나는 꼴의 묶음

시간 복잡도는 입력 크기 n 이 커질 때 걸리는 시간이 어떤 꼴로 불어나는지를 적습니다. 걸리는 시간은 3n² + 5n 처럼 n 에 대한 식으로 나옵니다.

이 식에서 가장 빨리 자라는 항 3n² 만 남깁니다. 그다음 앞에 곱한 상수 3, 곧 계수를 떼면 n² 꼴이 남습니다. 이렇게 n 이 한없이 커질 때 남는 꼴만 보는 방법을 점근 분석이라고 합니다.

줄인 꼴은 빅오 표기법으로 O(n²) 처럼 적습니다. 걸리는 시간이 많아야 n² 에 비례해 자란다는 뜻입니다.

줄이고 나면 꼴은 몇 가지로 모입니다. 이 꼴 하나하나가 알고리즘을 나누는 뜻의 복잡도 클래스입니다. 아래 표는 느리게 자라는 꼴부터 놓았습니다.

n², n³, n¹⁰ 처럼 n 을 정해진 횟수만큼 곱한 값을 넘지 않는 꼴을 통틀어 다항 시간이라고 부릅니다. 표의 위쪽 다섯 꼴은 모두 n² 을 넘지 않으므로 여기 듭니다. 맨 아래 2ⁿ 은 n 이 하나 늘 때마다 두 배가 되는 지수 시간입니다.

두 쪽의 차이는 입력이 커질수록 벌어집니다. n 이 30 이면 n² 은 900 이지만 2ⁿ 은 10억을 넘습니다. 다항 꼴은 입력을 두 배로 늘려도 시간이 정해진 배수로만 늘어납니다. n² 이면 네 배입니다.

문제를 자원 한도로 묶는 뜻

계산 복잡도 이론은 알고리즘이 아니라 문제를 묶습니다. 한 문제를 푸는 방법은 여럿입니다. 정렬만 해도 버블 정렬은 O(n²) 이고 병합 정렬은 O(n log n) 입니다.

이론은 한도 안에 드는 방법이 하나라도 있는지를 묻습니다. 하나라도 있으면 그 문제는 그 클래스에 듭니다. 정렬은 두 방법이 모두 다항 시간이므로 다항 시간 안에 풀리는 문제입니다.

클래스 하나를 정하려면 세 가지를 고릅니다. 무엇을 잴지(시간인가 메모리인가), 한도를 얼마로 둘지(다항식인가 지수인가), 어떤 기계로 풀지입니다.

기계는 튜링 기계라는 단순한 가상 기계를 기준으로 삼습니다. 끝없이 이어진 테이프에 글자를 읽고 쓰며 한 칸씩 움직이는 기계입니다. 시간은 이 기계가 밟는 단계 수로 잽니다. 실제 컴퓨터마다 달라지는 속도를 떼어 내려고 이런 가상 기계를 씁니다.

다항 시간이 경계로 널리 쓰이는 이유도 여기 있습니다. 튜링 기계에서 다항 시간에 풀리는 문제는 오늘날의 컴퓨터에서도 다항 시간에 풀립니다. 기계를 바꾸면 n² 의 2 같은 거듭제곱 수, 곧 차수가 조금 오를 수는 있습니다. 그래도 다항이 지수로 바뀌지는 않습니다.

클래스에 넣는 문제는 대개 「예」나 「아니요」로 답하는 결정 문제입니다. 「이 목록에서 몇 개를 골라 합을 9 로 만들 수 있나」 같은 물음입니다. 「가장 짧은 경로를 구하라」 같은 문제도 「길이 k 이하인 경로가 있나」로 바꿔 묻습니다. 답의 형식을 하나로 맞춰야 문제끼리 비교하기 쉽기 때문입니다.

다항 시간에 풀리는 문제

P(Polynomial time, 다항 시간)는 다항 시간 안에 푸는 방법이 있는 결정 문제의 모임입니다. 「정렬된 목록에 값 x 가 있나」나 「두 지점 사이에 길이 k 이하인 경로가 있나」가 여기 듭니다.

P 는 흔히 컴퓨터로 감당할 수 있는 문제의 기준으로 쓰입니다. 입력이 커져도 시간이 정해진 배수로만 늘기 때문입니다.

답을 빨리 확인할 수 있는 문제

NP(Nondeterministic Polynomial time, 비결정적 다항 시간)는 답이 「예」일 때 그 근거를 받으면 다항 시간 안에 맞는지 확인할 수 있는 결정 문제의 모임입니다. 푸는 데 드는 시간은 따지지 않습니다. 확인하는 데 드는 시간만 다항이면 됩니다.

부분집합 합 문제가 대표입니다. 수 목록 [3, 34, 4, 12, 5, 2] 에서 몇 개를 골라 합을 9 로 만들 수 있는지 묻습니다. 누가 「4 와 5」라는 근거를 주면 더해 보기만 하면 확인이 끝납니다.

근거 없이 찾는 일은 다릅니다. 가장 단순한 방법은 부분집합을 하나씩 만들어 보는 것입니다. 원소가 n 개면 부분집합은 2ⁿ 개입니다. 이 문제를 다항 시간에 푸는 방법은 아직 알려지지 않았습니다.

이름의 N 은 「아니다(Not)」가 아닙니다. 「비결정적」은 갈림길마다 맞는 쪽을 알아서 골라 가는 가상의 기계를 가리킵니다.

이 기계가 갈림길마다 고른 길이 곧 근거입니다. 그 길을 따라가며 확인하는 데는 다항 시간이 듭니다. 그래서 이 기계로 다항 시간에 푸는 문제와, 근거를 받아 다항 시간에 확인하는 문제가 같은 클래스가 됩니다.

클래스 사이의 포함 관계

이 소절은 클래스들이 서로를 어떻게 감싸는지 봅니다. P 와 NP 에 더해 한도가 넓은 클래스 둘을 들여와 그림 하나로 모읍니다.

P 에 드는 문제는 모두 NP 에도 듭니다. 근거를 받을 필요도 없이 처음부터 풀어 버리면 확인이 끝나기 때문입니다.

PSPACE(Polynomial Space, 다항 공간)는 다항식만큼의 메모리로 푸는 문제의 모임입니다. NP 는 PSPACE 안에 듭니다. 후보 근거를 하나 만들어 확인하고 지우기를 되풀이하면, 시간은 오래 걸려도 메모리는 후보 하나만큼만 씁니다.

EXPTIME(Exponential Time, 지수 시간)은 지수 시간 안에 푸는 문제의 모임입니다. 이것이 PSPACE 를 다시 감쌉니다. 아래 그림은 안쪽 테두리일수록 한도가 좁습니다.

flowchart TD
    subgraph EXP["EXPTIME · 지수 시간에 풂"]
        subgraph PS["PSPACE · 다항 메모리로 풂"]
            subgraph NPB["NP · 다항 시간에 확인"]
                subgraph PB["P · 다항 시간에 풂"]
                    A["정렬"]
                end
                B["부분집합 합 문제 · P 에 드는지 모름"]
            end
        end
    end

부분집합 합 문제를 P 상자 밖에 둔 것은 P 에 드는 풀이가 아직 알려지지 않았다는 뜻입니다. P 에 들지 않는다고 밝혀진 것은 아닙니다.

네 클래스 가운데 서로 다르다고 증명된 짝은 P 와 EXPTIME 뿐입니다. 지수 시간을 주면 다항 시간으로는 못 푸는 문제가 반드시 생깁니다.

P 와 EXPTIME 사이에는 경계가 셋 있습니다. P 와 NP 사이, NP 와 PSPACE 사이, PSPACE 와 EXPTIME 사이입니다. 경계가 진짜라는 것은 안쪽 클래스에 없는 문제가 바깥쪽 클래스에 실제로 있다는 뜻입니다.

세 경계 모두에서 안팎이 같다면 P 와 EXPTIME 도 같아집니다. 그러니 적어도 하나는 진짜 경계입니다. 어느 것인지는 아무도 모릅니다.

그중 P 와 NP 가 같은지를 묻는 것이 P 대 NP 문제입니다. 확인이 쉬운 문제는 푸는 것도 쉬운가를 묻습니다. 연구자 대부분은 둘이 다르다고 보지만 증명은 아직 없습니다.

가장 어려운 문제

문제끼리 어려움을 비교하려면 도구가 하나 필요합니다. 문제 A 의 입력을 문제 B 의 입력으로 다항 시간 안에 바꿀 수 있다고 합시다. 바꾼 입력에 대한 B 의 답이 A 의 답과 늘 같다면, B 를 푸는 방법으로 A 도 풀 수 있습니다.

이렇게 바꾸는 일을 환원이라고 합니다. A 가 B 로 환원되면 B 는 적어도 A 만큼 어렵습니다. 두 문제의 풀이를 몰라도 어느 쪽이 더 어려운지는 말할 수 있게 됩니다.

NP-완전 문제는 NP 에 들면서, NP 의 모든 문제가 그리로 환원되는 문제입니다. NP 안에서 가장 어려운 문제들이라는 뜻입니다. 그래서 이 가운데 하나라도 다항 시간에 풀리면 NP 의 모든 문제가 다항 시간에 풀립니다.

NP-완전으로 흔히 드는 문제는 셋입니다.

• 부분집합 합 문제
• SAT(Boolean Satisfiability, 불 충족 가능성) — 참·거짓 변수로 된 논리식을 참으로 만드는 값 배정이 있나
• 외판원 순회의 결정판 — 모든 도시를 한 번씩 도는 길이 k 이하의 경로가 있나

NP-난해는 환원 조건만 따집니다. NP 의 모든 문제가 그리로 환원되면, 그 문제가 NP 안에 없어도 NP-난해입니다. 「가장 짧은 순회 경로를 구하라」는 외판원 순회의 최적화판이 그렇습니다. 답이 「예·아니요」가 아니라서 NP 에 넣을 수 없습니다. 그래도 적어도 결정판만큼 어렵습니다.

백엔드 개발에서 이 이름을 만나는 때는 대개 이런 문제와 부딪힐 때입니다. 배송 경로 짜기, 회의와 시간표 배정, 정해진 용량에 짐 싣기 같은 요구가 NP-완전이나 NP-난해 문제와 같은 꼴입니다.

그런 요구라고 밝혀지면 큰 입력에서 최적해를 빠르게 내는 방법을 찾지 않습니다. 근사 알고리즘이나 휴리스틱으로 최적에 가까운 답을 내거나, 입력 크기를 작게 묶는 쪽을 고릅니다.

클래스가 알려 주지 않는 것

클래스는 입력이 한없이 커질 때의 이야기입니다. n¹⁰⁰ 단계를 밟는 방법도 다항 시간이라 P 에 듭니다. 그런 방법은 n 이 2 만 돼도 2¹⁰⁰ 단계를 밟아 끝나지 않습니다. 계수와 느리게 자라는 항을 버렸으므로 몇 초 걸리는지도 알려 주지 않습니다.

클래스는 최악의 경우, 곧 일이 가장 많아지는 입력을 기준으로 삼습니다. NP-완전 문제라도 실무에서 만나는 입력은 금방 풀리는 경우가 많습니다. 클래스는 풀이의 방향을 고르는 기준으로 씁니다. 걸리는 시간은 벤치마크로 따로 잽니다.

관련 항목

복잡도 클래스가 속하는 상위 분류

계산 복잡도 이론 · 계산 이론 · 계산가능성 · 알고리즘 분석 · 알고리즘

계산 복잡도 이론이 정의한 대표 클래스

P 클래스 · NP 클래스 · co-NP · PSPACE · EXPTIME · L 클래스 · BPP

클래스 사이의 난이도를 가르는 도구와 정리

환원 · NP-완전 · NP-난해 · P 대 NP 문제 · 시간 계층 정리 · 쿡-레빈 정리

클래스 정의에 쓰이는 계산 모델과 문제 형식

튜링 기계 · 비결정적 튜링 기계 · 결정 문제 · 최적화 문제

비용이 불어나는 꼴을 가리키는 이름

상수 시간 · 로그 시간 · 선형 시간 · 선형 로그 시간 · 이차 시간 · 다항 시간 · 지수 시간

비용을 재고 적는 표기와 측정 수단

빅오 표기법 · 점근 분석 · 시간 복잡도 · 공간 복잡도 · 증가 차수 · 최악의 경우 · 벤치마크 · 프로파일링

대표 클래스에 드는 문제

정렬 · 부분집합 합 문제 · SAT · 외판원 순회 · 배낭 문제 · 그래프 색칠

어려운 문제 앞에서 대신 고르는 풀이 방법

근사 알고리즘 · 휴리스틱 · 분기 한정법 · SAT 풀이기