환원: 문제의 어려움을 옮기는 기술

지난 글에서 복잡도 클래스들의 지도를 그렸습니다. 그 지도를 떠받치는 가장 중요한 도구가 이번 글의 주제, 환원(reduction)입니다. NP-완전성을 정의할 때도, 클래스 사이의 관계를 증명할 때도, “이 문제는 저 문제만큼 어렵다”고 말할 때도 모두 환원이 등장했습니다. 환원은 한 문제의 어려움을 다른 문제로 옮기는 기술이며, 이론 컴퓨터 과학 전체의 접착제입니다.

환원이란

문제 A를 문제 B로 환원한다는 것은, A의 모든 입력을 B의 입력으로 변환하는 방법을 만들되, 답이 보존되도록 하는 것입니다. A의 입력 x를 B의 입력 f(x)로 바꿨을 때, x의 답이 “예”인 것과 f(x)의 답이 “예”인 것이 정확히 일치해야 합니다.

이때 변환 f가 다항 시간에 계산 가능하면, 이를 다항 시간 다대일 환원(many-one reduction)이라 부르고 A ≤ₚ B로 씁니다. 이 기호는 “A는 B보다 어렵지 않다”, 즉 B를 풀 수 있으면 A도 풀 수 있다는 뜻입니다.

x  --f-->  f(x)
A의 답(x) = B의 답(f(x))     # 답 보존
f 는 다항 시간             # 어려움이 정확히 전달

어려움은 위로, 쉬움은 아래로

환원의 묘미는 양방향으로 정보를 전달한다는 데 있습니다. A ≤ₚ B가 성립할 때:

• 쉬움이 내려간다: B가 쉬우면(다항 시간) A도 쉽다. f로 변환한 뒤 B 해결기를 돌리면 되니까요.
• 어려움이 올라간다: A가 어려우면 B도 어렵다. 만약 B가 쉽다면 위 논리로 A도 쉬워져 모순이기 때문입니다.

바로 이 두 번째 방향이 NP-완전성 증명의 엔진입니다. “이미 어렵다고 알려진 문제 A를 새 문제 B로 환원하면, B도 최소한 A만큼 어렵다”는 결론이 나옵니다.

변환은 다항 시간이어야 한다

왜 변환 f가 다항 시간이어야 할까요? 만약 변환 자체가 지수 시간이 걸린다면, “B가 다항 시간에 풀린다”는 사실에서 “A도 다항 시간”이라는 결론을 끌어낼 수 없습니다. 변환에서 이미 지수 시간을 써버렸기 때문입니다. 환원이 어려움을 정확히 전달하려면, 변환 비용이 우리가 측정하려는 다항/지수 경계보다 작아야 합니다. 그래서 다항 시간 환원이 표준이 됩니다.

구체적인 예: 독립 집합 → 정점 덮개

추상적인 정의를 실제 환원으로 확인해 봅시다. 두 그래프 문제를 봅니다.

• 독립 집합(Independent Set): 서로 간선으로 이어지지 않은 정점들의 집합. 크기 k 이상인 독립 집합이 있는가?
• 정점 덮개(Vertex Cover): 모든 간선이 적어도 한 끝점을 포함하도록 하는 정점 집합. 크기 k 이하인 정점 덮개가 있는가?

이 둘은 놀랍도록 단순한 관계로 묶입니다. 정점 집합 S가 독립 집합인 것과, 그 여집합 V∖S가 정점 덮개인 것은 동치입니다. S 안의 두 정점 사이에 간선이 없다는 말은, 모든 간선이 적어도 한 끝점을 V∖S에 둔다는 말과 같기 때문입니다.

# 독립 집합 문제를 정점 덮개 문제로 환원
def reduce_IS_to_VC(graph, n, k):
    # "크기 ≥ k 독립 집합?" 을
    # "크기 ≤ n - k 정점 덮개?" 로 변환
    new_k = n - k
    return (graph, new_k)   # 그래프는 그대로, k만 변환 — O(1)

변환은 그래프를 그대로 두고 임곗값만 n − k로 바꾸는, 사실상 상수 시간 작업입니다. 두 문제 사이의 어려움이 이 한 줄로 옮겨집니다. 한쪽이 NP-완전임을 알면 다른 쪽도 즉시 NP-완전이 됩니다.

환원의 종류

이 글에서 다룬 다대일 환원이 가장 흔하지만, 다른 형태도 있습니다.

환원 종류	특징
다대일(many-one, ≤ₚ)	x를 f(x) 하나로 변환, 답 그대로 사용
튜링(Turing, Cook)	B를 부속 호출(oracle)로 여러 번 사용 가능
로그 공간 환원	변환을 로그 공간으로 — 더 미세한 클래스 구분

NP-완전성 정의에는 보통 다대일 환원을 쓰고, 더 강력한 튜링 환원은 NP-난해 같은 더 넓은 개념에서 쓰입니다.

환원적 사고의 가치

환원은 이론을 넘어 실전 문제 해결의 사고방식이기도 합니다. 새로운 문제를 만났을 때, 우리는 종종 이렇게 생각합니다. “이거 혹시 내가 아는 그 문제 아닌가?” 최대 유량으로, 이분 매칭으로, 최단 경로로 환원되는 순간 문제는 풀린 것이나 다름없습니다. 지금까지 다룬 수많은 알고리즘이 사실은 서로의 환원으로 연결돼 있었습니다.

• 이분 매칭은 최대 유량으로 환원됩니다.
• 많은 스케줄링·할당 문제가 그래프 문제로 환원됩니다.
• 어려운 문제는 SAT나 정수 계획법으로 환원해 범용 솔버에 맡깁니다.

환원은 두 얼굴을 가집니다. 한편으로는 “이 문제는 본질적으로 어렵다”는 불가능성의 증거이고, 다른 한편으로는 “이미 풀린 문제로 바꿔 풀자”는 가장 강력한 문제 해결 전략입니다. 어떤 알고리즘을 새로 발명하기 전에, 그것이 이미 아는 문제로 환원되지 않는지 묻는 습관 — 그것이 알고리즘을 길게 공부한 사람의 가장 값진 직관입니다.

기초 분석에서 출발해 자료구조, 그래프, 정렬과 탐색, 동적 계획법, 문자열, 정수론, 계산기하, 그리고 복잡도 이론까지 — 알고리즘이라는 넓은 대륙을 함께 가로질렀습니다. 환원이 보여주듯, 이 모든 주제는 따로 떨어진 섬이 아니라 서로 연결된 하나의 지형입니다.

---

지난 글: 복잡도 클래스: P, NP, PSPACE의 지도

읽어주셔서 감사합니다. 😊