Decision problem which belongs to P reduced to a decision problem which belongs to NP?

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?

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

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

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

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