2.4 복잡도 클래스 — 풀 수 있지만 감당하기 어려운 문제

2.3이 "알고리즘이 원리적으로 존재하는가"를 물었다면, 이 문서는 "존재하는 알고리즘이 현실적인 시간 안에 끝나는가"를 묻는다. P와 NP를 인증서 검증 가능성으로 정의하고, 다항 시간 환원으로 NP-완전성이 퍼지는 방식을 확인한 뒤, 백트래킹 정규식 엔진의 ReDoS를 "알고리즘의 비효율"과 "문제 자체의 하한"을 구분하는 반례로 다시 가져온다.

학습 목표

• 문제와 인스턴스, 입력 크기, 결정 문제와 최적화 문제를 구분하고 복잡도 클래스가 worst case 기준으로 정의되는 이유를 설명한다.
• P와 NP를 각각 "다항 시간에 풀 수 있음"과 "인증서를 다항 시간에 검증할 수 있음"으로 정의하고, "NP는 non-polynomial의 약자다"라는 오해를 반박한다.
• NP-완전과 NP-난해의 차이를 설명하고, 다항 시간 환원으로 한 문제의 어려움이 다른 문제로 전달되는 방향을 작은 사례로 재현한다.
• 지수 시간 실행과 NP-난해성을 구분하고, ReDoS를 반례로 알고리즘의 비효율과 문제 자체의 하한을 분리한다.
• 문제의 크기·최적성 요구·제약의 변동성을 근거로 exact·근사·휴리스틱·솔버 중 하나를 선택하고 그 근거를 설명한다.

배경: 왜 이것이 존재하는가

2.3이 세운 결정 가능성은 "0과 1로 답이 나뉘는" 성질이다 — 알고리즘이 존재하거나 존재하지 않거나. 그런데 알고리즘이 존재해도 입력이 조금만 커지면 우주의 나이보다 오래 걸리는 경우가 있다. 1960년대 코브햄(Cobham)과 에드먼즈(Edmonds)는 "효율적으로 계산 가능하다"를 실무적으로 근사하는 기준으로 다항 시간(polynomial time)을 제안했다 — 입력 크기 n에 대해 실행 시간이 n의 다항식으로 상한이 잡히는 것. 이 기준이 유용한 이유는 계산 모델이나 인코딩 방식을 합리적인 범위에서 바꿔도 "다항 시간이냐 아니냐"라는 분류 자체는 바뀌지 않는다는 강건성에 있다.

1971년 쿡(Cook)이, 그리고 독립적으로 레빈(Levin)이 SAT가 이 분류 체계에서 특별한 위치에 있다는 것을 증명했다 — SAT를 다항 시간에 풀 수 있다면 특정 클래스의 모든 문제를 다항 시간에 풀 수 있다는 것(Cook–Levin 정리). 1972년 카프(Karp)는 이 결과를 실제 스케줄링, 그래프, 집합 문제 21개로 확장해, "다항 시간 알고리즘을 찾기 어려운 문제"가 SAT 하나만의 특이 현상이 아니라 광범위한 실무 문제에 공통된 구조임을 보였다. 이 챕터가 세우려는 것은 이 구조를 알아보는 눈이다 — 눈앞의 문제가 그 구조에 속한다면, "더 똑똑한 알고리즘을 찾으면 해결된다"는 기대 자체를 재검토해야 한다.

핵심 개념

문제, 인스턴스, 입력 크기 — 왜 worst case로 정의하는가

문제(problem)는 "그래프가 주어졌을 때 최단 경로를 찾아라"처럼 무한히 많은 인스턴스(instance, 구체적인 입력 하나하나)에 대한 일반적 질문이다. 복잡도 클래스는 결정 문제(decision problem, 예/아니오로 답하는 문제)를 기준으로 정의된다 — "이 그래프에 크기 k 이하의 정점 커버가 있는가?"처럼. 최적화 문제("최소 정점 커버의 크기는?")는 대개 대응하는 결정 문제로 바꿔 분류하고, 실제로 최적값을 찾는 것은 이 결정 문제를 이분 탐색하듯 반복하는 것과 비용이 비슷하다는 것이 알려져 있다.

