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?
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 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 3 |
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 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 NP-hard, then it is NP-complete. | |
πA may be undecidable. |
Question 5 |
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 |
Question 6 |
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?
R is NP-complete | |
R is NP-hard | |
Q is NP-complete | |
Q is NP-hard |
Question 7 |
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?
Both DHAM3 and SHAM3 are NP-hard | |
SHAM3 is NP-hard, but DHAM3 is not | |
DHAM3 is NP-hard, but SHAM3 is not | |
Neither DHAM3 nor SHAM3 is NP-hard |
Question 8 |
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 NP-complete | |
α is NP-complete and β is in P | |
Both α and β are NP-complete | |
Both α and β are in P
|