PNP
Question 1 
Consider two decision problems Q_{1}, Q_{2} such that Q_{1} reduces in polynomial time to 3SAT and 3 SAT reduces in polynomial time to Q_{2}. Then which one of following is consistent with the above statement?
Q_{1} is in NP, Q_{2} in NP hard
 
Q_{1} is in NP, Q_{2} is NP hard  
Both Q_{1} and Q_{2} are in NP
 
Both Q_{1} and Q_{2} are NP hard

Question 1 Explanation:
3SAT ⇒ NPC problem
Q_{1}≤p 3SAT≤p Q_{2} ≤p ≤p hence → Q1 is in NP
but Q_{2} is not given in NP
Hence Q_{2} is in NPHard.
Q_{1}≤p 3SAT≤p Q_{2} ≤p ≤p hence → Q1 is in NP
but Q_{2} is not given in NP
Hence Q_{2} is in NPHard.
Question 2 
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
Question 2 Explanation:
The most important open question in complexity theory is whether the P = NP, which asks whether polynomial time algorithms actually exist for NPcomplete and all NP problems (since a problem “C” is in NPcomplete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NPcomplete problem. Hence P=NP=NPComplete.
Question 3 
Assuming P ≠ NP, which of the following is TRUE?
NPcomplete = NP  
NPcomplete ∩ P = ∅  
NPhard = NP  
P = NPcomplete 
Question 3 Explanation:
Note: Out of syllabus.
The definition of NPcomplete is,
A decision problem p is NPcomplete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NPcomplete ∩ P = ∅ .
This is due to the fact that, if NPcomplete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NPcomplete also, then it means that P1 (NPcomplete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NPcomplete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
The definition of NPcomplete is,
A decision problem p is NPcomplete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NPcomplete ∩ P = ∅ .
This is due to the fact that, if NPcomplete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NPcomplete also, then it means that P1 (NPcomplete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NPcomplete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
Question 4 
Let π_{A} be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for π_{A}.
 
If π_{A} can be solved deterministically in polynomial time,then P = NP.  
If π_{A} is NPhard, then it is NPcomplete.  
π_{A} may be undecidable. 
Question 4 Explanation:
Note: Out of syllabus.
Question 5 
The subsetsum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
Q solves the subsetsum problem in polynomial time when the input is encoded in unary
 
Q solves the subsetsum problem in polynomial time when the input is encoded in binary
 
The subset sum problem belongs to the class NP  
The subset sum problem is NPhard

Question 5 Explanation:
Note: Out of syllabus.
Question 6 
For problems X and Y, Y is NPcomplete and X reduces to Y in polynomial time. Which of the following is TRUE?
If X can be solved in polynomial time, then so can Y  
X is NPcomplete  
X is NPhard  
X is in NP, but not necessarily NPcomplete

Question 6 Explanation:
Note: Out of syllabus.
Question 7 
Let S be an NPcomplete 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 polynomialtime reducible to R. Which one of the following statements is true?
R is NPcomplete
 
R is NPhard  
Q is NPcomplete
 
Q is NPhard

Question 7 Explanation:
NPHard if it can be solved in polynomial time then all NPComplete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.
Question 8 
Let SHAM_{3} be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM_{3} be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Both DHAM_{3} and SHAM_{3} are NPhard  
SHAM_{3} is NPhard, but DHAM_{3} is not
 
DHAM_{3} is NPhard, but SHAM_{3} is not  
Neither DHAM_{3} nor SHAM_{3} is NPhard

Question 8 Explanation:
Whether to finding a hamiltonian cycles exist (or) not is a NP Hard problem. So both DHAM_{3} and SHAM_{3} are NPhard.
Question 9 
Consider the following two problems on undirected graphs
α : Given G(V, E), does G have an independent set of size  V   4? β : Given G(V, E), does G have an independent set of size 5?Which one of the following is TRUE?
α is in P and β is NPcomplete
 
α is NPcomplete and β is in P
 
Both α and β are NPcomplete
 
Both α and β are in P

Question 9 Explanation:
Graph independent set decision problem is belongs to NPcomplete.
Question 10 
The problems 3SAT and 2SAT are
both in P  
both NP complete
 
NPcomplete and in P respectively
 
undecidable and NPcomplete respectively

Question 10 Explanation:
SAT → Boolean satisfiability problem & it is a decision problem.
2SAT and 3SAT is a NPcomplete.
2SAT and 3SAT is a NPcomplete.
Question 11 
Ram and Shyam have been asked to show that a certain problem Π is NPcomplete. Ram shows a polynomial time reduction from the 3SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3SAT. Which of the following can be inferred from these reductions?
Π is NPhard but not NPcomplete
 
Π is in NP, but is not NPcomplete
 
Π is NPcomplete
 
Π is neither NPhard, nor in NP

Question 11 Explanation:
Note: As per Present syllabus, it is not required.
There are 11 questions to complete.