I've stumbled upon this Question:

  • We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t if $ |w| \geq n \ than \ |f(w)| < |w| $. Also, $A,B \notin \{\Sigma^*,\emptyset \} $. Prove there is such a reduction which is also polynomial-time reduction from any languages $ A,B \in P $.
  • This was my approach: Take $ w' $ to be the shortest word in $B$ and define $f(w) = w'$ for every $w \in A $. I'm pretty sure the idea is correct because we simply choose $n = |w'| + 1$ and then obviously for every $w \ s.t \ |w| >= n \ we \ get \ |w| > n-1 = |w'| = |f(w)| $

So my question is, can I really choose a word $ w' $ to be the shortest word in $B$?

Also, am I correct with my approach?



1 Answer 1


In order to prove your result, you don't need to give an algorithm that gets a description of $A$ and $B$ and outputs a description of $f$, a polytime shortening reduction from $A$ to $B$. It's enough to show that for each $A$ and $B$, such an $f$ exists. If a language $B$ is different from $\emptyset$ and $\Sigma^*$ then there is some word $x \in B$ and some other word $y \notin B$, and these are enough to carry out your construction (you don't actually need them to be the shortest word).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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