복잡도는 입력 크기 n(인코딩된 비트 수 등)의 함수로, 그것도 **최악의 경우(worst case)**를 기준으로 정의한다. 1.1에서 다룬 점근 표기의 논의가 그대로 적용된다 — 평균적으로 빠른 알고리즘도 특정 입력에서 감당 못 할 정도로 느릴 수 있고, 복잡도 클래스가 말하는 "다항 시간에 풀린다"는 어떤 입력에도 적용되는 보장이다.

P — 다항 시간에 풀리는 문제

P는 결정론적 튜링 기계(또는 그와 동등한 통상적 계산 모델)로 입력 크기의 다항식 시간 안에 풀 수 있는 결정 문제의 클래스다. "다항 시간"이 항상 "실용적으로 빠르다"는 뜻은 아니다 — n¹⁰⁰도 다항식이지만 현실적으로 쓸 수 없다. 그러나 실무에서 발견되는 대부분의 다항 시간 알고리즘은 차수가 낮고(1.1이 다룬 상수 인자·차수의 실측이 여기서도 유효하다), P는 "합리적으로 확장 가능한 문제"의 실용적 경계선 역할을 한다.

NP — 인증서를 검증할 수 있는 문제

NP(nondeterministic polynomial time)는 "yes"인 인스턴스마다 인증서(certificate, 증거)가 존재해서, 그 인증서가 주어지면 다항 시간에 검증할 수 있는 결정 문제의 클래스다. 예를 들어 "이 그래프에 크기 k의 정점 커버가 있는가?"에서, 실제 정점 커버 집합이 주어지면 그 집합의 크기가 k 이하인지, 모든 간선이 덮이는지는 다항 시간에 확인할 수 있다 — 이 문제는 NP에 속한다. 정의의 이름은 "비결정론적 튜링 기계(가능한 모든 경로를 동시에 시도할 수 있다고 가정한 기계)가 다항 시간에 판정할 수 있는 문제"에서 왔고, 인증서 검증 정의와 동치임이 증명되어 있다 — 비결정론적 기계의 "올바른 경로를 어떻게든 골라낸다"는 것이 곧 그 경로(인증서)가 주어졌을 때의 검증과 같기 때문이다.

여기서 가장 흔한 오해를 바로잡는다: NP는 "non-polynomial"의 약자가 아니다. NP는 Nondeterministic Polynomial time의 약자이고, "다항 시간에 풀 수 없는 문제들의 모임"이라는 뜻이 전혀 아니다. 실제로 P에 속한 모든 문제는 NP에도 속한다(P ⊆ NP) — 다항 시간에 풀 수 있다면, 인증서 없이도 직접 풀어서 확인하면 그만이므로 인증서 검증도 당연히 다항 시간에 된다. P = NP인지 P ⊊ NP인지는 아직 아무도 증명하지 못한 미해결 문제다(밀레니엄 문제 중 하나). "NP에 속한 문제는 다항 시간에 풀 수 없다"는 문장도 마찬가지로 틀렸다 — 그것이 사실인지 아닌지 자체가 아직 증명되지 않았다.

NP-완전과 NP-난해 — "NP에 속하는가"와 "NP만큼 어려운가"는 별개다

다항 시간 환원(polynomial-time reduction, A ≤p B)은 2.3에서 본 환원을 시간 제약과 함께 다시 쓴 것이다 — 문제 A의 임의의 인스턴스를 다항 시간 안에 문제 B의 인스턴스로 변환할 수 있고, 그 변환된 인스턴스에 대한 B의 답이 원래 A의 답과 일치한다는 뜻이다. A ≤p B이고 B를 다항 시간에 풀 수 있다면, 변환(다항 시간) + B의 알고리즘(다항 시간) = 다항 시간이므로 A도 다항 시간에 풀린다. 즉 ≤p는 "B가 쉬우면 A도 쉽다"는 방향의 화살표다.

• NP-난해(NP-hard): NP에 속한 모든 문제가 이 문제로 다항 시간 환원된다(∀X ∈ NP, X ≤p B). B가 NP에 속하는지는 요구하지 않는다 — NP-난해는 "NP의 모든 문제만큼, 또는 그보다 어렵다"는 하한만 말한다.
• NP-완전(NP-complete): NP-난해이면서 동시에 NP에도 속하는 문제. NP 안에서 가장 어려운 문제들이다.

