There are certain computational problems which cannot be solved by algorithms even with unlimited time complexity.

NP-Complete problems are another set of problems which fall under this category.

In order to assist you in your GATE preparation , We provide daily Free Quiz (chapter wise) , study tips , preparation Tips for GATE 2017preparation .

You can subscribe and get **daily** **FREE Quiz (Chapter Wise) , study tutorials and tips delivered on your personal email id to crack the upcoming GATE Exam**.

**Classification of Problems**

- P :These are a set of problems which can be solved in polynomial time by a deterministic Turing machine.

- NP : These are a set of decision problems which can be solved in Polynomial time by a Non-Deterministic Turing machine.

NP is a superset of P.

- NP-Complete

These problems are the hardest problems in the NP set.

**must read : 6 Month Study Plan/TimeTable To Crack GATE (CS) 2017 By Experts **

A decision problem C is NP-Complete if

- C is in NP
- Every problem in NP is reducible to C in polynomial time

From the figure, it is clear that NP-Complete is a subset of NP-Hard set.

**must read : Most Important Topics For GATE-2017 (CSE) || guaranteed Results**

**What is Reduction?**

Let L_{1} and L_{2} denote two decision problems. Suppose algorithm A_{2} solves L_{2}.

The main purpose is to find a transformation from L_{1} to L_{2 } such that Algorithm A_{2} can be a part of A_{1 }to solve L_{1}.

**How to Prove that a given problem is NP-Complete?**

**Tips: **

The technique is to take a known NP-complete problem and reduce it to L.

Then, we can prove that L is NP-Complete by transitivity of reduction if polynomial time reduction is possible.

**Solved Examples**

**Q1. Which of the following statements are TRUE?**

- The problem of identifying whether a cycle exists in an undirected graph is in P
- The problem of identifying whether a cycle exists in an undirected graph is in NP

- If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A

**Options**

- 1, 2 and 3
- 1 and 2 only
- 2 and 3 only
- 1 and 3 only

Answer: (A)

**Solution**:

- In order to find whether there is a cycle in an undirected graph, we can use either BFS or DFS. The time complexity of a DFS based implementation is O(V + E) which is a polynomial
- A problem in P domain is definitely NP.

- This statement is also true.

**important article : Just 4 Tips ,Problem on Heap Sort Solved || Exam Preparation Simplified**

**Q2. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?**

**Options**

- R is NP-complete
- R is NP-hard
- Q is NP-complete
- Q is NP-hard

**Answer**: (B)

**Solution:**

**Statement **(A) is incorrect since R is not in NP.

Statement (B) is correct since S is polynomial time reducible to R

Statement (C) is incorrect since Q is not in NP

Statement (D) is incorrect since there is no NP-Complete problem which is polynomial time

Turing-reducible to Q.

## Enroll in Mentor Program and Avail your Personalized Mentor for GATE 2017 Preparation and Doubts Clarification!

What aspirants need is the right approach along with concrete strategies to reach their goals. **GATE GUARANTEE PACK has been the choice of successful GATE toppers all over India.**

It is the perfect online tool to check your level of preparedness among st students preparing all over the country where you study under guidance of mentors.

** Best Wishes !!**