Dalam ilmu komputer, khususnya dalam kajian algoritma aproksimasi, reduksi L (bahasa Inggris: L-reductioncode: en is deprecated , singkatan dari linear reduction) adalah suatu transformasi pada masalah optimisasi yang mempertahankan sifat keteraproksimasian (approximability) secara linear. Dengan kata lain, jika suatu masalah dapat didekati dengan tingkat aproksimasi tertentu, maka sifat tersebut tetap terjaga secara proporsional setelah masalah itu ditransformasikan. Reduksi L merupakan salah satu jenis reduksi yang mempertahankan sifat aproksimasi (approximation-preserving reduction). Dalam kajian keteraproksimasian masalah optimisasi, reduksi L memiliki peran yang serupa dengan reduksi polinomial dalam kajian kompleksitas komputasi untuk masalah keputusan.

Istilah reduksi L terkadang juga digunakan untuk merujuk pada reduksi ruang logaritmik (log-space reduction), berdasarkan analogi dengan kelas kompleksitas L. Namun, penggunaan tersebut mengacu pada konsep yang berbeda dan tidak berkaitan dengan reduksi L yang dibahas di atas.

Sebelum memberikan definisinya, ada baiknya mengingat kembali beberapa konsep dasar dalam masalah optimisasi, yang akan dijelaskan melalui contoh Permasalahan Penjual Keliling (TSP).

Pertama, instans (instance) adalah masukan dari suatu masalah, yaitu sekumpulan informasi yang diperlukan untuk menghitung sebuah solusi. Pada TSP, sebuah instans berupa himpunan berhingga kota beserta jarak antara setiap pasangan kota tersebut.

Selanjutnya, solusi adalah sebuah rute (tour) yang mengunjungi seluruh kota. Dalam kasus TSP, biaya (cost) suatu solusi adalah panjang total rute tersebut. Notasi ${\textstyle \mathrm {OPT_{TSP}} (x)}$ digunakan untuk menyatakan biaya dari solusi optimal bagi instans ${\textstyle x}$, yaitu panjang rute terpendek yang dapat diperoleh.

Misalkan ${\displaystyle A}$ dan ${\displaystyle B}$ adalah dua masalah optimisasi, sedangkan ${\displaystyle c_{A}}$ dan ${\displaystyle c_{B}}$ masing-masing merupakan fungsi biaya (cost function) untuk kedua masalah tersebut.

Sepasang fungsi ${\displaystyle f}$ dan ${\displaystyle g}$ disebut sebagai reduksi L apabila seluruh syarat berikut terpenuhi:

