Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?
Let $L$ be any NP-complete language, and consider what happens when $L_1 = L_2 = L$. Given an instance $x$, by applying $f$ a linear number of times we would get that $x \in L$ iff $y \in L$, where $|y| &lt; n$. Since there are only finitely many strings of length smaller than $n$, we can hardcode the correct answer for these strings, thus obtaining a polynomial time algorithm for $L$.