np complete problems for GATE

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 .

Expert Tips and Tutorials to crack GATE 2018 Exam.

Subscribe Here     

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

  1. P :These are a set of problems which can be solved in polynomial time by a deterministic Turing machine.
  1. 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.

  1. NP-Complete

These problems are the hardest problems in the NP set.

 

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

 

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 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?

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.

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

Solved Examples

Q1. Which of the following statements are TRUE?

  1. The problem of identifying whether a cycle exists in an undirected graph is in P
  2. 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. 1, 2 and 3
  2. 1 and 2 only
  3. 2 and 3 only
  4. 1 and 3 only

Answer: (A)

Solution

  1. 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
  2. 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

  1. R is NP-complete
  2. R is NP-hard
  3. Q is NP-complete
  4. 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.

Free All India Test Equipped with Artificial Intelligence

Start Test  

 Best Wishes !!

Search on PrepLadder