[Solved]: Decision problem which belongs to P reduced to a decision problem which belongs to NP?

Problem Detail: 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?

Asked By : user3603634

Answered By : Alexey Romanov

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33624 Ask a Question Download Related Notes/Documents