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.
These problems are the hardest problems in the NP set.
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.
What is Reduction?
Let L1 and L2 denote two decision problems. Suppose algorithm A2 solves L2.
The main purpose is to find a transformation from L1 to L2 such that Algorithm A2 can be a part of A1 to solve L1.
How to Prove that a given problem is NP-Complete?
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.
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
- 1, 2 and 3
- 1 and 2 only
- 2 and 3 only
- 1 and 3 only
- 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?
- R is NP-complete
- R is NP-hard
- Q is NP-complete
- Q is NP-hard
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 !!