## NP-Complete

 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(V2)
Here, for complete graph E<= V2. 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.