Class NP
 The class of decision problems for which there is a polynomially bounded nondeterministic algorithm.
 The class of problems that are "slightly harder" than P.
 In general, an exponential number of subproblems, each of which can be solved or verified in polynomial time.
 Being in class NP constitutes an upper bound on problem complexity.
Nondeterministic Turing Machine (NDTM)
 The tree has polynomial depth but is exponentially bushy.
NPhard
NPComplete
Satisfiability (SAT)
e.g., (x_{1} + x_{2} + ¬x_{3}) · (x_{1} + x_{3}) · (¬x_{2})
 easy to falsify: make all terms in one clause fail.
 hard to satisfy: terms in clauses interact.
 uses SAT to simulate a machine
 To prove that problem Q is NPcomplete, reduce SAT
(or any other NPcomplete problem) to Q:
SAT <=_{P} Q  E.g., 3SAT: like SAT, but  c_{i}  = 3 for 1 <= i <= n.
 Need to show that 3SAT is NPhard:
Since X <=_{P} SAT for any problem X in NP, we need only show SAT <=_{P} 3SAT.  Proof:
General form of clauses in SAT is c_{j} = (z_{1} + z_{2} + ... + z_{k}), where each z_{i} is either an input or the negation of an input. k = 1
 {z_{1} + z_{1} + z_{1}}
 k = 2
 {z_{1} + z_{2} + z_{2}}
 k = 3
 {z_{1} + z_{2} + z_{3}}
 k >= 4
 Add auxiliary variables that transmit information between pieces.
E.g., {z_{1} + z_{2} + z_{3} + z_{4} + z_{5}} becomes {(z_{1} + z_{2} + y_{1}) (¬y_{1} + z_{3} + y_{2}) (¬y_{2} + z_{4} + z_{5})}
Note: 2SAT is solvable in polynomial time.
Other NPComplete Problems

 Graph coloring
 A coloring of a graph is the assignment of a "color" to each vertex
of the graph such that adjacent vertices are not assigned the same color.
The chromatic number of a graph G, X(G) [Chi(G)],
is the smallest number of colors needed to color G.
Optimization problem: Given an undirected graph G, determine X(G) (and produce an optimal coloring).
Decision problem: Given G and a positive integer k, is there a coloring of G using at most k colors (i.e., is G kcolorable)?

 Job scheduling with penalties
 Suppose we are given n jobs to be executed one at a time and,
for each job, an execution time, deadline, and penalty for missing the deadline.
Optimization problem: Determine the minimum possible penalty (and find an optimal schedule).
Decision problem: Given a nonnegative integer k, is there a schedule with penalty < k?

 Multiprocessor scheduling
 Suppose we are given a deadline and a set of tasks of varying length to be performed
on two identical processors.
Optimization problem: Determine an allocation of the tasks to the two processors such that the deadline can be met.
Decision problem: Can the tasks be arranged so that the deadline is met?

 Bin packing
 Optimization problem: Given an unlimited number of bins, each of size 1,
and n objects with sizes s_{1}, ..., s_{n}
where 0 < s_{i} < 1,
determine the smallest number of bins into which the objects can be packed (and find
an optimal packing).
Decision problem: Given, in addition to the inputs described above, an integer k, do the objects fit in k bins?

 Knapsack problem
 Optimization problem: Given a knapsack of capacity C and
n objects with sizes s_{1}, ..., s_{n}
and "profits" p_{1}, ..., p_{n},
find the largest total profit of any subset of the objects that fits in the knapsack
( and find a subset that achieves the maximum profit).
Decision problem: Given k, is there a subset of the objects that fits in the knapsack and has total profit at least k?

 Subset sum problem
 Optimization problem: Given a positive integer C and n objects
with positive sizes s_{1}, ..., s_{n}, among subsets
of the objects with sum at most C, what is the largest subset sum?
Decision problem: Is there a subset of the objects whose sizes add up to exactly C?

 Partition
 Suppose we are given a set of integers.
Decision problem: Can the integers be partitioned into two sets whose sum is equal?

 Hamiltonian cycles and Hamiltonian paths
 A Hamiltonian cycle (path) is a simple cycle (path)
that passes through every vertex of a graph exactly once.
Decision problem: Does a given undirected graph have a Hamiltonian cycle (path)?

 Traveling salesperson problem (TSP) or minimum tour problem
 Optimization problem: Given a complete, weighted graph,
find a minimumweight Hamiltonian cycle.
Decision problem: Given a complete, weighted graph and an integer k, is there a Hamiltonian cycle with total weight at most k?

 Vertex cover
 A vertex cover for an undirected graph G is a subset V' of vertices
such that each edge in G is incident upon some vertex in V'.
Optimization problem: Find a vertex cover for G with as few vertices as possible.
Decision problem: Given an integer k, does G have a vertex cover consisting of k vertices?

 Clique
 A clique is a subset V' of vertices in an undirected graph G such that
every pair of distinct vertices in V' is joined by an edge in G (i.e., the subgraph
induced by V' is complete). A clique with k vertices is called a kclique.
Optimization problem: Find a clique with as many vertices as possible.
Decision problem: Given an integer k, does G have a kclique?

 Independent set
 An independent set is a subset V' of vertices in an undirected graph G
such that no pair of vertices in V' is joined by an edge of G.
Optimization problem: Find an independent set with as many vertices as possible.
Decision problem: Given an integer k, does G have an independent set consisting of k vertices?

 Feedback edge set
 A feedback edge set in a digraph G is a subset E' of edges such that
every cycle in G has an edge in E'.
Optimization problem: Find a feedback edge set with as few edges as possible.
Decision problem: Given an integer k, does G have a feedback edge set consisting of k edges?

 Longest simple path problem
 Optimization problem: What is the longest simple path between any
two vertices in graph G?
Decision problem: Given an integer k, is there a path in graph G longer than k?

 Subgraph isomorphism
 Decision problem: Given two graphs G_{1} and G_{2}, determine if G_{1} is isomorphic to a subgraph of G_{2}.

 Integer linear programming
 Linear programming is a method of analyzing systems of linear inequalities
to arrive at optimal solutions to problems
Decision problem: Given a linear program, is there an integral solution?
References
 Baase and Van Gelder, Computer Algorithms, 3e (Addison Wesley Longman, 2000)
 Sedgewick, Algorithms (Addison Wesley, 1983)
 Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2e (MIT Press/McGraw Hill, 2001) The authors provide NPcompleteness proofs reducing 3SAT to CLIQUE to VERTEXCOVER to HAMILTONIANCYCLE to TSP, and 3SAT to SUBSETSUM.
No comments:
Post a Comment