4
$\begingroup$

Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?

$\endgroup$
8
$\begingroup$

Of course. Just take B=A, since every P problem is in NP.

$\endgroup$
  • $\begingroup$ Or take $B$ to be any NP-complete problem, or any problem in P. $\endgroup$ – David Richerby Nov 29 '14 at 18:15
1
$\begingroup$

Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P. We have CNFSAT( http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) which is an NP-complete problem. We can convert all 2-sat instances to cnfsat instances

If we have a 2-SAT formula like this:

$$ (x_{1} \vee x_{2}) \wedge (\neg x_{3} \vee x_{4}) $$

we can convert it to CNFSAT by inserting a dummy variable in each clause:

$$ (x_{1} \vee x_{2} \vee \neg x_{5}) \wedge (\neg x_{3} \vee x_{4} \vee \neg x_{6}) \wedge x_{5} \wedge x_{6} $$

$\endgroup$
  • 1
    $\begingroup$ An instance of 2SAT is already an instance of SAT! $\endgroup$ – David Richerby Nov 29 '14 at 21:44

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.