NP-완전 문제 하나라도 다항 시간 알고리즘이 발견되면 P = NP가 증명되고, 그 결과로 NP의 모든 문제가 다항 시간에 풀리게 된다 — NP-완전 문제들이 서로 다항 시간 환원으로 연결되어 있기 때문이다. 지금까지 수십 년간 수천 개의 NP-완전 문제에 다항 시간 알고리즘을 찾으려는 시도가 실패해 온 것이, P ≠ NP일 것이라는(증명되지는 않은) 폭넓은 믿음의 근거다.

작은 사례로 보는 다항 시간 환원 — 3-SAT에서 독립 집합으로

환원이 실제로 어떻게 동작하는지 작은 논리식으로 확인하자. 3-SAT 인스턴스(각 절이 리터럴 3개인 CNF, 2.1에서 다룬 CNF 표기를 그대로 쓴다) 하나를 생각한다.

φ = (x₁ ∨ x₂ ∨ ¬x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃)

구성 규칙: 절마다 리터럴 하나당 노드 하나를 만들고, 같은 절 안의 노드끼리는 모두 간선으로 연결한다(삼각형). 그리고 서로 다른 절에 있는 상보 리터럴(x와 ¬x) 노드 사이에도 간선을 연결한다.

절 1: (x1)──(x2)      절 2: (¬x1)──(x2)
        \  /                    \  /
        (¬x3)                  (x3)

절 1의 x1 ── 절 2의 ¬x1   (상보 리터럴 — 충돌 간선)
절 1의 ¬x3 ── 절 2의 x3   (상보 리터럴 — 충돌 간선)

주장: 이 그래프에 크기가 절의 개수(여기서는 2)인 독립 집합(independent set, 서로 간선으로 연결되지 않은 노드 집합)이 있는 것과 φ가 만족 가능한 것은 동치다.

• 절 안의 삼각형 간선 때문에 독립 집합은 절 하나당 노드를 최대 하나만 고를 수 있다. 크기 2(=절 개수)를 채우려면 각 절에서 정확히 하나씩 골라야 한다.
• 충돌 간선 때문에 x1(절1)과 ¬x1(절2)을 동시에 고를 수 없다 — 이는 "x1을 참으로도 거짓으로도 동시에 만들 수 없다"는 논리적 제약을 그래프 제약으로 옮긴 것이다.
• 예를 들어 절1에서 x1, 절2에서 x2를 고르면 둘 사이에 충돌 간선이 없으므로(변수가 다르다) 유효한 독립 집합이다. 이는 x1 = 참, x2 = 참이라는 배정에 대응하고, 실제로 두 절 모두 만족시킨다.

이 변환은 절의 개수에 선형으로 비례하는 노드와 간선만 만들므로 다항 시간에 계산할 수 있다. 따라서 3-SAT ≤p 독립 집합이다. 이 환원의 방향이 뜻하는 것은 이렇다 — 만약 독립 집합 문제를 다항 시간에 푸는 알고리즘이 있다면, 임의의 3-SAT 인스턴스를 위 규칙으로 그래프로 바꾼 뒤 그 알고리즘에 넣어 3-SAT도 다항 시간에 풀 수 있다. 3-SAT가 NP-완전이라고 알려져 있으므로(Cook–Levin 정리에서 SAT의 NP-완전성을 보인 뒤, SAT를 3-SAT로 다시 환원하는 표준 결과가 있다 — 이 챕터에서는 결과만 가져다 쓴다), 독립 집합도 NP-난해임이 증명된다. 독립 집합 자체도 "후보 집합이 주어지면 크기와 간선 없음을 다항 시간에 확인"할 수 있어 NP에 속하므로, 독립 집합은 NP-완전이다.

SAT에서 출발하는 난이도의 전달

Cook–Levin 정리의 증명 아이디어는(전체 증명은 이 챕터의 범위를 넘는다) NP에 속한 임의의 문제에 대해, 그 문제를 판정하는 비결정론적 튜링 기계의 계산 과정 전체를 "이 칸에는 이 기호가, 이 시점에는 이 상태가 있다"는 식의 명제 변수들로 표현하고, 튜링 기계의 전이 규칙이 요구하는 지역적 일관성을 절(clause)로 인코딩하는 것이다 — 계산 과정 전체가 이 거대한 CNF 논리식이 만족 가능한 것과 정확히 대응하도록 만든다. 이 증명이 SAT를 NP-완전의 "첫 번째" 문제로 만들었고, 이후 카프(1972)를 비롯한 여러 연구자가 SAT에서 시작해 스케줄링, 집합 덮개(set cover, 이 문서의 미니 실험 주제), 배낭 문제, 외판원 문제(TSP)의 결정 버전 등 수십 개의 문제로 다항 시간 환원의 사슬을 이어 NP-완전성을 확산시켰다.

