# Shorten Length Reduction

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?

Thanks!

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