Reductions NPC Flashcards
NPC
A language L is NPC if Lis NP and for every language L’ in NP There is a reduction from L’ to L
Cook Levin theorem
SAT∈NPC
3SAT∈NPC (SAT≤3SAT)
For every clause C that has more than three literals we change it to C’:
C’=(l1∨y1)∧
(~y1∨l2∨y2) ∧
(~y2∨l3∨y3) ∧
…
(~yk-1∨lk∨yk) ∧
…
(~ym-2∨lm-1∨ym-1) ∧
(~ym-1∨lm)
For a clause with less than three, we just multiply the existing ones
Vertex cover problem (VC)
Given an undirected graph G, what is the minimal group M of nodes so that each edge in the graph is covered. For the verification problem, we ask if there is a vertex cover under k.
VC∈NPC (3SAT≤VC)
For every atomic class Xi we add to the graph
Xi <—> ~Xi
For every clause we create a triangle and add it to the graph. We then connect each part of the triangle to the correct assignment in the atomic clause. For example If I1 is ~X5 we connect them.
We also declare k = n+2m (n number of atomic clauses, m number of clauses).
Set Cover problem (SC)
Given a group of object S and a list of it’s sub-groups, what is the minimal number of subgroups so that each object in S is in at least one of the chosen subgroups.
SC∈NPC (VC≤SC)
The nodes in the VC graph will act as the subgroups, so we have n number of subgroups. Which each subgroup i being the edges going out from the ith node. And the original group S = E.
The Clique problem (CLQ)
Given a graph G, is there a sub graph, that is fully connected of size k.
CLQ∈NPC (VC≤CLQ)
Given a input (G=(V,E),k) for the VC problem, we construct the input for the CLQ problem
( (G=(V,~E),|V|-k)).
3COL ≤ 4COL
Given a graph input G add to G a new node w and connect it to all nodes in G. This way if G is 3 colored, than you can 4 color it by just coloring in w in. a new color. Since w is connected to all, if the graph is 4 colored, than w is an exclusive color and G is 3 colored.
3COL ≤ Almost 3COL
Given a graph G, create the new graph G’ by adding to it a separate clique of size 4. If G is 3 colored, then the new graph is almost 3 colored with the miss being in the clique. If G’ is almost 3 colored, than G must be 3 colored.
TSP∈NPC (HAM≤TSP)
Given a graph G from the Hamilton cycle problem, we will build a new graph that is the same but a fully connected graph. With edge weight of 0 if it was present in G and 1 if not. Dnd set k=0.
Subset-Sum∈NPC (3SAT≤Subset-Sum)
Given a 3SAT input with I variables and k clauses, we create a subset S with 2I + 2k members.
S:
yi has a 1 in every column i and in every column Cj where Xi is present.
zi has a 1 in every column i and in every column Cj where ~Xi is present.
gi and hi each have 1 in every Cj column.
partition problem
Given a set of numbers S return a possible partition so that both sub groups are different and their sums are equal.
PAR∈NPC (Subset-Sum≤PAR)
Given a (S,t) input for Subset Sum, we set our target k to be the half of the sum.
**If t=k: **
S’ = S
**If t < k: **
S’ = S ∪ {2k-st}
If t > k:
S’ = S ∪ {2t-sk}
