NP Flashcards
SAT: inputs and outputs
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
k-SAT: inputs and outputs
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
For what values of k is k-SAT NP-Complete?
k >= 3
Knapsack-Search: inputs and outputs
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
Independent-Set Search: inputs and outputs
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
Is Knapsack-Seach NP-Complete?
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.
Clique: inputs and outputs
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
Vertex Cover: inputs and outputs
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
Subset-Sum: inputs and outputs
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
What’s the intuitive definition of “Vertex Cover”?
A set of vertices that covers every edge
Which graph problems specifically take undirected graphs as part of their input?
Clique and Vertex Cover
Does the Independent Set problem require the input graph G to be directed or undirected?
No, it doesn’t matter.
Given a SAT problem, how to you reduce a clause of size k to conjunction of clauses of size <= 3? i.e., 3SAT
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)
Given a clause of size 4 (x1 v x2 v x3 v x4), how do you reduce it to clauses of size 3?
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)
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?
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)
How do you expand a clause of size 3 (x1 v x2 v x3) to a clause of size 4?
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).
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?
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.
How do you express in CNF the statement A = B?
Same as reducing a clause of size 3 to size 2:
(A v !B) ^ (!A v B)
How do you express in CNF the statement A != B?
(A v B) ^ (!A v !B)
This prevents A and B from taking the same value.
What special thing do you have to do with clauses like (x v !x)
Nothing! They’re always true, so you could depending on the case, drop or ignore them.
What do you do with a clause of size 1?
A clause of size 1 like (x) always evaluates to True.
