0
$\begingroup$

If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a $P$-problem would be impossible?

$\endgroup$
  • $\begingroup$ Have you read the definition of these notions you use? $\endgroup$ – Raphael Mar 19 '14 at 0:04
5
$\begingroup$

Since $P \subseteq NP$, every problem in $P$ is also in $NP$. So in both cases there is an $NP$-problem that can be reduced to a $P$-problem. Simply choose a problem in $P$ as the $NP$-problem and the same problem as the $P$-problem.

If you replace $NP$-problem by $NP$-complete problem, both of your statements hold.

$\endgroup$

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.