실무 관점

어려운 문제를 만났을 때의 선택지

문제가 NP-난해로 판명되면(또는 그럴 것으로 강하게 의심되면) "더 나은 알고리즘을 찾는다"가 아니라 "어떤 보장을 포기할 것인가"를 선택해야 한다.

• 작은 입력, 엄격한 최적성 요구: 완전 탐색, 동적 계획법, 분기 한정법(branch-and-bound) 같은 exact 접근이 여전히 통한다. 입력이 작으면 지수적 알고리즘도 현실적인 시간 안에 끝난다. 각 패러다임의 조건과 실패 지점은 1.3 알고리즘 설계 패러다임에서 다뤘다.
• 최악 성능 보장이 필요한 대규모 입력: 근사 알고리즘(approximation algorithm)은 최적해를 포기하는 대신, "최적의 몇 배 이내"라는 증명된 비율(approximation ratio)을 제공한다. 이 문서의 미니 실험에서 쓰는 greedy 집합 덮개도 특별한 우연이 아니라, 원소가 d개인 집합까지 다뤘을 때 최적의 H(d)(조화수) 배 이내라는 증명된 근사 비율을 갖는 것으로 알려져 있다 — "그때그때 다른 휴리스틱"이 아니라 보장이 있는 근사다.
• 평균적인 해 품질과 빠른 응답이 중요한 경우: greedy, 지역 탐색(local search), 메타휴리스틱은 최악 성능 보장 없이 실전 입력에서 좋은 해를 빠르게 낸다. 최적성 보장이 없다는 것을 명시적으로 받아들이는 선택이다.
• 복잡한 제약과 반복되는 모델 변경: SAT·SMT·ILP 솔버에 문제를 인코딩한다(2.1의 CNF·Tseitin 변환이 이 인코딩의 기반이다). 실무에서 중요한 것은 솔버의 결과 계약을 명시하는 것이다 — 제한 시간(timeout) 안에 답을 못 찾으면 무엇을 반환하는지, 반환된 해가 "증명된 최적(optimal)"인지 "지금까지 찾은 최선(feasible이지만 최적 미확인)"인지, unsatisfiable로 판정됐다면 그 근거(2.1의 미니 실험에서 손으로 해 본 것과 같은 unsat core)를 제공하는지.

통념을 정면으로 반박한다

"지수 시간으로 실행되면 그 문제는 NP-난해하다"는 틀렸다. 정규식 매칭 — 고정된 정규식과 문자열이 주어졌을 때 매칭 여부를 판정하는 문제 자체 — 은 2.2에서 다룬 lockstep NFA 시뮬레이션으로 입력 길이에 선형 시간에 풀린다. 즉 이 문제는 P에 속한다. 그런데도 특정 엔진이 그 문제를 백트래킹으로 구현하면 특정 입력(모호한 선택과 반복이 겹친 패턴)에서 지수 시간이 걸릴 수 있다 — 2.2의 미니 실험이 직접 측정했다. 이 지수 시간은 문제 자체의 하한이 아니라, 그 문제를 실행하는 특정 알고리즘(백트래킹, 상태 중복 제거 없음)의 선택이 만든 비효율이다. 같은 문제를 lockstep으로 실행하면 지수 시간이 사라진다는 사실 자체가, 지수 시간이 문제의 본질적 어려움이 아니었다는 것을 보여 준다. NP-난해성을 주장하려면 "이 구현이 느리다"가 아니라 "알려진 NP-난해 문제가 이 문제로 다항 시간 환원된다"는 것을 보여야 한다.

