P-NP
Question 1 |
Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let Lc be the complement of L over ∑*. Show that Lc is also in NP.
Theory Explanation. |
Question 2 |
Assuming P ≠ NP, which of the following is TRUE?
NP-complete = NP | |
NP-complete ∩ P = ∅ | |
NP-hard = NP | |
P = NP-complete |
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 3 |
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?
Π is NP-hard but not NP-complete
| |
Π is in NP, but is not NP-complete
| |
Π is NP-complete | |
Π is neither NP-hard, nor in NP
|
Question 4 |
A problem in NP is NP-complete if
It can be reduced to the 3-SAT problem in polynomial time | |
The 3-SAT problem can be reduced to it in polynomial time | |
It can be reduced to any other problem in NP in polynomial time | |
Some problem in NP can be reduced to it in polynomial time
|
Question 5 |
For problems X and Y, Y is NP-complete 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 NP-complete | |
X is NP-hard | |
X is in NP, but not necessarily NP-complete |
Question 6 |
The problems 3-SAT and 2-SAT are
both in P | |
both NP complete | |
NP-complete and in P respectively | |
undecidable and NP-complete respectively |
2-SAT and 3-SAT is a NP-complete.
Question 7 |
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?
Q1 is in NP, Q2 in NP hard | |
Q1 is in NP, Q2 is NP hard | |
Both Q1 and Q2 are in NP | |
Both Q1 and Q2 are NP hard |
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 8 |
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)?
 | |
 | |
 | |
 |