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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Of course. Just take B=A, since every P problem is in NP.
-
$\begingroup$ Or take $B$ to be any NP-complete problem, or any problem in P. $\endgroup$ Nov 29, 2014 at 18:15
$\begingroup$
$\endgroup$
1
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} $$
-
1$\begingroup$ An instance of 2SAT is already an instance of SAT! $\endgroup$ Nov 29, 2014 at 21:44