L-환산(L-reduction, linear reduction)은 최적화 문제 간의 근사 비율을 선형 보존하는 환산이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다.
최적화 문제
와 각 문제의 비용 함수
에 대해서, 함수
와 양수
가 다음의 조건을 만족할 경우
를 A에서 B로의 L-환산이라고 정의한다.
- 두 함수
는 다항 시간에 계산가능하다.
- 문제
에 속하는 입력
에 대해,
는 문제
의 입력이다.
- 문제
에 속하는 입력
의 해가
일 때,
는 문제
의 입력
에 해당하는 해이다.
- 입력
에 대한 최적 비용이
일 때, 모든
에 대해
를 만족하는 양수
가 존재한다.
- 입력
의 해가
일 때, 모든
에 대해
를 만족하는 양수
가 존재한다.
L-환산이 존재할 경우, 만약 A에 대한
-근사 알고리즘이 존재한다면 그 알고리즘은 B에 대한
-근사 알고리즘으로도 사용할 수 있다. 즉, B에 대한 다항 시간 근사 해법(PTAS)이 존재하게 된다.