P 클래스

P 클래스는 컴퓨터로 감당할 수 있는 문제를 가려 냅니다. 입력이 커져도 걸리는 시간이 완만하게만 늘어나는 문제들이 여기 듭니다. 목록에 같은 값이 두 번 나오는지, 지도에서 두 곳이 정해진 거리 안에 이어지는지 묻는 문제가 대표입니다. 어떤 문제가 이 묶음에 드는지가 정답을 노릴지 근삿값으로 물러설지를 가릅니다.

쉽고 빠른 이해

P 클래스는 빨리 풀리는 문제의 모임입니다. 「정렬된 목록에 7 이 있나」는 가운데 값과 견줘 절반씩 버리면 금방 답이 나오므로 여기 듭니다.

이 모임이 있으면 알고리즘 하나가 아니라 문제 자체가 쉬운지를 말할 수 있습니다. 요구사항을 받았을 때 정답 풀이를 짤지 근삿값으로 물러설지 정하는 기준이 됩니다.

판정은 이렇게 합니다.

1. 문제를 「예·아니요」로 답하는 물음으로 바꿉니다
2. 입력 크기를 n 이라 하고 걸리는 단계 수를 n 에 대한 식으로 셉니다
3. 그 식이 n² 이나 n³ 처럼 n 을 정해진 횟수만큼 곱한 값을 넘지 않는 풀이가 하나라도 있으면 P 에 듭니다

대가도 있습니다. n¹⁰⁰ 단계짜리 풀이도 P 에 듭니다. 그래서 P 에 든다고 꼭 금방 끝나는 것은 아닙니다. 또 어떤 문제가 P 밖이라고 증명하기는 매우 어렵습니다.

상세

이사를 떠올려 봅시다. 짐 상자가 두 배가 되면 이사 시간도 두 배쯤 되는 집이 있습니다. 상자를 하나 더할 때마다 시간이 두 배가 되는 집도 있습니다. 앞의 집은 짐이 많아도 날짜를 잡을 수 있습니다. 뒤의 집은 상자 몇십 개면 끝나는 날을 못 잡습니다.

P 클래스는 앞의 집 같은 문제를 모은 것입니다. 이름의 P 는 Polynomial time, 곧 다항 시간의 머리글자입니다. 계산 문제를 풀기 버거운 정도에 따라 나눈 복잡도 클래스 가운데 가장 기본이 되는 묶음입니다.

이 절은 정의에 들어가는 낱말 셋을 먼저 풉니다. 「예·아니요」로 답하는 결정 문제, 입력 크기, 다항 시간입니다. 그다음 셋을 모아 P 를 정의하고 어떤 문제가 드는지, 실무에서 이 구분을 언제 쓰는지를 봅니다.

결정 문제

결정 문제는 답이 「예」나 「아니요」 둘 중 하나인 물음입니다. 「이 목록에 7 이 있나」나 「이 두 사람이 친구의 친구로 이어지나」가 그렇습니다.

「가장 짧은 경로를 구하라」처럼 값을 내라는 문제도 결정 문제로 바꿔 묻습니다. 「길이 10 이하인 경로가 있나」로 물으면 됩니다. 10 대신 여러 값을 넣어 물으면 가장 짧은 길이도 알아낼 수 있습니다.

답의 꼴을 하나로 맞추는 이유는 문제끼리 견주기 위해서입니다. 답이 수인 문제와 답이 경로인 문제는 바로 견줄 수 없습니다. 모두 「예·아니요」로 맞추면 같은 잣대로 잽니다.

입력 크기와 단계 수

입력 크기는 입력을 적는 데 드는 글자 수입니다. 보통 n 으로 적습니다.

수 목록이라면 수 하나를 한 칸으로 쳐서 수의 개수를 n 으로 씁니다. 수마다 자릿수가 정해진 범위 안이면 글자 수가 개수에 비례하기 때문입니다. 수 1,000 개짜리 목록이면 n 은 1,000 입니다.

걸리는 시간은 초가 아니라 단계 수로 셉니다. 값 둘을 비교하거나 더하는 일을 한 단계로 칩니다. 초로 재면 컴퓨터가 바뀔 때마다 답이 달라지기 때문입니다.

단계 수는 같은 크기의 입력끼리도 다릅니다. 목록에서 7 을 찾을 때 7 이 맨 앞에 있으면 한 단계로 끝납니다. 그래서 크기가 n 인 입력 가운데 일이 가장 많은 입력을 기준으로 셉니다. 이 기준을 최악의 경우라고 부릅니다.

