Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|cite|improve this question

marked as duplicate by Henning Makholm, MJD, Thomas, Rudy the Reindeer, draks ... Oct 9 '12 at 9:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Please state your definition of reducible. In these questions it is vital that you know what the terms mean with great precision. – Erick Wong Oct 8 '12 at 16:48

1 Answer 1

up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks, rewriting it like that clears up some of my confusion. – Takkun Oct 8 '12 at 17:01
I have a question regarding this answer: Why does B have to be solved in constant time? – eva Feb 12 at 16:10

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