# How could I prove that $B$ reduces to $A$ in polynomial time in this case?

Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time?

Thanks in advance.

• Just decide B within the reduction and output a word in A / not in A accordingly – dave Feb 8 '17 at 16:10
• @dave Make an answer? – Yuval Filmus Feb 8 '17 at 19:03

## 1 Answer

Take $a\in A$ and $b \notin A$.

the reduction defined as follows: $$f(x)=\begin{cases} a & x\in B\\ b & x\notin B \end{cases}$$

It is easy to see that $f \in \text{POLY}$ since $B\in\text{P}$, and the correctness is trivial.