In this post we will learn how to find if any problem is P, NP, NP-complete, NP-hard or undecidable. We will follow the below two theorems to understand which type of a problem is.
Theorem - 1: When a given Hard Problem (NPC, NPH and Undecidable Problems) is reduced to an unknown problem in polynomial time, then unknown problem also becomes Hard.
Case - 1 When NPC(NP-Complete) problem is reduced to unknown problem, unknown problem becomes NPH(NP-Hard).
Case - 2 When NPH(NP-Hard) problem is reduced to unknown problem, unknown problem becomes NPH(NP-Hard).
Case - 3 When undecidable problem is reduced to unknown problem, unknown problem becomes also becomes undecidable. Remember that Hard problems needs to be converted for this theorem but not the other way.
Theorem - 2: When an unknown problem is reduced to an Easy problem(P or NP) in polynomial time, then unknown problem also becomes easy.
Case - 1 When an unknown problem is reduced to a P type problem, unknown problem also becomes P.
Case - 2 When an unknown problem is reduced to a NP type problem, unknown problem also becomes NP. Remember that unknown problems needs to be converted for this theorem to work but not the other way.
QUESTION:
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
a) If X can be solved in polynomial time, then so can Y.
b) X is NP Complete
c) X is NP Hard
d) X is NP but not necessarily NP complete.
ANSWER:
In the given question, X which is unknown problem is reduced to NPC problem in polynomial time so Theorem - 1 will not work. But all NPC problems are also NP, so we can say that X is getting reduced to a known NP problem so that Theorem - 2 is applicable and X is also NP. In order to make it NPC, we have to prove it NPH first which is not the case as Y is not getting reduced to X. So X is NP but not necessarily NP complete .
Advertisements
nice
ReplyDelete