P, NP, NP-Completeness, NP-Hardness, Undecidability Flashcards
Are all P problems NP?
Yes
What is NP?
Problems for which solutions can be verified in polynomial time
If a problem is in NP, and can’t be proven to be P, what do we say about it?
It’s not known to be P.
What is P?
NP problems that have polynomial time solutions.
What is polynomial time?
Complexity that varies entirely as a function of the input size.
What is the significance of P=NP?
It would mean all algorithms with polynomial time verification (NP) can also be solved in polynomial time (P), which would be huge.
What is NP-Hard?
Problems with no known polynomial solutions.
How are the difficulties of NP-Hard and NP problems related?
An NP-Hard problem is at least as hard as the hardest NP problems.
How are NP-Hard and NP related?
NP-Hard problems can be in NP, but also can be outside NP. If outside NP, we can’t verify it in polynomial time. The hardest NP problems are also NP-Hard.
How do you prove that a problem is NP-Complete?
- Prove it’s in NP by showing that it has a polynomial time verification
- Prove it’s NP-Hard by reducing a known-NP-Complete problem to it in polynomial time (inputs and outputs)
What must you cover when proving that an unknown problem is NP-Complete by reducing a known-NP-Complete problem to it?
- Inputs to the known-NPC can be converted to the unknown problem in polynomial time
- Solution to the unknown problem can be converted back to the known-NPC in polynomial time
- If there is a solution to the unknown problem, there is a solution to the known-NPC
- If there is no solution to the unknown problem, there is no solution to the known-NPC
How do you prove that a problem is NP-Hard?
Prove that a known NP-Hard or NP-Complete problem can be reduced to it. (Does not require proof of being in NP)
How are the difficulty of NP-Complete and NP related?
NP-Complete problems are the hardest NP problems.
What is Undecidable?
No algorithm can solve the problem for every input (but maybe some), even with unlimited time and space.
What is the Halting Problem?
An Undecidable problem built on a contradiction which proves that Undecidable problems exist. It is not possible to solve the Halting Problem.
What is the idea behind the Halting Problem?
Suppose we have an algorithm Terminator(P, I) that solves the Halting Problem for every input. We recursively call it in the Halting Problem to show that it can’t terminate: Harmful(J): (1) If Terminator(J, J): Goto (1) Else Return()
If a problem is P, is it NP, NP-Hard, NP-Complete, Undecidable?
NP
If a problem is NP, is it P, NP-Hard, NP-Complete, Undecidable?
None necessarily
If a problem is NP-Hard, is it P, NP, NP-Complete, Undecidable?
None necessarily
If a problem is NP-Complete, is it P, NP, NP-Hard, Undecidable?
NP, NP-Hard
If a problem is Undecidable, is it P, NP, NP-Hard, NP-Complete?
None
What are the known NP-Complete problems?
SAT, 3SAT, Clique, Independent Set, Vertex Cover, Subset Sum, Knapsack Search, Integer Linear Programming
What is the SAT problem?
SAT(C)
Complexity: NP-Complete
Input: C is a CNF with any number of variables (n variables) and clauses (m clauses)
Output: assignment of each variable such that the CNF is true
What is the 3SAT problem?
3SAT(C)
Complexity: NP-Complete
Input: C is a CNF whose clauses have at most 3 literals
Output: assignment of each variable such that the CNF is true
What is the Clique problem?
Clique(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph, k is the target size of the clique
Output: A clique with >= k vertices
Background: A clique is a subset of vertices in a graph that are fully connected
What is the Independent Set problem?
IndependentSet(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph, k is the target size of the independent set
Output: An independent set with >= k vertices
Background: An independent set is a subset of vertices in a graph that have no edge between any pair of them
What is the Vertex Cover problem?
VertexCover(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph. k is the target size of the vertex cover
Output: A vertex cover with >= k vertices
Background: A vertex cover is a subset of vertices in a graph such that all edges in the graph have at least one vertex in the subset
What is the Subset Sum problem?
SubsetSum(A, t)
Complexity: NP-Complete
Input: A is a list of integers. t is a target sum
Output: A subset of integers from A that add up to t
Background: A DP algorithm exists which solves this problem in O(nt) time
What is the Knapsack Search problem?
KnapsackSearch(W, V, B, g)
Complexity: NP-Complete
Input: W is the weight of each item, V is the value of each item, B is the capacity of the knapsack, g is the target value
Output: A subset of items with >= g value and <= B weight
What is the easiest problem to reduce to 3SAT?
SAT
What is the easiest problem to reduce to Independent Set?
3SAT
What is the easiest problem to reduce to Vertex Cover?
Independent Set
What is the easiest problem to reduce to Clique?
Independent Set
What is the easiest problem to reduce to Integer Linear Programming?
3SAT
What is the easiest problem to reduce to Subset Sum?
3SAT
What is the easiest problem to reduce to Knapsack Search?
Subset Sum
How do you prove 3SAT is NP-Complete?
Reduce SAT to 3SAT by introducing new variables to toggle each clause on or off. Create k-3 new variables as Y1, Y2, Y3, etc.
C’ = (X1 v X2 v Y1) ^ (!Y1 v X3 v Y2) … (!Y{k-4} v X{k-2} v Y{k-3}) ^ (!Y{k-3} v X{k-1} v Xk)
How do you prove Independent Set is NP-Complete?
Reduce 3SAT to Independent Set by encoding the expression as a graph. Literals for clauses are fully connected, then each X must be connected to each !X and vice versa. g = m because satisfying m clauses takes g independent vertices/variables.
How do you prove Clique is NP-Complete?
Reduce Independent Set to Clique by taking the complement of the Independent Set graph and running Clique on it.
How do you prove Vertex Cover is NP-Complete?
Reduce Independent Set to Vertex Cover, but with b=n-g.
How do you prove Subset Sum is NP-Complete?
Verification takes O(n log t) which is polynomial (log t is a function of input size because it takes that many bits). Reduce 3SAT to Subset Sum by encoding the satisfiability into t and combining variables and clauses. Make a table with 2n+2m+1 rows and n+m columns, fill in which ones are needed.
How do you prove that Knapsack Search is NP-Complete?
TODO
How do you prove Integer Linear Programming is NP-Complete?
Reduce Max-SAT to ILP by encoding each literal as true or false assignments, and clauses as summations that must sum up to new z variables. We try to maximize the sum of the z variables.
How do you produce a polynomial time approximation of an NP-Hard problem?
- Reduce to ILP
- Relax to LP
- Solve the LP (Simplex or other polynomial algorithm)
- Round the solution (randomized or other technique)
