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 |
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 3 |
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 4 |
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 5 |
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 6 |
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 7 |
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 8 |
The subset-sum 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 subset-sum problem in polynomial time when the input is encoded in unary
| |
Q solves the subset-sum 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 NP-hard |