환산(다항 시간 환산)

문제 A 의 입력을 다항 시간에 문제 B 의 입력으로 바꾸되 답(예/아니오)이 그대로 유지되게 하는 변환이다(귀착·변환이라고도 한다). A 가 B 로 환산되면 B 를 푸는 빠른 알고리즘으로 A 도 빠르게 풀 수 있으므로 「B 는 적어도 A 만큼 어렵다」고 말한다. 따라서 B 가 쉬우면 A 도 쉽고, A 가 어려우면 B 도 어렵다. NP-완전성은 환산으로 정의되며, 서로 무관해 보이는 수천 가지 문제가 환산으로 한데 묶인다. 입력을 한 번 바꾸는 카프 환산과 B 를 여러 번 불러 쓰는 쿡(튜링) 환산을 구분하기도 한다.