topic – RBR

NP-Complete

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Consider the decision problem 2CNFSAT defined as follows:

The decision problem 2CNFSAT is

A	NP-Complete.
B	solvable in polynomial time by reduction to directed graph reachability.
C	solvable in constant time since any input instance is satisfiable.
D	NP-hard, but not NP-complete.

Theory-of-Computation NP-Complete Gate 2014 Set -03

Question 1 Explanation:

Note: Out of Syllabus.

Question 2

Which of the following statements are TRUE?

1. The problem of determining whether there exists
   a cycle in an undirected graph is in P.
2. The problem of determining whether there exists
   a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a 
   non-deterministic polynomial time algorithm to solve A.

A	1, 2 and 3
B	1 and 2 only
C	2 and 3 only
D	1 and 3 only

Theory-of-Computation NP-Complete Gate 2013

Question 2 Explanation:

Note: Out of syllabus.
1. Detecting cycle in a graph using DFS takes O(V+E)=O(V²)
Here, for complete graph E<= V². So, It runs in polynomial time.
2. Every P-problem is NP because P subset of NP (P ⊂ NP)
3. NP – complete ∈ NP.
Hence, NP-complete can be solved in non-deterministic polynomial time.

Question 3

Which of the following problems is not NP-hard?

A	Hamiltonian circuit problem
B	The 0/1 Knapsack problem
C	Finding bi-connected components of a graph
D	The graph colouring problem

Theory-of-Computation NP-Complete Gate-1992

Question 3 Explanation:

Note: Out of syllabus.

There are 3 questions to complete.