• Fungsi ${\displaystyle f}$ dan ${\displaystyle g}$ dapat dihitung dalam waktu polinomial;
• Jika ${\textstyle x}$ adalah sebuah instans dari masalah ${\displaystyle A}$, maka ${\displaystyle f(x)}$ merupakan sebuah instans dari masalah ${\displaystyle B}$;
• Jika ${\displaystyle y'}$ adalah sebuah solusi untuk ${\displaystyle f(x)}$, maka ${\displaystyle g(y')}$ merupakan sebuah solusi untuk ${\displaystyle x}$;
• Terdapat suatu konstanta positif ${\displaystyle \alpha }$ sehingga berlaku ${\displaystyle \mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)}$;
• Terdapat suatu konstanta positif ${\displaystyle \beta }$ sehingga, untuk setiap solusi ${\displaystyle y'}$ dari ${\displaystyle f(x)}$, berlaku ${\displaystyle |\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|}$.

Dengan kata lain, kondisi keempat menyatakan bahwa biaya solusi optimal pada masalah hasil transformasi tidak boleh melebihi suatu kelipatan konstan dari biaya solusi optimal pada masalah asal. Sementara itu, kondisi kelima memastikan bahwa selisih antara biaya solusi yang diperoleh dan biaya solusi optimal pada masalah asal tetap sebanding (dibatasi secara linear) dengan selisih yang sama pada masalah hasil transformasi. Kedua syarat inilah yang membuat reduksi L mampu mempertahankan sifat keteraproksimasian dari suatu masalah optimisasi.

Berikut ini adalah contoh reduksi L dari MAX 3-SAT ke MAX 2-SAT.

Misalkan terdapat sebuah instans MAX 3-SAT ${\displaystyle \varphi :=\bigwedge _{i=1}^{m}(\ell _{i}^{1}\lor \ell _{i}^{2}\lor \ell _{i}^{3})}$ dengan ${\displaystyle \ell _{i}^{1}}$, ${\displaystyle \ell _{i}^{2}}$, dan ${\displaystyle \ell _{i}^{3}}$ merupakan literal (sebuah variabel Boolean atau negasinya). Fungsi ${\displaystyle f}$ dalam reduksi L ini didefinisikan sebagai berikut. Instans MAX 2-SAT yang dihasilkan, yaitu ${\displaystyle f(\varphi )}$, adalah rumus

${\displaystyle f(\varphi ):=\bigwedge _{i=1}^{m}(\ell _{i}^{1}\land \ell _{i}^{2}\land \ell _{i}^{3}\land \ell _{i}^{4}\land ({\bar {\ell }}_{i}^{1}\lor {\bar {\ell }}_{i}^{2})\land ({\bar {\ell }}_{i}^{1}\lor {\bar {\ell }}_{i}^{3})\land ({\bar {\ell }}_{i}^{2}\lor {\bar {\ell }}_{i}^{3})\land (\ell _{i}^{1}\lor {\bar {\ell }}_{i}^{3})\land (\ell _{i}^{2}\lor {\bar {\ell }}_{i}^{4})\land ({\bar {\ell }}_{i}^{3}\lor {\bar {\ell }}_{i}^{4})}$

dengan ${\displaystyle \ell _{i}^{4}}$ merupakan sebuah variabel baru yang ditambahkan dan tidak terdapat pada rumus semula.

Selanjutnya, fungsi ${\displaystyle g}$ dalam reduksi L didefinisikan sebagai berikut. Diberikan sebuah penugasan nilai kebenaran (truth assignment) ${\displaystyle \nu }$ untuk rumus ${\displaystyle f(\varphi )}$, maka ${\displaystyle g(\nu )}$ adalah penugasan yang sama, tetapi hanya diterapkan pada variabel-variabel yang terdapat di dalam ${\displaystyle \varphi }$. Dengan kata lain, nilai kebenaran dari seluruh variabel baru ${\displaystyle \ell _{i}^{4}}$ diabaikan.

Dapat dibuktikan bahwa reduksi ini memenuhi dua sifat berikut.

• Terdapat batas ${\displaystyle \mathrm {OPT_{MAX-2SAT}} (f(\varphi ))\leq 13\mathrm {OPT_{MAX-3SAT}} (\varphi )}$.
• Selain itu, untuk setiap penugasan ${\displaystyle \nu '}$, berlaku ${\displaystyle |\mathrm {OPT_{MAX3SAT}} (\phi )-c_{MAX3SAT}(g(\nu '))|\leq |\mathrm {OPT_{MAX-2SAT}} (f(\phi ))-c_{MAX-2SAT}(y')|}$.

• Papadimitriou, Christos; Yannakakis, Mihalis (1988). Optimization, approximation, and complexity classes. ACM Press. doi:10.1145/62212.62233. ISBN 978-0-89791-264-8.
• Crescenzi, P. (1997). A short guide to approximation preserving reductions. IEEE Comput. Soc. hlm. 262–273. doi:10.1109/CCC.1997.612321. ISBN 978-0-8186-7907-0.
• Kann, Viggo (1992). On the approximability of NP-complete optimization problems. Stockholm: Tekniska högsk. ISBN 978-91-7170-082-7.