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