We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ satisfying $|x|\ge n \implies |f(x)|\lt |x|$.
Assuming $P\ne NP$
Prove\Disprove: Every two NP-complete languages $L_1,L_2$ are decreasing reducible.
I'd appreciate a hint or direction
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| < 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$.