"SAT/SMT/ILP 솔버를 쓰면 NP-난해성이 사라진다"도 틀렸다. 현대 SAT 솔버는 CDCL(2.1에서 예고한 DPLL의 발전형), 절 학습(clause learning), 변수 순서 휴리스틱 같은 정교한 기법으로 변수 수백만 개짜리 산업 인스턴스를 실전에서 빠르게 푼다. 하지만 이것은 실전에서 나타나는 인스턴스의 구조를 활용한 결과이지, 최악의 경우 복잡도가 다항 시간으로 바뀐 것이 아니다. 의도적으로 구성된 적대적 인스턴스(예: pigeonhole principle을 인코딩한 CNF)는 여전히 최신 솔버도 지수 시간을 요구한다는 것이 알려져 있다. 솔버는 "이 문제 클래스의 많은 실전 인스턴스를 빠르게 푸는 훌륭한 도구"이지, "P = NP를 증명한 것"이 아니다.

더 깊이: greedy 집합 덮개의 근사 비율

이 문서의 미니 실험은 greedy가 최적을 놓치는 사례를 보여 주지만, "얼마나 나쁠 수 있는가"에는 상한이 있다. 원소를 최대 d개 포함하는 집합들로 구성된 인스턴스에서, greedy가 선택하는 집합 수는 최적해 크기의 H(d) = 1 + 1/2 + 1/3 + ... + 1/d(조화수) 배를 넘지 않는다는 것이 증명되어 있다. H(d)는 d가 커져도 ln(d) + 1 근처로 천천히만 자라므로, 최적해가 매우 나쁘게 벌어지는 것을 막아 주는 실질적인 보장이다. 이 상한이 최악의 경우에도 성립하는 증명된 경계라는 점이 근사 알고리즘을 "그냥 그럴듯한 휴리스틱"과 구분 짓는다 — 근사 알고리즘을 선택하는 실무적 이유가 여기에 있다.

미니 실험: 작은 집합 덮개에서 완전 탐색과 greedy를 비교한다

로그 소스 8개를 태그로 묶어 최소 개수의 집합으로 덮는 상황을 가정한다. A={1,2,3,4}, B={5,6,7,8}은 딱 절반씩 나눠 덮는 최적 조합(2개)이고, G1={1,2,3,5,6}은 A, B보다 원소가 하나 더 많아 greedy가 항상 먼저 고르게 되는 미끼 집합이다. 이어서 무작위로 생성한(재현 가능하도록 결정적 LCG로 생성) 더 큰 인스턴스에서 집합 수 m을 늘려 가며 완전 탐색의 방문 상태 수·시간과 greedy의 그것을 비교한다.

// set-cover.ts — node set-cover.ts 로 실행

interface CoverResult { chosen: number[]; size: number; statesExplored: number; elapsedMs: number; }

function toBitset(s: number[]): number { return s.reduce((acc, x) => acc | (1 << x), 0); }

// 완전 탐색: 선택 집합 수 k=1,2,...를 늘려가며 크기 k인 모든 조합을 시도한다.
// "상태를 몇 번 방문했는가"는 combo() 재귀 호출 횟수로 센다.
function exhaustiveSetCover(universeSize: number, sets: number[][]): CoverResult {
  const start = process.hrtime.bigint();
  const full = (1 << universeSize) - 1;
  const bitsets = sets.map(toBitset);
  const m = sets.length;
  let statesExplored = 0;

  for (let k = 1; k <= m; k++) {
    let answer: number[] | null = null;
    const combo = (from: number, chosen: number[], covered: number) => {
      if (answer) return;
      statesExplored++;
      if (chosen.length === k) { if (covered === full) answer = [...chosen]; return; }
      if (chosen.length + (m - from) < k) return; // 가지치기
      for (let i = from; i < m && !answer; i++) combo(i + 1, [...chosen, i], covered | bitsets[i]);
    };
    combo(0, [], 0);
    if (answer) {
      return { chosen: answer, size: k, statesExplored, elapsedMs: Number(process.hrtime.bigint() - start) / 1e6 };
    }
  }
  return { chosen: [], size: -1, statesExplored, elapsedMs: Number(process.hrtime.bigint() - start) / 1e6 };
}

