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 '17 at 16:10
  • $\begingroup$ @dave Make an answer? $\endgroup$ – Yuval Filmus Feb 8 '17 at 19:03

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, privacy policy and cookie policy

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