다항 시간

다항 시간은 단계 수가 n², n³ 처럼 n 을 정해진 횟수만큼 곱한 값을 넘지 않는다는 뜻입니다. 곱하는 횟수를 k 라 하면 단계 수가 nᵏ 을 넘지 않는다는 말입니다. k 는 n 이 커져도 바뀌지 않는 상수입니다.

이것을 빅오 표기법으로 O(nᵏ) 라고 적습니다. 빅오 표기법은 단계 수가 많아야 어떤 식에 비례해 자라는지만 나타냅니다. 그래서 앞에 곱한 상수와 느리게 자라는 항은 버립니다. 3n² + 5n 단계면 O(n²) 입니다.

반대편에는 지수 시간이 있습니다. 2ⁿ 처럼 n 이 하나 늘 때마다 단계 수가 두 배가 되는 꼴입니다. 아래 표는 n 을 늘려 가며 세 꼴의 단계 수를 견줍니다.

n 이 10 일 때는 세 꼴이 비슷합니다. n 이 60 이 되면 n³ 은 20만을 조금 넘습니다. 2ⁿ 은 1초에 10억 단계를 밟는 컴퓨터로도 30년 넘게 걸립니다.

다항 꼴은 늘어나는 폭이 예측됩니다. 입력을 두 배로 늘리면 단계 수는 정해진 배수로만 늡니다. n² 이면 네 배, n³ 이면 여덟 배입니다. 2ⁿ 은 입력을 두 배로 늘리면 단계 수가 제곱이 됩니다.

P 의 정의

이제 세 낱말을 모읍니다. P 는 다항 시간 안에 답을 내는 풀이가 하나라도 있는 결정 문제의 모임입니다.

「정렬된 목록에 7 이 있나」가 P 에 듭니다. 가운데 값과 7 을 견줘 절반을 버리기를 되풀이하는 이진 탐색을 쓰면 100만 개 목록도 스무 번 남짓 비교해 답이 나옵니다.

입력이 두 배가 될 때 단계가 하나씩만 느는 이 셈을 O(log n) 이라고 적습니다. log n 은 n 보다 작으니 단계 수가 n¹ 을 넘지 않습니다. 곱하는 횟수 k 가 1 인 다항 시간 안에 드는 것입니다.

계산 이론은 풀이를 튜링 기계라는 가상의 기계로 적습니다. 끝없이 긴 테이프에 글자를 읽고 쓰며 한 칸씩 움직이는 단순한 기계입니다. 실제 컴퓨터마다 다른 속도를 떼어 내려고 이런 기계를 기준으로 삼습니다.

P 의 정의에 쓰는 것은 결정적 튜링 기계입니다. 「결정적」은 같은 상황에서 다음 동작이 늘 하나로 정해진다는 뜻입니다. 우리가 짜는 보통의 프로그램이 이렇게 돕니다.

기계를 보통의 컴퓨터로 바꿔도 P 에 드는 문제는 바뀌지 않습니다. 튜링 기계에서 다항 시간에 풀리는 문제는 오늘날의 컴퓨터에서도 다항 시간에 풀립니다. 그 반대도 같습니다. 기계를 바꾸면 곱하는 횟수 k 가 조금 오를 수는 있습니다. 그래도 다항이 지수로 바뀌지는 않습니다.

알고리즘이 아니라 문제의 성질

P 는 알고리즘이 아니라 문제를 나눕니다. 한 문제를 푸는 방법은 여럿입니다. 「목록에 같은 값이 두 번 나오나」는 모든 쌍을 비교하면 n² 에 비례하는 단계가 듭니다. 먼저 정렬한 뒤 이웃끼리만 비교하면 단계가 훨씬 줄어듭니다.

다항 시간 풀이가 하나라도 있으면 그 문제는 P 에 듭니다. 같은 문제를 지수 시간에 푸는 서툰 방법이 따로 있어도 이 판정은 바뀌지 않습니다.

그래서 P 에 든다고 보이기는 쉽고 P 밖이라고 보이기는 어렵습니다. 드는 쪽은 다항 시간 풀이 하나를 내놓으면 끝납니다. 밖이라는 쪽은 아직 아무도 생각하지 못한 풀이까지 모두 안 된다고 증명해야 합니다.