// greedy: 남은 미해결 원소를 가장 많이 덮는 집합을 매번 고른다.
function greedySetCover(universeSize: number, sets: number[][]): CoverResult {
  const start = process.hrtime.bigint();
  const full = (1 << universeSize) - 1;
  const bitsets = sets.map(toBitset);
  let covered = 0;
  const chosen: number[] = [];
  let statesExplored = 0;
  while (covered !== full) {
    let bestIdx = -1, bestGain = -1;
    for (let i = 0; i < bitsets.length; i++) {
      statesExplored++;
      const gain = popcount(bitsets[i] & ~covered);
      if (gain > bestGain) { bestGain = gain; bestIdx = i; }
    }
    if (bestGain <= 0) break;
    chosen.push(bestIdx);
    covered |= bitsets[bestIdx];
  }
  return { chosen, size: chosen.length, statesExplored, elapsedMs: Number(process.hrtime.bigint() - start) / 1e6 };
}
function popcount(x: number): number { let c = 0; while (x) { c += x & 1; x >>= 1; } return c; }

console.log("=== 해 품질: greedy vs exhaustive ===");
const universeSize = 8;
const A = [0, 1, 2, 3], B = [4, 5, 6, 7], G1 = [0, 1, 2, 4, 5];
const exQuality = exhaustiveSetCover(universeSize, [A, B, G1]);
const grQuality = greedySetCover(universeSize, [A, B, G1]);
console.log(`exhaustive: 선택=[${exQuality.chosen}], 개수=${exQuality.size}, 방문 상태=${exQuality.statesExplored}`);
console.log(`greedy    : 선택=[${grQuality.chosen}], 개수=${grQuality.size}, 방문 상태=${grQuality.statesExplored}`);

console.log("\n=== 입력 크기(집합 수)에 따른 성장 ===");
function randomInstance(uSize: number, numSets: number, density: number, seed: number): number[][] {
  let s = seed;
  const rand = () => { s = (s * 1103515245 + 12345) & 0x7fffffff; return s / 0x7fffffff; };
  const sets: number[][] = [];
  for (let i = 0; i < numSets; i++) {
    const set: number[] = [];
    for (let e = 0; e < uSize; e++) if (rand() < density) set.push(e);
    sets.push(set);
  }
  return sets;
}
function coveringInstance(uSize: number, numSets: number, density: number, seedBase: number): number[][] {
  for (let attempt = 0; attempt < 50; attempt++) {
    const sets = randomInstance(uSize, numSets, density, seedBase + attempt * 9973);
    if (sets.reduce((acc, s) => acc | toBitset(s), 0) === (1 << uSize) - 1) return sets;
  }
  throw new Error("적당한 인스턴스를 찾지 못함");
}

console.log("m\tex.states\tex.ms\tgr.states\tgr.ms\tex.size\tgr.size");
for (let m = 12; m <= 30; m += 2) {
  const sets = coveringInstance(16, m, 0.22, 7 + m * 13);
  const ex = exhaustiveSetCover(16, sets);
  const gr = greedySetCover(16, sets);
  console.log(`${m}\t${ex.statesExplored}\t${ex.elapsedMs.toFixed(3)}\t${gr.statesExplored}\t${gr.elapsedMs.toFixed(3)}\t${ex.size}\t${gr.size}`);
}

Node.js v24.14.0, Apple M5 Pro, macOS 26.6.2에서 실행한 결과다.

=== 해 품질: greedy vs exhaustive ===
exhaustive: 선택=[0,1], 개수=2, 방문 상태=7
greedy    : 선택=[2,1,0], 개수=3, 방문 상태=9

=== 입력 크기(집합 수)에 따른 성장 ===
m	ex.states	ex.ms	gr.states	gr.ms	ex.size	gr.size
12	2850	0.469	72	0.020	6	6
14	11504	0.574	98	0.006	7	7
16	782	0.025	48	0.003	3	3
18	7536	0.258	90	0.004	5	5
20	5290	0.206	100	0.006	4	5
22	11796	0.342	110	0.004	5	5
24	19702	0.514	144	0.004	5	6
26	26566	0.691	130	0.009	5	5
28	1112	0.026	84	0.004	3	3
30	43956	1.051	150	0.005	5	5

