계산 복잡도 환원: 문제의 난도를 비교하는 방향
환원은 문제 A의 입력을 문제 B의 입력으로 바꾸고, B의 답에서 A의 답을 얻는 방법이다. B를 풀 수 있다면 A도 풀 수 있도록 연결한다. 난도를 증명할 때 가장 자주 틀리는 부분은 이 방향이다.
A≤ₚB는 B의 풀이를 이용해 A를 풀 수 있다는 뜻이다.
A를 B로 바꾸면 무엇을 얻는가
다항시간 다대일 환원 A≤ₚB는 다항시간에 계산되는 변환 f가 있어서 x가 A의 예 입력인 것과 f(x)가 B의 예 입력인 것이 동치라는 뜻이다. 변환은 예 입력뿐 아니라 아니오 입력도 보존해야 한다.
Input x for problem A
|
v
Polynomial-time transformation f
|
v
Input f(x) for problem B
|
v
Solver for B returns YES or NO
|
v
Use the same answer for A
B에 빠른 풀이가 있고 변환도 빠르면 A도 빠르게 풀 수 있다. 반대로 A가 어렵다고 이미 알려졌다면 A≤ₚB를 보여 B가 적어도 그 어려움을 담고 있음을 설명한다. B≤ₚA를 보여 놓고 B가 어렵다고 결론 내리면 방향이 뒤집힌다.
3-SAT를 클릭 문제로 바꾸기
3-SAT 식이 m개 절로 이루어져 있다고 하자. 각 절의 세 리터럴을 정점으로 만들고, 서로 다른 절에서 온 정점 중 x와 ¬x처럼 모순되지 않는 두 정점 사이에 간선을 둔다. 클릭 목표 크기를 m으로 정한다.
식을 만족하는 대입이 있으면 각 절에서 참인 리터럴 하나를 선택할 수 있다. 이 선택들은 서로 모순되지 않으므로 모두 연결된 크기 m 클릭을 이룬다. 반대로 m 클릭은 같은 절의 정점 사이에 간선이 없으므로 절마다 하나를 고르며, 모순된 리터럴도 함께 포함할 수 없다. 그 선택을 참으로 만드는 대입으로 모든 절을 만족시킬 수 있다.
두 방향의 논증이 예·아니오 동치를 만든다. 그래프의 정점 수는 3m이고 모든 쌍을 검사해도 다항 크기와 시간이므로 다항 환원이 된다. 지수 크기의 그래프를 만드는 변환은 같은 난도 증명에 사용할 수 없다.
환원 종류와 보장 범위를 구분한다
계산 가능성 논의에서는 계산 가능한 환원만으로 충분할 수 있지만 복잡도 논의에서는 변환 비용 제한이 중요하다. 여러 번 B의 풀이를 호출하는 튜링 환원과 입력 하나로 바꾸는 다대일 환원도 다른 개념이다.
환원은 정확성을 보존한 입력 변환이지 문제 이름을 비슷한 비유로 바꾸는 일이 아니다. 입력 크기, 목표값, 예·아니오 보존, 변환 시간, 역방향 해석을 모두 확인해야 한다. 이 구조가 NP 완전성이나 결정 불가능성 증명의 핵심 도구가 된다.
예 입력 하나에서 변환이 잘 작동하는 것을 보여 주는 것만으로 환원이 증명되지는 않는다. 모든 유효 입력에서 양방향 동치가 성립해야 한다. 특히 아니오 입력이 예로 바뀌면 B의 정확한 풀이를 사용해도 A의 답을 틀린다. 변환이 사용하는 숫자의 부호화 길이와 그래프 크기도 입력 크기에 대한 다항식으로 제한되어야 한다.