P 밖이라고 증명된 문제도 있습니다. 판을 n×n 으로 키운 체스에서 먼저 두는 쪽이 반드시 이길 수 있는지 묻는 문제가 그렇습니다. 실무에서 만나는 어려운 문제는 대부분 P 에 드는지 아직 모릅니다.

P 에 드는 문제

아래 표는 P 에 드는 문제를 결정 문제 꼴로 적고 다항 시간 풀이를 하나씩 짝지었습니다. 경로 문제의 n 은 지점 수입니다.

네 풀이 모두 단계 수가 n² 을 넘지 않습니다. 백엔드에서 매일 쓰는 조회·정렬·그래프 탐색이 대개 이 표에 드는 문제입니다.

NP 와의 관계

P 를 이해하려면 바로 바깥에 있는 묶음 하나를 같이 봐야 합니다. NP(Nondeterministic Polynomial time, 비결정적 다항 시간)는 답이 「예」일 때 그 근거를 받으면 다항 시간 안에 맞는지 확인할 수 있는 결정 문제의 모임입니다.

이름의 「비결정적」은 갈림길마다 맞는 갈래를 골라 가는 가상의 기계에서 왔습니다. 그 기계가 고른 갈래를 적어 두면 그대로 근거가 됩니다. 그래서 맞는 갈래를 고르는 일을 근거를 받는 일로 바꿔 읽어도 같은 모임이 나옵니다.

「수 목록 [3, 34, 4, 12, 5, 2] 에서 몇 개를 골라 합을 9 로 만들 수 있나」가 NP 에 듭니다. 누가 「4 와 5」라는 근거를 주면 더해 보기만 하면 됩니다. 근거 없이 찾는 다항 시간 풀이는 아직 알려지지 않았습니다.

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

거꾸로 NP 의 문제가 모두 P 에 드는지는 아무도 모릅니다. 확인이 쉬운 문제는 푸는 것도 쉬운가라는 이 물음이 P 대 NP 문제입니다. 연구자 대부분은 둘이 다르다고 보지만 증명은 아직 없습니다.

flowchart TD
    subgraph NPB["NP · 근거를 받으면 다항 시간에 확인"]
        subgraph PB["P · 다항 시간에 풂"]
            A["정렬된 목록에 x 가 있나"]
            B["길이 10 이하 경로가 있나"]
        end
        C["합이 9 가 되게 고를 수 있나 · P 에 드는지 모름"]
    end

그림에서 합 문제를 P 상자 밖에 둔 것은 다항 시간 풀이가 아직 없다는 뜻입니다. P 에 들지 않는다고 밝혀진 것은 아닙니다.

환원과 NP-완전

어떤 문제가 P 에 드는지 모를 때는 이미 아는 문제로 바꿔 물어봅니다. 이 절은 앞 표의 두 문제로 그 방법을 보입니다. 친구 문제(「두 사람이 친구 관계로 이어지나」)와 경로 문제(「두 지점 사이에 길이 몇 이하 경로가 있나」)입니다.

환원은 문제 A 의 입력을 문제 B 의 입력으로 다항 시간 안에 바꾸는 일입니다. 바꾼 입력에 대한 B 의 답은 A 의 답과 늘 같아야 합니다. 여기서는 친구 문제가 A, 경로 문제가 B 입니다.

사람을 지점으로, 친구 관계를 길이 1 인 길로 놓으면 친구 문제가 경로 문제로 바뀝니다. 물음은 「두 사람 사이에 길이가 사람 수 이하인 경로가 있나」입니다. 두 사람이 이어져 있으면 같은 사람을 두 번 거치지 않는 경로가 있습니다. 그 경로의 길이는 사람 수보다 짧으므로 두 물음의 답은 늘 같습니다.

A 가 B 로 환원되면 B 를 푸는 방법으로 A 도 풉니다. 경로 문제는 다익스트라 알고리즘으로 다항 시간에 풀리므로 친구 문제도 P 에 듭니다. 거꾸로 A 가 어렵다면 B 는 A 보다 쉬울 수 없습니다. B 를 풀면 A 도 풀리기 때문입니다.

NP-완전 문제는 NP 에 드는 문제 가운데 NP 의 모든 문제가 그리로 환원되는 문제입니다. 이 가운데 하나라도 P 에 들면 NP 전체가 P 에 들게 됩니다. 앞의 합 문제가 여기 듭니다.