첫 실험에서 exhaustive는 2개(A, B)로 정확히 덮지만, greedy는 원소가 하나 더 많은 G1을 먼저 고르는 바람에 그 뒤에 B, 마지막으로 남은 원소 하나를 위해 A까지 써서 3개가 필요해진다 — 최적보다 1개 더 쓴 것이다. 두 번째 표에서는 m(후보 집합 수)이 늘어남에 따라 exhaustive의 방문 상태 수가 대체로 커지는 추세를 보이지만(m=12의 2850에서 m=30의 43956까지), m=16이나 m=28처럼 우연히 쉬운 인스턴스에서는 오히려 줄기도 한다 — 같은 문제 크기라도 인스턴스의 구조에 따라 실제 탐색 비용이 크게 달라질 수 있다는 것을 보여 준다. 반면 greedy의 상태 수는 m에 거의 선형으로만 늘고(라운드 수 × 후보 집합 수 정도), 실행 시간은 항상 exhaustive보다 훨씬 작다. 몇몇 지점(m=20, 24)에서는 greedy가 최적보다 1개 더 많은 집합을 선택했다 — 속도의 대가로 해의 품질을 완벽히 보장하지 못한다는 것이 이 실험에서도 재현된다.

이 결과에서 놓치지 말아야 할 것은, exhaustive의 방문 상태 수가 들쭉날쭉한 것이 집합 덮개 문제가 NP-난해가 아니라는 증거가 아니라는 점이다. 최악의 경우(입력을 의도적으로 어렵게 구성하면) exhaustive의 비용은 여전히 조합적으로 폭발한다 — 이번 실험의 무작위 인스턴스들이 우연히 다양한 난이도를 가졌을 뿐이다. "이번에 측정한 인스턴스가 빨리 끝났다"와 "이 문제는 항상 빨리 풀린다"를 혼동하지 않는 것이, 이 챕터가 반복해서 강조하는 worst case 기준의 실무적 의미다.

정리

• 복잡도 클래스는 결정 문제를 입력 크기의 함수로, 최악의 경우를 기준으로 정의한다. 최적화 문제는 대응하는 결정 문제로 바꿔 분류한다.
• P는 다항 시간에 풀리는 문제의 클래스이고, NP는 "yes" 인증서를 다항 시간에 검증할 수 있는 문제의 클래스다. NP는 non-polynomial의 약자가 아니며, P = NP인지는 아직 증명되지 않은 미해결 문제다.
• NP-난해는 NP의 모든 문제가 다항 시간 환원되는 하한을, NP-완전은 그 하한이면서 동시에 NP에도 속하는 것을 뜻한다. A ≤p B는 "B를 다항 시간에 풀 수 있으면 A도 풀 수 있다"는 방향이다.
• Cook–Levin 정리는 SAT가 NP-완전임을 보였고, 이후 다항 시간 환원의 사슬로 스케줄링·집합 덮개·TSP 등 수십 개의 실무 문제가 NP-완전으로 밝혀졌다.
• 문제가 NP-난해로 판명되면 exact(작은 입력), 근사(증명된 최악 비율이 필요한 대규모 입력), 휴리스틱(평균 품질과 속도 우선), 솔버(복잡한 제약과 잦은 모델 변경) 중 어떤 보장을 포기할지 선택해야 한다.
• 지수 시간 실행은 알고리즘 선택의 결과일 수도, 문제 자체의 하한일 수도 있다. ReDoS는 전자(문제는 P에 속하지만 백트래킹이라는 실행 전략이 지수 시간을 만든 것)의 대표 사례다. 솔버가 실전 인스턴스를 잘 푸는 것은 최악의 경우 보장이 바뀐 것이 아니다.

확인 문제

1. 신입 개발자가 "NP는 non-polynomial의 약자이므로, NP에 속한 문제는 다항 시간에 풀 수 없다는 것이 증명되어 있다"고 발표 자료에 적었다. 어디가 틀렸는지 두 가지로 나눠 지적하라.

정답과 해설

첫째, NP는 non-polynomial이 아니라 nondeterministic polynomial time의 약자다 — 비결정론적 튜링 기계가 다항 시간에 판정할 수 있다는(또는 동치로, "yes" 인증서를 다항 시간에 검증할 수 있다는) 뜻이다. 둘째, "NP에 속한 문제는 다항 시간에 풀 수 없다"는 것은 증명된 사실이 아니라 P = NP인지가 아직 아무도 증명하지 못한 미해결 문제라는 뜻이다. 실제로 P는 NP의 부분집합이므로(P ⊆ NP), P에 속한 문제들은 NP에도 속하면서 동시에 다항 시간에 풀린다 — "NP에 속하면 다항 시간에 못 푼다"는 이 사실만으로도 반증된다.

