# Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

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

• What have you tried? Can you explain the problem in your own words? – Pål GD Jun 9 '19 at 15:57
• @PålGD I know every two NP-complete languages are polynomial reducible. Choosing some two NP-complete languages, I'd like to show they can not be decreasing reducible, i.e. for large enough $x$ the length of the image of $x$ decreases for every $x$. – Um Shmum Jun 9 '19 at 16:14

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$$.