외판원 순회도 여기 듭니다. 외판원 순회는 모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 경로를 찾는 문제입니다. 「총 길이 100 이하로 다 돌 수 있나」처럼 결정 문제 꼴로 물으면 NP-완전입니다.

실무에서 이 구분을 쓰는 때

백엔드 개발자가 이 구분을 꺼내는 때는 요구사항이 조합을 고르는 꼴일 때입니다. 배송 경로 짜기, 회의실과 시간표 배정, 용량이 정해진 서버에 작업 나눠 담기가 그렇습니다. 풀이를 짜기 전에 이 요구가 P 에 드는지부터 따집니다.

근사 알고리즘은 최적에 가깝다고 보장된 답을 다항 시간에 냅니다. 보장은 비율로 줍니다. 「찾은 답이 최적의 두 배를 넘지 않는다」 같은 보장입니다.

휴리스틱은 대개 쓸 만한 답을 빨리 내는 경험적 방법입니다. 근사 알고리즘과 달리 최적에 얼마나 가까운지는 보장하지 않습니다. 둘 다 정답을 포기하고 시간을 얻습니다.

따지는 순서는 아래 그림과 같습니다. 갈림은 두 번입니다. 다항 시간 풀이를 아는지, 모르면 이미 알려진 NP-완전 문제를 이 요구로 환원할 수 있는지입니다.

flowchart TD
    A["요구를 결정 문제로 바꾼다"] --> B{"다항 시간 풀이를 아나"}
    B -->|안다| C["P 에 든다 · 정답 풀이를 짠다"]
    B -->|모른다| D{"NP-완전 문제를 이 요구로 환원할 수 있나"}
    D -->|안 된다| F["다항 시간 풀이를 더 찾는다"]
    D -->|된다| E["다항 시간 정답 풀이를 기대하지 않는다"]
    E --> G["근사 알고리즘 · 휴리스틱 · 입력 크기 제한"]

입력 크기를 묶는 길도 실제로 많이 씁니다. 앞의 표에서 n 이 20 이면 2ⁿ 도 약 105만 단계라 금방 끝납니다. 고를 대상이 늘 스무 개 남짓이라면 모든 조합을 다 따져 보는 풀이로 충분합니다.

P 가 알려 주지 않는 것

P 는 입력이 한없이 커질 때의 이야기입니다. n¹⁰⁰ 단계를 밟는 풀이도 다항 시간이라 P 에 듭니다. 그런 풀이는 n 이 2 만 돼도 2¹⁰⁰ 단계를 밟아 끝나지 않습니다.

앞에서 본 대로 빅오 표기법은 상수와 느리게 자라는 항을 버립니다. 그래서 P 에 든다는 사실은 몇 초 걸리는지를 알려 주지 않습니다.

P 밖일지 모르는 문제라도 실무 입력은 금방 풀리는 경우가 많습니다. 정해진 무게 안에서 값어치가 가장 크게 물건을 고르는 배낭 문제가 그렇습니다. 무게 한도가 작은 수이면 동적 계획법으로 금방 풉니다.

최악의 경우는 드물게만 나오기도 합니다. P 는 풀이의 방향을 고르는 기준으로 쓰고 걸리는 시간은 벤치마크로 따로 잽니다.

관련 항목

P 클래스가 속하는 상위 분류

복잡도 클래스 · 계산 복잡도 이론 · 계산 이론 · 알고리즘 분석 · 알고리즘

P 클래스를 정의하는 데 쓰이는 개념

결정 문제 · 다항 시간 · 입력 크기 · 튜링 기계 · 결정적 튜링 기계 · 최악의 경우 · 시간 복잡도 · 빅오 표기법

P 클래스를 감싸거나 견주는 복잡도 클래스

NP 클래스 · co-NP · PSPACE · EXPTIME · L 클래스 · BPP · NP-완전 · NP-난해 · P-완전

P 클래스와 다른 클래스 사이를 다루는 문제와 정리

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

P 클래스에 드는 대표 문제

정렬 · 이진 탐색 · 너비 우선 탐색 · 다익스트라 알고리즘 · 최단 경로 · 소수 판정 · 이분 매칭 · 최대 흐름 · 선형 계획법 · 2-SAT

P 클래스 밖일지 모르는 문제

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

P 클래스에 드는지 모르는 문제 앞에서 고르는 풀이 방법

근사 알고리즘 · 휴리스틱 · 분기 한정법 · 동적 계획법 · 의사 다항 시간

단계 수가 불어나는 꼴을 가리키는 이름

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