NP

Question 1

SAT: inputs and outputs

Answer 1

Inputs:
- Boolean formula in CNF with n variables and m clauses

Outputs:
- A satisfying assignment S such that each clause evaluates to True
- NO, if no such assignment exists

Question 2

k-SAT: inputs and outputs

Answer 2

Inputs:
- Boolean formula in CNF with n variables and m clauses. Each clause has no more than k literals.

Outputs:
- A satisfying assignment S such that each clause evaluates to True
- NO, if no such assignment exists

Question 3

For what values of k is k-SAT NP-Complete?

Answer 3

k >= 3

Question 4

Knapsack-Search: inputs and outputs

Answer 4

Inputs:
- n items with integer values v_i and weights w_i
- capacity B
- goal g

Outputs:
- A subset S of items for which we can sum values v_i to be >= g and w_i to be <= b
- NO, if no such S exists

Question 5

Independent-Set Search: inputs and outputs

Answer 5

Inputs:
- Graph G
- Goal g

Outputs:
- A set S of vertices of |S| >= g with no edges between them, forming an independent set
- NO, if no such S exists

Question 6

Is Knapsack-Seach NP-Complete?

Answer 6

Yes! It’s the optimization version (find the max value for a given capacity) that’s not NP-C. It’s not NP-C because we can’t verify the solution in polynomial time, so it’s not in NP at all. We need to run Knapsack again to verify the solution, and this version of Knapsack is not polynomial in the input size.

Question 7

Clique: inputs and outputs

Answer 7

Inputs:
- Undirected graph G
- Goal g

Outputs:
- Set S of vertices such that |S|>= g and there is an edge e = (u,v) for every pair u,v in S
- NO if no such S exists

Question 8

Vertex Cover: inputs and outputs

Answer 8

Inputs:
- Undirected graph G
- Budget b

Outputs:
- Set S of vertices such that |S|<= b and for every edge e = (u, v) in G, either u or v are in S
- NO if no such S exists

Question 9

Subset-Sum: inputs and outputs

Answer 9

Inputs:
- n positive integers a_i
- Target t

Outputs:
- Subset S of [1..n] such that the sum over all a_i with i in S == t
- NO if no such S exists

Question 10

What’s the intuitive definition of “Vertex Cover”?

Answer 10

A set of vertices that covers every edge

Question 11

Which graph problems specifically take undirected graphs as part of their input?

Answer 11

Clique and Vertex Cover

Question 12

Does the Independent Set problem require the input graph G to be directed or undirected?

Answer 12

No, it doesn’t matter.

Question 13

Given a SAT problem, how to you reduce a clause of size k to conjunction of clauses of size <= 3? i.e., 3SAT

Answer 13

We’re given a clause (x1 v x2 v … xk).

We create k-3 new variables y1..y(k-3).

Then we create clauses (x1 v x2 v y1) ^ (!y1 v x3 v y2) ^ … ^ (!y(k-3) v x(k-1) v xk)

Question 14

Given a clause of size 4 (x1 v x2 v x3 v x4), how do you reduce it to clauses of size 3?

Answer 14

Give (x1 v x2 v x3 v x4), we create one new variable y and do the following:

(x1 v x2 v y) ^ (!y v x3 v x4)

Question 15

Given a clause of size 5 (x1 v x2 v x3 v x4 v x5), how do you reduce it to clauses of size 3?

Answer 15

Given (x1 v x2 v x3 v x4 v x5), we create two new variables y1 and y2, then do the following:

(x1 v x2 v y1) ^ (!y1 v x3 v y2) ^ (!y2 v x4 v x5)

Question 16

How do you expand a clause of size 3 (x1 v x2 v x3) to a clause of size 4?

Answer 16

Given (x1 v x2 v x3), create one new variable y, then:

(x1 v x2 v x3 v y) ^ (x1 v x2 v x3 v !y).

To get larger clauses, we repeat this process! Like so:

(x1 v x2 v x3 v y1 v y2) ^ (x1 v x2 v x3 v !y1 v y2) ^ (x1 v x2 v x3 v y1 v !y2) ^ (x1 v x2 v x3 v !y1 v !y2).

Question 17

How do you reduce a clause of size 3 (x1 v x2 v x3) to clauses of size 2 while maintaining the requirement that x1 = x2 = x3?

Answer 17

Given (x1 v x2 v x3), we do:

(x1 v !x2) ^ (x2 v !x3) ^ (x3 v !x1)

We can do the same for larger clauses too! Such as (x1 v x2 v x3 v x4):

(x1 v !x2) ^ (x2 v !x3) ^ (x3 v !x4) ^ (x4 v !x1)

It just takes another clause.

Question 18

How do you express in CNF the statement A = B?

Answer 18

Same as reducing a clause of size 3 to size 2:

(A v !B) ^ (!A v B)

Question 19

How do you express in CNF the statement A != B?

Answer 19

(A v B) ^ (!A v !B)

This prevents A and B from taking the same value.

Question 20

What special thing do you have to do with clauses like (x v !x)

Answer 20

Nothing! They’re always true, so you could depending on the case, drop or ignore them.

Question 21

What do you do with a clause of size 1?

Answer 21

A clause of size 1 like (x) always evaluates to True.