Prove that every problem in P is reducible


You've sort of answered your own question.

"$A$ is reducible to $B$" means "Given a black box that solves problem $B$ in constant time, we can solve problem $A$ in polynomial time." Since $A$ is in $P$, this statement is always true: we can simply throw away our black box to $B$ and solve $A$ without it.


Related videos on Youtube

Author by


Updated on June 15, 2022


  • Takkun
    Takkun less than a minute

    Possible Duplicate:
    For two problems A and B, if A is in P, then A is reducible to B?

    Given two problems $A$ and $B$, if $A$ is in $\def\P{{\mathcal P}}\P$ then $A$ is reducible to $B$. ($A < B$)

    Why does it not matter if $B$ is in $\P$ or $\mathcal{NP}$?
    Why can just knowing that $A$ is in $\P$ mean that it is reducible regardless of $B$?

    • Erick Wong
      Erick Wong over 9 years
      Please state your definition of reducible. In these questions it is vital that you know what the terms mean with great precision.
  • Takkun
    Takkun over 9 years
    Thanks, rewriting it like that clears up some of my confusion.
  • eva
    eva over 7 years
    I have a question regarding this answer: Why does B have to be solved in constant time?