CS6515 Practice Test Questions with Verified
Correct Answers
Definition of NP
- class of problems that are considered to be search problems
- nondeterministic polynomial time
Definition of P
subset of NP problems that can generate a solution in polynomial time.
What it means to be NP?
Given an input I and a solution S, verify that S is a valid solution for input I in polynomial
time.
What is a search problem?
Form: Find a solution S for I if one exists. Output NO if I has no solution.
Requirement: If given an instance I and a solution S, we can verify S is a solution to I in
polynomial time.
What it means to be P?
You can verify and generate solutions in polynomial time.
P = NP?
- P is a subset of NP.
- P = NP is not true.
- If a problem is in NP but cannot be proven to be in P, then it is not known to be in P.
NP Hard
,- at least as hard as the hardest NP Problems
- can be in NP, but also be outside of NP
- if outside of NP, then its a problem we don't know how to verify a solution for in
polynomial time.
NP Complete
- subset of NP problems and NP Hard problems
- hardest NP problems
- prove that it is in NP and that it is NP Hard
- all NP complete problems can be reduced to each other
- all search problems can reduce to NP complete problems. This means P, NP, and NP
Complete can reduce to NP Complete.
P, NP, NP Complete, NP Hard space
Complexity is lowest for P and increases as you go to NP -> NP Complete -> NP Hard
What problems can be reduced to each other?
- ALL NP complete problems (which are in the class NP) are reducible to NP Hard problems
- Not all NP Hard problems can be reduced to each other in all cases
What does a reduction from P to NP mean?
if A∈P, then A is automatically reducible to any NP problem, because:
- The reduction algorithm is allowed to run in polynomial time.
- Solving problem A is already polynomial-time.
What does a reduction from NP to P mean?
, A->B, where A in NP and B in P
- If you ALREADY have a poly-time solver for B, then you could solve A using it. But this
does NOT prove A is easy. It just rewrites A.
What does a reduction from NP to NP mean?
You can translate one NP problem into another NP problem.
What does a reduction from NP to NP Complete mean?
If you had a solver for B, you could solve A. Does NOT prove anything about A's difficulty.
What does a reduction from NP Complete to NP mean?
B -> A
- A is at least as hard as B (B ≤p A)
- Since every NP problem reduces to B, and B reduces to A, every NP problem reduces to A
Therefore A is NP-hard, and because A is also in NP, A is NP-complete
What does a reduction from NP Complete to NP Complete mean?
A-> B, where both A and B are in NP Complete.
Shows A is at least as hard as B; both are top-level problems.
What does a reduction from NP-Hard to NP-Complete mean?
Membership in NP + NP-hardness means A is NPC.
What does a reduction from NP-Complete to P mean?
This would mean a P-time solver solves NPC Complete. Implies NP Complete is a subset of
P and would collapse the NP Completeness theory.
How to prove a unknown problem is NP Complete?
Correct Answers
Definition of NP
- class of problems that are considered to be search problems
- nondeterministic polynomial time
Definition of P
subset of NP problems that can generate a solution in polynomial time.
What it means to be NP?
Given an input I and a solution S, verify that S is a valid solution for input I in polynomial
time.
What is a search problem?
Form: Find a solution S for I if one exists. Output NO if I has no solution.
Requirement: If given an instance I and a solution S, we can verify S is a solution to I in
polynomial time.
What it means to be P?
You can verify and generate solutions in polynomial time.
P = NP?
- P is a subset of NP.
- P = NP is not true.
- If a problem is in NP but cannot be proven to be in P, then it is not known to be in P.
NP Hard
,- at least as hard as the hardest NP Problems
- can be in NP, but also be outside of NP
- if outside of NP, then its a problem we don't know how to verify a solution for in
polynomial time.
NP Complete
- subset of NP problems and NP Hard problems
- hardest NP problems
- prove that it is in NP and that it is NP Hard
- all NP complete problems can be reduced to each other
- all search problems can reduce to NP complete problems. This means P, NP, and NP
Complete can reduce to NP Complete.
P, NP, NP Complete, NP Hard space
Complexity is lowest for P and increases as you go to NP -> NP Complete -> NP Hard
What problems can be reduced to each other?
- ALL NP complete problems (which are in the class NP) are reducible to NP Hard problems
- Not all NP Hard problems can be reduced to each other in all cases
What does a reduction from P to NP mean?
if A∈P, then A is automatically reducible to any NP problem, because:
- The reduction algorithm is allowed to run in polynomial time.
- Solving problem A is already polynomial-time.
What does a reduction from NP to P mean?
, A->B, where A in NP and B in P
- If you ALREADY have a poly-time solver for B, then you could solve A using it. But this
does NOT prove A is easy. It just rewrites A.
What does a reduction from NP to NP mean?
You can translate one NP problem into another NP problem.
What does a reduction from NP to NP Complete mean?
If you had a solver for B, you could solve A. Does NOT prove anything about A's difficulty.
What does a reduction from NP Complete to NP mean?
B -> A
- A is at least as hard as B (B ≤p A)
- Since every NP problem reduces to B, and B reduces to A, every NP problem reduces to A
Therefore A is NP-hard, and because A is also in NP, A is NP-complete
What does a reduction from NP Complete to NP Complete mean?
A-> B, where both A and B are in NP Complete.
Shows A is at least as hard as B; both are top-level problems.
What does a reduction from NP-Hard to NP-Complete mean?
Membership in NP + NP-hardness means A is NPC.
What does a reduction from NP-Complete to P mean?
This would mean a P-time solver solves NPC Complete. Implies NP Complete is a subset of
P and would collapse the NP Completeness theory.
How to prove a unknown problem is NP Complete?
