NP Flashcards
Polynomial time reductions
“Polynomial time reductions
reduction: we will show that a particular problem X is at least as hard as some other
problem Y by arguing that, if we had a “black box” capable of solving X,
then we could also solve Y. (In other words, X is powerful enough to let us
solve Y.)
To make this precise, we add the assumption that X can be solved in
polynomial time directly to our model of computation.
(∗) Can arbitrary instances of problem Y be solved using a polynomial
number of standard computational steps, plus a polynomial number of
calls to a black box that solves problem X?
“
Independent sets
“Recall that in a graph G= (V, E), we say a set of nodes
S ⊆ V is independent if no two nodes in S are joined by an edge.
Decision version: Given a graph G and a number k, does G contain an independent set of
size at least k?
(8.3) Let G= (V, E) be a graph. Then S is an independent set if and only if its complement V− S is a vertex cover.”
Vertex cover
“Given a graph G= (V, E), we say that a set of nodes S ⊆ V is a vertex cover if every edge e ∈ E has at least one end in S.
Now, it is easy to find large vertex covers in a graph (for example, the full vertex
set is one); the hard part is to find small ones.
Given a graph G and a number k, does G contain a vertex cover of size at
most k?
(8.3) Let G= (V, E) be a graph. Then S is an independent set if and only if its complement V− S is a vertex cover.”
Set Cover
“We can phrase Set Cover as follows.
Given a set U of n elements, a collection S1, . . . , Sm of subsets of U, and a number k, does there exist a collection of at most k of these sets whose union is equal to all of U?
Vertex cover <p Set cover”
3-SAT - reductions via satisfiability
Circuit Satisfiability
”s a problem where we are given a logic circuit and asked a simple question:
““Is there a way to set the inputs of this circuit (true or false) so that the output of the circuit is true?””
(8.16) All of the following problems are NP-complete: Independent Set, Set Packing, Vertex Cover, and Set Cover.”
The traveling salesman problem
“Consider a salesman who must visit n cities labeled v1, v2, . . . , vn.
The salesman starts in city v1, his home, and wants to find a tour—an order
in which to visit all the other cities and return home. His goal is to find a tour
that causes him to travel as little total distance as possible.
Here is a decision version of the Traveling Salesman Problem.
Given a set of distances on n cities, and a bound D, is there a tour of length
at most D?
Hamiltonian Cycle <P traveling salesman”
The Hamiltonian Cycle problem
“Given a directed graph G= (V, E), we say that a cycle C in G is a Hamiltonian cycle if it visits each
vertex exactly once. In other words, it constitutes a “tour” of all the vertices, with no repetitions.
We do this by first establishing the NP-completeness of Hamiltonian Cycle, and then proceeding
to reduce from Hamiltonian Cycle to Traveling Salesman.
We now show that 3-SAT ≤P Hamiltonian Cycle. Why are we reducing
from 3-SAT?
We now show that Hamiltonian Cycle ≤P Traveling Salesman.”
The Hamiltonian Path Problem
“Thus, given a directed graph G= (V, E), we say that a path P in G is a Hamiltonian path if it contains each vertex exactly once. (The path is allowed to start at any node and end
at any node, provided it respects this constraint.)
8.19) Hamiltonian Path is NP-complete.
One way to show that Hamiltonian Path is NP-complete is to use a reduc-
tion from 3-SAT that is almost identical to the one we used for Hamiltonian
Cycle:
An alternate way to show that Hamiltonian Path is NP-complete is to prove
that Hamiltonian Cycle ≤P Hamiltonian Path.”
Graph coloring
“Graph coloring refers to the same process on an undirected graph G, with the
nodes playing the role of the regions to be colored, and the edges representing
pairs that are neighbors. We seek to assign a color to each node of G so
that if (u, v) is an edge, then u and v are assigned different colors; and
the goal is to do this while using a small set of colors.
k-coloring of G is a function f : V → {1, 2, . . . , k} so that for every edge (u, v),
we have f(u) ̸= f(v).
Given a graph G and a bound k, does G have a k-coloring?
(8.21) A graph G is 2-colorable if and only if it is bipartite
(8.22) 3-Coloring is NP-complete.
So once again, we’re going to reach all the way back to 3-SAT”
Subset sums problem
“a special case of the Knapsack Problem.
Given natural numbers w1, . . . , wn, and a target number W, is there a
subset of {w1, . . . , wn} that adds up to precisely W? in Section 6.4. The algorithm we developed there has running time O(nW), which is reasonable
when W is small, but becomes hopelessly impractical as W (and the numbers
wi) grow large.
(8.23) Subset Sum is NP-complete.
The 3-Dimensional Matching Problem
is a natural choice; we show that 3-Dimensional Matching ≤P Subset Sum.”
