2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ What have you tried? Can you explain the problem in your own words? $\endgroup$
    – Pål GD
    Jun 9, 2019 at 15:57
  • $\begingroup$ @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$. $\endgroup$
    – Um Shmum
    Jun 9, 2019 at 16:14

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.