## P-NP

 Question 1
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
 A Q1 is in NP, Q2 in NP hard B Q1 is in NP, Q2 is NP hard C Both Q1 and Q2 are in NP D Both Q1 and Q2 are NP hard
Theory-of-Computation       P-NP       GATE 2015 -(Set-2)
Question 1 Explanation:
3-SAT ⇒ NPC problem
Q1≤p 3-SAT≤p Q2 ≤p ≤p hence → Q1 is in NP
but Q2 is not given in NP
Hence Q2 is in NP-Hard.
 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)?
 A B C D
Algorithms       P-NP       GATE 2014(Set-01)
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 NP-complete and all NP problems (since a problem “C” is in NP-complete, 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 NP-complete problem. Hence P=NP=NP-Complete.
 Question 3
Assuming P ≠ NP, which of the following is TRUE?
 A NP-complete = NP B NP-complete ∩ P = ∅ C NP-hard = NP D P = NP-complete
Algorithms       P-NP       Gate 2012
Question 3 Explanation:
Note: Out of syllabus.
The definition of NP-complete is,
A decision problem p is NP-complete 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 NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete 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 NP-complete 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?
 A There is no polynomial time algorithm for πA. B If πA can be solved deterministically in polynomial time,then P = NP. C If πA is NP-hard, then it is NP-complete. D πA may be undecidable.
Algorithms        P-NP       2009
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.
NP-Complete: In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes. In this context, NP stands for "nondeterministic polynomial time". The set of NP-complete problems is often denoted by NP-C or NPC.
Standard Definition:
A decision problem C is NP-complete 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 NP-hard, 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 Turing-equivalent 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
 A Q solves the subset-sum problem in polynomial time when the input is encoded in unary B Q solves the subset-sum problem in polynomial time when the input is encoded in binary C The subset sum problem belongs to the class NP D The subset sum problem is NP-hard
Algorithms       P-NP       Gate-2008
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.
 Question 6
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
 A If X can be solved in polynomial time, then so can Y B X is NP-complete C X is NP-hard D X is in NP, but not necessarily NP-complete
Algorithms        P-NP       Gate 2008-IT
Question 6 Explanation:
We can't be able to say X is NP-hard unless and untill X is also NP-complete (or) below it.
That means to be it belongs to NP class, in that class it may be NP-complete. So, X is NP for sure but may be NP-complete.
 Question 7
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?
 A R is NP-complete B R is NP-hard C Q is NP-complete D Q is NP-hard
Algorithms        P-NP       Gate-2006
Question 7 Explanation:
NP-Hard- if it can be solved in polynomial time then all NP-Complete 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 SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
 A Both DHAM3 and SHAM3 are NP-hard B SHAM3 is NP-hard, but DHAM3 is not C DHAM3 is NP-hard, but SHAM3 is not D Neither DHAM3 nor SHAM3 is NP-hard
Algorithms        P-NP       Gate-2006
Question 8 Explanation:
Whether to finding a hamiltonian cycles exist (or) not is a NP Hard problem. So both DHAM3 and SHAM3 are NP-hard.
 Question 9

 A α is in P and β is NP-complete B α is NP-complete and β is in P C Both α and β are NP-complete D Both α and β are in P
Algorithms        P-NP       Gate-2005
Question 9 Explanation:
Graph independent set decision problem is belongs to NP-complete.
 Question 10
The problems 3-SAT and 2-SAT are
 A both in P B both NP complete C NP-complete and in P respectively D undecidable and NP-complete respectively
Algorithms        P-NP       Gate-2004
Question 10 Explanation:
SAT → Boolean satisfiability problem & it is a decision problem.
2-SAT and 3-SAT is a NP-complete.
 Question 11
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions?
 A Π is NP-hard but not NP-complete B Π is in NP, but is not NP-complete C Π is NP-complete D Π is neither NP-hard, nor in NP
Algorithms        P-NP       Gate-2003
Question 11 Explanation:
Note: As per Present syllabus, it is not required.
There are 11 questions to complete.