NP-Complete

Question 1

Define a search problem

Answer 1

A search problem is specified by a search algorithm C that takes two inputs, an instance I and a proposed solution S, and runs in time polynomial | I |. We say S is a solution if and only if C(I,S) = True

Note: we must be able to find S quickly (in poly-time with respect to I).

Question 2

Is SAT a search problem? Why or why not?

Answer 2

Yes SAT is a search problem. We can take a proposed solution of variable-assignments and verify that every clause in I is satisfied. This can be done in polynomial time.

Question 3

What is the input and output to the SAT problem? Is it NP-Complete?

Answer 3

**Input**:
The input is m or-clauses with n boolean variables. The clauses are in conjunctive normal form:
(x1 or ~x2) and (x3 or x2 or x1) and (x5 …)

**Output**:

• Assignments for all variables if the statement can be satisfied
• “No” if not.

NP-Complete? YES! (note if 2SAT, it’s in P)

Question 4

What is the input to the Independent Set problem? Is it NP-Complete?

Answer 4

**Input**: G=(V,E), k
An undirected, unweighted graph G=(V,E). k is the target size of the IS.

**Output**:

• IS with >= k vertices. An independent is a set such that no two vertices in the set share an edge.
• “No” if not set exists.

NP-Complete? YES!

Question 5

What is the input and output to the Vertex Cover problem? Is it NP-Complete?

Answer 5

**Input**: G=(V,E), b
An undirected, unweighted graph G=(V,E). b is the budget size of the vertex cover.

**Output**:

• Vertex cover with <= b vertices
• “No” if no vertex cover exists with <= b vertices

NP-Complete? YES!

Question 6

What is the input and output to the Subset Sum problem? Is it NP-Complete?

Answer 6

**Input**: A, t
A is an array of integers. t is the target integer sum.

**Output**:

• An array of integers which is a subset of A, and sums to t.
• “No” if no such array of ints exists

NP-Complete? YES!

Question 7

What is the input and output to the Knapsack Search problem? Is it NP-Complete?

Answer 7

**Input**: W, V, B, g
W is the array of weights. V is the array of values. B is the capacity of the knapsack. g is the target value.

**Output**:

• An array of items of total weight <= B and total value >= g.
• “No” if no such collection of items exists.

NP-Complete? YES!

Question 8

What is the input and output to the clique problem? Is it NP-Complete?

Answer 8

**Input**: G, k
G is an undirected, unweighted graph. k is the target size of the clique.

**Output**:

• A set of at least k vertices that are in a clique. This means each pair of vertices in the clique has an edge between them (directly connected).
• “No” if no such clique exists

NP-Complete? YES!

Question 9

List all reductions that we can make from Indepdent Set (that we reviewed in lectures)

Answer 9

Question 10

List all reductions that we can make from SAT

Answer 10

Question 11

When writting an NP-Complete Proof by reducing A => B, you have to show that A <=> B. What logical statements can you use to do this?

Answer 11

Pick one of the 4 combos below to prove this

A => B AND B => A

A => B AND NO A => NO B

B => A AND NO B => NO A

NO A => NO B AND NO B => NO A

Important:

A => B, NO B => NO A are contrapositives; they have the same logical value. If you were to use this combo then you would have proven the same direction twice.

Question 12

True or False? Knapsack is in P?

Answer 12

False (there is no known algorithm that runs in polynomial time). The dynamic programming algorithm we discussed in class runs in O(nB), which is not polynomial with respect to the inputs.

Note: If you add a goal, you have the “Knapsack-Search” problem, and this is in NP. We can check that the sum of weights are at most B and that the sum of values is at least the goal.

Question 13

True or False? MST is in NP? MST is in P?

Answer 13

True and True. We know of two polynomial time algorithm to find an MST: Prims and Kruskals. We can use these algorithms to verify that a given solution is a minimum spanning tree by 1) running BFS or DFS to make sure it’s a tree and 2) running Prims or Kruskals to ensure it’s a minimum spanning tree.

Question 14

What does NP stand for?

Answer 14

Nondeterministic polynomial time. This means problems that can be solved in poly-time on a nondeterministic machine. A nondeterministic machine is one in which we can guess at each step.

Question 15

What are NP-complete problems?

Answer 15

They are the hardest problems in the class NP. If P != NP, then all NP-complete problems are not in P. If an algorithm is found to solve an NP-complete problem in polynomial time, this means P=NP.

Ex) If we can solve SAT in poly-time then we can solve every problem in NP in poly-time. If P != NP, SAT is not in P.

Question 16

True or false? Knapsack (without a goal) is in NP.

Answer 16

False (Knapsack is not known to be in NP). This is because we don’t know of an algorithm that can run in polynomial time to verify that the total value of the objects in a solution is the maximum.

Question 17

How long does it take to verify a solution, S, to a SAT formula f?

Answer 17

In the worst case, this takes O(mn) time, since each of the m clauses needs to be checked once, and each clause has (at most) 2n literals.

Question 18

True or false? It is possible to solve some NP problems in polynomial time?

Answer 18

True - these problems are both in NP and in P.

Question 19

If you have a graph G=(V,E), and V_is are vertices that form an indepdent set, what can be said about the vertices V-V_is?

Answer 19

V-V_is forms a vertex cover.

Question 20

If you have a graph G=(V,E), and V_is are vertices that form an indepdent set of G, what can be said about G(V_is,E_modify) where E_modify contains all the edges that are not in E?

Answer 20

G(V_is,E_modify) forms a clique of the same size as the indepdent set.

Question 21

What is the hitting set input and output? Is it NP Complete?

Answer 21

**Input**: S, b
A set of sets, S = {s1, s2, …, sn} and a budget b. We want to find a set H such that |H| <= b and for all s_i in S, there exists an element in element a in H such that a in s_i.

**Output**:
- The set H

-“No” if no such set exists.

NP-Complete? YES!

Question 22

How long does it take to verfiy a subsetsum solution?

Answer 22

Given inputs a1, …, an and t and S, check that Sum a_i = t. This takes O(nlogt) because each number is log(a_i) size. This is polynomial in the input size.