다항 시간 환원 (polynomial-time reduction)
쉽게 풀면
다항 시간 환원은 '문제 A를 풀고 싶은데, A를 문제 B로 바꿔서 B를 푸는 알고리즘을 빌려 쓴다'는 아이디어다. 이 변환 작업 자체가 다항 시간 안에 끝나야 한다. 이를 통해 문제들 사이의 상대적 난이도를 비교할 수 있고, NP-완전성을 증명하는 표준 도구로 쓰인다.
왜 중요한가
다항 시간 환원은 새로 마주친 문제를 매번 처음부터 분석하지 않고도, 이미 잘 알려진 문제와의 관계를 통해 그 계산적 난이도를 판단할 수 있게 해주는 핵심 도구이기 때문에 이론전산학 논문에서 필수적으로 다뤄집니다. 특히 NP-완전성을 증명하는 표준 절차 자체가 환원에 기반하고 있어, 새로운 최적화 문제나 알고리즘 설계 문제를 다루는 논문에서 그 문제가 왜 효율적으로 풀기 어려운지(혹은 쉬운지)를 정당화하는 근거로 반복해서 사용됩니다.
논문에서는 이렇게 쓰입니다
새로운 문제의 난이도를 이미 알려진 문제와 비교하거나 NP-완전성을 증명할 때 환원 과정을 설명하는 데 쓰인다.
운영체제·네트워크 자원 관리 논문에서는 실무적으로 마주친 최적화 문제가 이론적으로 얼마나 어려운지를 증명한 뒤, 정확한 해 대신 근사 알고리즘으로 접근하는 근거를 마련한다는 뜻입니다.
암호학 논문에서는 어떤 공격이 성공하려면 결국 풀기 어렵다고 알려진 문제를 풀어야 한다는 점을 환원으로 보여, 프로토콜의 안전성을 간접적으로 증명한다는 의미입니다.
조금 더 깊게 보면
환원에는 여러 종류가 있는데, 가장 널리 쓰이는 카프 환원(Karp reduction, 다대일 환원)은 문제 A의 모든 입력을 문제 B의 입력 하나로 바꾸는 방식이고, 튜링 환원(Turing reduction)은 B를 푸는 알고리즘을 여러 번 호출할 수 있도록 허용하는 더 넓은 개념입니다. NP-완전성을 정의할 때는 보통 카프 환원을 기준으로 삼으며, 어떤 문제가 NP에 속하면서 이미 알려진 NP-완전 문제로부터 카프 환원이 가능하면 그 문제도 NP-완전임이 증명됩니다. 이러한 환원 관계들을 사슬처럼 연결해 나가는 것이 새로운 문제의 복잡도 클래스를 규명하는 표준적인 연구 방법입니다.
주의할 점
환원의 방향에 주의해야 한다. A가 B로 환원된다는 것은 B가 A보다 어렵거나 같다는 뜻이지 그 반대가 아니다.