2. 동료가 "우리 백트래킹 정규식 매처가 특정 입력에서 지수 시간이 걸리는 것을 보니, 정규식 매칭 문제 자체가 NP-난해인 것 같다"고 주장한다. 이 챕터의 논증으로 반박하라.

정답과 해설

정규식 매칭 문제(고정된 정규식과 문자열이 주어졌을 때 매칭 여부 판정) 자체는 2.2에서 다룬 lockstep NFA 시뮬레이션으로 입력 길이에 선형인 시간에 풀린다 — 즉 이 문제는 P에 속한다. 관찰된 지수 시간은 문제의 하한이 아니라 백트래킹이라는 특정 실행 전략(상태 중복 제거 없이 깊이 우선 탐색)의 비효율이다. 문제 자체가 NP-난해임을 주장하려면 "이 구현이 느리다"가 아니라 "알려진 NP-난해 문제가 이 문제로 다항 시간 환원됨"을 보여야 하는데, 정규식 매칭에는 그런 환원이 없고 오히려 다항 시간(선형) 알고리즘이 존재한다. 지수 시간 구현의 존재와 문제의 다항 시간 알고리즘의 존재는 모순되지 않는다 — 같은 문제에 나쁜 알고리즘과 좋은 알고리즘이 공존할 수 있을 뿐이다.

3. 물류 팀이 매주 배송 경로 최적화 문제를 풀어야 하는데, 다음 두 시나리오 중 어떤 접근을 선택할지 이 문서의 기준으로 판단하라. (a) 배송지 8곳 이내의 소규모 지역 배송으로, 완벽한 최소 비용 경로가 필요하다. (b) 배송지 5,000곳 규모의 전국 배송으로, 제약(차량 수, 시간대, 냉장 여부)이 주마다 바뀌고 "합리적으로 좋은" 경로면 충분하되 배송 마감 안에 답이 나와야 한다.

정답과 해설

(a)는 입력이 작고 엄격한 최적성이 필요한 경우다 — 완전 탐색이나 동적 계획법 같은 exact 접근이 적합하다. 배송지 8곳이면 최악의 경우도 현실적인 시간 안에 끝날 만큼 작다. (b)는 대규모 입력에 제약이 자주 바뀌고 엄격한 최적성보다 정해진 시간 안의 답이 중요한 경우다 — 매번 새 exact 알고리즘을 짜기보다 SAT/SMT/ILP 솔버에 제약을 모델링하고 timeout을 걸어, 그 안에 찾은 최선의 feasible한 해(최적 증명 여부와 함께)를 받는 접근이 적합하다. 제약이 자주 바뀐다는 것은 매번 알고리즘을 새로 설계하는 비용을 감당하기 어렵다는 뜻이고, 이는 손으로 짠 휴리스틱보다 선언적으로 제약을 바꿔 넣을 수 있는 솔버 기반 접근의 강점과 맞는다. 다만 솔버를 쓴다고 문제의 NP-난해성이 사라지는 것은 아니므로, timeout 안에 최적을 증명하지 못하면 "최선의 feasible해"로 결과 계약을 명시해야 한다.

참고 자료

• Stephen Cook, "The Complexity of Theorem-Proving Procedures" (Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971) — SAT가 NP-완전임을 보인 Cook–Levin 정리의 원 논문.
• Richard Karp, "Reducibility Among Combinatorial Problems" (1972) — SAT에서 출발한 다항 시간 환원으로 21개 조합 문제의 NP-완전성을 보인 원 논문.
• Michael Garey, David Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979) — NP-완전 문제 목록과 환원 증명 기법의 표준 카탈로그.
• Vijay Vazirani, Approximation Algorithms (Springer, 2001) — greedy 집합 덮개의 H(d) 근사 비율을 포함한 근사 알고리즘의 증명들을 다루는 표준 교재.
• CWE-1333, Inefficient Regular Expression Complexity — ReDoS를 알고리즘 취약점으로 분류한 공식 항목.
• OWASP, Regular expression Denial of Service - ReDoS — ReDoS의 공격 패턴과 완화책을 다루는 실무 자료.