Transcript Reductions, Lecture 16

Hardness Results for Problems
• P: Class of “easy to solve” problems
• Absolute hardness results
• Relative hardness results
– Reduction technique
Fundamental Setting
When faced with a new problem P, we
alternate between the following two goals
1. Find a “good” algorithm for solving P
•
•
Use algorithm design techniques
2. Prove a “hardness result” for problem P
•
No “good” algorithm exists for problem P
Complexity Class P
•
P is the set of problems that can be solved using a
polynomial-time algorithm
–
–
•
•
•
Sometimes we focus only on decision problems
The task of a decision problem is to answer a yes/no question
If a problem belongs to P, it is considered to be
“efficiently solvable”
If a problem is not in P, it is generally considered to be
NOT “efficiently solvable”
Looking back at previous slide, our goals are to:
1. Prove that P belongs to P
2. Prove that P does not belong to P
Hardness Results for Problems
• P: Class of “easy to solve” problems
• Absolute hardness results
• Relative hardness results
– Reduction technique
Absolute Hardness Results
• Fuzzy Definition
– A hardness result for a problem P without
reference to another problem
• Examples
– Solving the clique problem requires W(n) time
in the worst-case
– Solving the clique problem requires W(2n)
time in the worst-case.
– The clique problem is not in P.
Proof Techniques
• Diagonalization
– We don’t cover, but can be used to prove superpolynomial times
required for some problems
• Information Theory argument
– W(nlog n) lower bound for sorting
– Typically not a superpolynomial lower bounds
• “Size of input” argument
– Prove that solving the graph connectivity problem requires W(V2) time
– Prove that solving the maximum clique problem requires W(V2) time
– Typically not a superpolynomial lower bound
Status
• Many natural problems can be shown to be in P
– Graph connectivity
– Shortest Paths
– Minimum Spanning Tree
• Very few natural problems have been proven to NOT be in P
– Variants of halting problem are one example
• Many natural problems cannot be placed in or out of P
–
–
–
–
Satisfiability
Clique Problem
Hamiltonian Path
Traveling Salesperson
Hardness Results for Problems
• P: Class of “easy to solve” problems
• Absolute hardness results
• Relative hardness results
– Reduction technique
Relative Hardness Results
•
•
Fuzzy Definition
– A hardness result for a problem P without reference to
another problem
Examples
– Satisfiability is at least as hard as Hamiltonian Path to
solve
– If Satisfiability is unsolvable, then Hamiltonian Path
is unsolvable.
– If Satisfiability is in P, then Hamiltonian Path is in P
– If Hamiltonian Path is not in P, then Satisfiability is
not in P
Important Observation
•
•
•
We are interested in relative hardness results
BECAUSE of our inability to prove absolute
hardness results
That is, if we could prove strong absolute
hardness results, we would not be as interested in
relative hardness results
Example
– If I could prove “Satisfiability is not in P”, then I
would be less interested in proving “If Hamiltonian
Path is not in P, then Satisfiability is not in P”.
Relative Hardness Proof Technique
• We show that P2 is at least as hard as P1 in
the following way
• Informal: We show how to solve problem
P1 using a procedure P2 that solves P2 as a
subroutine
Examples
•
Multiplication and Squaring
– square(x) = mult(x,x)
•
Proves multiplication is at least as hard as squaring
– mult(x,y) = (square(x+y) – square(x-y))/4
•
•
•
Prove squaring is at least as hard as multiplication
Assumes that addition, subtraction, and division by 4 can be
done with no substantial increase in complexity
Specific complexity of multiplication may be higher as there
are two calls to square, but the difference is polynomially
bounded
Hardness Results for Problems
• P: Class of “easy to solve” problems
• Absolute hardness results
• Relative hardness results
– Reduction technique
Decision Problems
•
•
We now restrict our attention to decision
problems
Key characteristic: 2 types of inputs
– Yes input instances
– No input instances
•
Almost all natural problems can be converted
into an equivalent decision problem without
changing the complexity of the problem
– One technique: add an extra input variable that
represents the solution for the original problem
No loss of complexity
•
Example using clique problem
– Non-decision Problems
•
•
•
Input: Graph G=(V,E)
Task: Output size of maximum clique in G
Task 2: Output a maximum sized clique of G
– Decision Problems
•
•
•
Input: Graph G=(V,E), integer k <= |V|
Y/N Question: Does G contain a clique of size k?
Your task
– Show that if we can solve decision clique in
polynomial-time, then we can solve the non-decision
clique problems in polynomial-time.
Reduction Technique
•
•
In CSE 460, I use the terminology “Answerpreserving input transformation”
A many-one reduction R is a computable
function mapping inputs of problem P1 to inputs
of problem P2
– R is computable by some program/algorithm
– x is a yes input to P1  R(x) is a yes input to P2
•
Notation: P1 <=m P2
Pictoral Representation of Reduction
x
Input to P1
R
R(x)
P2
solves
P2
P1 solves P1
Y/N
Yes/No
Solvability Implications
Yes Input to P1
No Input to P1
R
Yes Input
to P2
P2
solves
No Input
P
2
to P2
P1 solves P1
If many-one reduction R exists, then:
If P2 is solvable, then P1 is solvable
If P1 is not solvable, then P2 is not
solvable
Yes
No
Relative hardness properties
•
•
Suppose P1 <=m P2
Consequences
– If P2 is solvable, then P1 is solvable
– If P1 is not solvable, then P2 is not solvable
•
•
Thus, in some sense, P1 is no harder than P2
However, for all solvable problems P1 and P2,
P1 <=m P2 and P2 <=m P1, so this does not help
us define the relative hardness of solvable
problems
Polynomial-time Reductions
• A polynomial-time many-one reduction R
is a computable function mapping inputs
of problem P1 to inputs of problem P2
– R is computable by some program/algorithm
in polynomial-time
– x is a yes input to P1  R(x) is a yes input
to P2
• Notation: P1 <=p P2
“In P” Implications
Yes Input to P1
No Input to P1
R
Yes Input
to P2
P2 solves
P2 in poly
time
No Input
to P2
P1 solves P1 in polynomial-time
Yes
No
If polynomial time many-one reduction R exists,
then:
If P2 is in P, then P1 is in P
If P1 is not in P, then P2 is not in P
Relative hardness properties
• Suppose P1 <=p P2
• Consequences
– If P2 is in P, then P1 is in P
– If P1 is not in P, then P2 is not in P
• Thus, in exactly the sense we want, P1 is
no harder than P2
Showing P1 <= P2
•
•
For any x input for P1, specify what R(x) will be
Show that R(x) has polynomial size relative to x
– You should show that R runs in polynomial time; I
only require the size requirement above
•
•
Show that if x is a yes instance for P1, then R(x)
is a yes instance for P2
Show that if x is a no instance for P1, then R(x)
is a no instance for P2
– Often done by showing that if R(x) is a yes instance
for P2, then x must have been a yes instance for P1
Example: HP <=p HC
• Hamiltonian Path
– Input: Undirected Graph G = (V,E)
– Y/N Question: Does G contain a Hamiltonian
Path?
• Hamiltonian Cycle
– Input: Undirected Graph G = (V,E)
– Y/N Question: Does G contain a Hamiltonian
Cycle?
Specification of R(x)
• Consider any undirected graph G = (V,E)
as input x
• R(x) will be a graph G’ = (V’, E’) where
– V’ = V union {v} where v is not in V
– E’ = E union {(v,w) | w in V}
• Argument that R(x) has polynomial size
– We add exactly 1 node and |V| edges.
x is yes  R(x) is yes
•
•
•
Suppose graph G has a Hamiltonian Path
Let this path be v1, v2, …, vn
We now argue that v1, v2, …, vn, v is a
Hamiltonian Cycle in G’
– First, all nodes in V’ are included exactly once above
or else v1, v2, …, vn would not be a HP in G
– Since G’ has all the edges that G has, (vi,vi+1) is an
edge in E’ for 1 <= i <= n-1
– Finally, since E’ contains edge (v,w) for all w in V, it
must be the case that E’ contains edges (vn, v) and
(v,v1).
R(x) is yes  x is yes
•
•
•
Suppose graph G’ has a Hamiltonian Cycle
Let this cycle be v1, v2, …, vn, v
We now argue that v1, v2, …, vn is a Hamiltonian
Path in G
– First, all nodes in V are included exactly once above
or else v1, v2, …, vn, v would not be a HC in G’
– Since the only extra edges in E’ compared to E are
edges involving node v, it must be the case that E
contains edge (vi,vi+1) for 1 <= i <= n-1
Turing Reducibility
•
•
Phil made a suggestion for an alternate reduction.
Given graph G, output Q(n2) graphs Gv,w = (V,Ev,w) where
–
•
•
This is not a polynomial-time reduction because we are outputting
Q(n2) graphs.
However, this idea can be used to show that if HC can be solved in
polynomial time, then HP can be solved in polynomial time.
–
–
–
•
•
Ev,w = E union {(v,w)} where v,w are nodes in V
Run each graph Gv,w through our procedure that solves HC.
If HC says yes for any one of these graphs, return yes.
Otherwise return no.
This more general reduction is often called a Turing reduction.
We allow ourselves to use the procedure that solves HC (or P2) a
polynomial number of times rather than just once.