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.
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)?
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.
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.
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
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
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
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