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.

  • 2
    $\begingroup$ Just decide B within the reduction and output a word in A / not in A accordingly $\endgroup$
    – dave
    Feb 8, 2017 at 16:10
  • $\begingroup$ @dave Make an answer? $\endgroup$ Feb 8, 2017 at 19:03

1 Answer 1


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.


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.