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:
As per the above question, only option C is correct because it is an standard definition of NP Complete. Rest of the options are violating their definition and properties.
NPComplete: In computational complexity theory, an NPcomplete decision problem is one belonging to both the NP and the NPhard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NPcomplete problems is often denoted by NPC or NPC.
Standard Definition:
A decision problem C is NPcomplete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NPhard, whether or not it satisfies condition 1. A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turingequivalent abstract machine) for C, we could solve all problems in NP in polynomial time.
Note: As per Present GATE syllabus NP Complete and NP Hard not required
NPComplete: In computational complexity theory, an NPcomplete decision problem is one belonging to both the NP and the NPhard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NPcomplete problems is often denoted by NPC or NPC.
Standard Definition:
A decision problem C is NPcomplete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NPhard, whether or not it satisfies condition 1. A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turingequivalent abstract machine) for C, we could solve all problems in NP in polynomial time.
Note: As per Present GATE syllabus NP Complete and NP Hard not required
Question 5 
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:
Suppose the input is encoded in binary format. If W is an exponential in terms of the input length of W and O(nW) also becomes exponential in terms of the input lengths. Q is not a polynomial time algorithm.
Note: As per Present GATE syllabus , the above concept is not required.
Note: As per Present GATE syllabus , the above concept is not required.
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:
We can't be able to say X is NPhard unless and untill X is also NPcomplete (or) below it.
That means to be it belongs to NP class, in that class it may be NPcomplete. So, X is NP for sure but may be NPcomplete.
That means to be it belongs to NP class, in that class it may be NPcomplete. So, X is NP for sure but may be NPcomplete.
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 
α 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.