P, NP, NP-Completeness, NP-Hardness, Undecidability

Question 1

Are all P problems NP?

Answer 1

Yes

Question 2

What is NP?

Answer 2

Problems for which solutions can be verified in polynomial time

Question 3

If a problem is in NP, and can’t be proven to be P, what do we say about it?

Answer 3

It’s not known to be P.

Question 4

What is P?

Answer 4

NP problems that have polynomial time solutions.

Question 5

What is polynomial time?

Answer 5

Complexity that varies entirely as a function of the input size.

Question 6

What is the significance of P=NP?

Answer 6

It would mean all algorithms with polynomial time verification (NP) can also be solved in polynomial time (P), which would be huge.

Question 7

What is NP-Hard?

Answer 7

Problems with no known polynomial solutions.

Question 8

How are the difficulties of NP-Hard and NP problems related?

Answer 8

An NP-Hard problem is at least as hard as the hardest NP problems.

Question 9

How are NP-Hard and NP related?

Answer 9

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.

Question 10

How do you prove that a problem is NP-Complete?

Answer 10

1. Prove it’s in NP by showing that it has a polynomial time verification
2. Prove it’s NP-Hard by reducing a known-NP-Complete problem to it in polynomial time (inputs and outputs)

Question 11

What must you cover when proving that an unknown problem is NP-Complete by reducing a known-NP-Complete problem to it?

Answer 11

1. Inputs to the known-NPC can be converted to the unknown problem in polynomial time
2. Solution to the unknown problem can be converted back to the known-NPC in polynomial time
3. If there is a solution to the unknown problem, there is a solution to the known-NPC
4. If there is no solution to the unknown problem, there is no solution to the known-NPC

Question 12

How do you prove that a problem is NP-Hard?

Answer 12

Prove that a known NP-Hard or NP-Complete problem can be reduced to it. (Does not require proof of being in NP)

Question 13

How are the difficulty of NP-Complete and NP related?

Answer 13

NP-Complete problems are the hardest NP problems.

Question 14

What is Undecidable?

Answer 14

No algorithm can solve the problem for every input (but maybe some), even with unlimited time and space.

Question 15

What is the Halting Problem?

Answer 15

An Undecidable problem built on a contradiction which proves that Undecidable problems exist. It is not possible to solve the Halting Problem.

Question 16

What is the idea behind the Halting Problem?

Answer 16

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()

Question 17

If a problem is P, is it NP, NP-Hard, NP-Complete, Undecidable?

Answer 17

NP

Question 18

If a problem is NP, is it P, NP-Hard, NP-Complete, Undecidable?

Answer 18

None necessarily

Question 19

If a problem is NP-Hard, is it P, NP, NP-Complete, Undecidable?

Answer 19

None necessarily

Question 20

If a problem is NP-Complete, is it P, NP, NP-Hard, Undecidable?

Answer 20

NP, NP-Hard

Question 21

If a problem is Undecidable, is it P, NP, NP-Hard, NP-Complete?

Answer 21

None

Question 22

What are the known NP-Complete problems?

Answer 22

SAT, 3SAT, Clique, Independent Set, Vertex Cover, Subset Sum, Knapsack Search, Integer Linear Programming

Question 23

What is the SAT problem?

Answer 23

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

Question 24

What is the 3SAT problem?

Answer 24

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

Question 25

What is the Clique problem?

Answer 25

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

Question 26

What is the Independent Set problem?

Answer 26

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

Question 27

What is the Vertex Cover problem?

Answer 27

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

Question 28

What is the Subset Sum problem?

Answer 28

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

Question 29

What is the Knapsack Search problem?

Answer 29

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

Question 30

What is the easiest problem to reduce to 3SAT?

Answer 30

SAT

Question 31

What is the easiest problem to reduce to Independent Set?

Answer 31

3SAT

Question 32

What is the easiest problem to reduce to Vertex Cover?

Answer 32

Independent Set

Question 33

What is the easiest problem to reduce to Clique?

Answer 33

Independent Set

Question 34

What is the easiest problem to reduce to Integer Linear Programming?

Answer 34

3SAT

Question 35

What is the easiest problem to reduce to Subset Sum?

Answer 35

3SAT

Question 36

What is the easiest problem to reduce to Knapsack Search?

Answer 36

Subset Sum

Question 37

How do you prove 3SAT is NP-Complete?

Answer 37

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)

Question 38

How do you prove Independent Set is NP-Complete?

Answer 38

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.

Question 39

How do you prove Clique is NP-Complete?

Answer 39

Reduce Independent Set to Clique by taking the complement of the Independent Set graph and running Clique on it.

Question 40

How do you prove Vertex Cover is NP-Complete?

Answer 40

Reduce Independent Set to Vertex Cover, but with b=n-g.

Question 41

How do you prove Subset Sum is NP-Complete?

Answer 41

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.

Question 42

How do you prove that Knapsack Search is NP-Complete?

Answer 42

TODO

Question 43

How do you prove Integer Linear Programming is NP-Complete?

Answer 43

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.

Question 44

How do you produce a polynomial time approximation of an NP-Hard problem?

Answer 44

1. Reduce to ILP 2. Relax to LP 3. Solve the LP (Simplex or other polynomial algorithm) 4. Round the solution (randomized or other technique)