The Complexity of
Finding Locally Optimal Solutions
Todd Wareham
January 26, 2010
Optimization Search Problems
(Feasible) solution spaces and neighborhoods; are defined
relative to particular instances of a given problem.
Two representations of a solution space / neighbourhood pair:
neighbourhood graphs and transition graphs [SY91,
Definition 3.1].
Globally optimal solutions defined relative to solution
spaces; locally optimal solutions defined relative to
solution-space / neighbourhood pairs.
Why care about local optimality?
Finding local solutions by the standard hill-climbing
algorithm is typically assumed to be easy -- but is it
always so?
If there is a polynomially-bounded number of possible
solution-values, can always find a local optimum in
poly-time by hill-climbing; however, if problem has
weights and hence a non-polynomial number of possible
solution-values, this need not hold.
Sometimes, all local optima are also global optima and
worth finding in themselves, e.g., Knuth's matrix
problem [JPY88, p. 81].
Sometimes, an interesting computational process just yields
local optima, e.g., Hopfield Networks.
Some questions of interest:
Given an optimization search problem P with neighbourhood-function N(),
How hard is it to verify if a given solution s to a given instance
x of P is locally optimal? (Verification Problem)
How hard is it to find a locally optimal solution s for a given instance
x of P? (Local Optimum Problem)
How hard is it to find a locally optimal solution s for a given instance
x of P that is reachable (possibly by the standard hill-climbing
algorithm) from a given solution s' for i?
(Standard Algorithm Problem)
The Complexity Class PLS (Polynomial-time Local Search)
Defined relative to optimization search problem / neighbourhood pairs;
hence, a problem with many neighborhoods may have many associated
PLS problems.
DEFINITION [JPY88, Section 2]:
An optimization search problem is in PLS
if it has polynomial-time algorithms A (get initial
solution), B (evaluate cost of given solution), and C (determine if
given solution is locally optimal, and if not, return better solution
in neighbourhood of given solution).
Natural standard hill-climbing algorithm relative to A, B, and C.
Note that standard algorithm need not run in polynomial time;
membership in PLS only says that algorithms A, B, and C run in
polynomial time.
LEMMA [JPY88, Lemma 4]: If a PLS-problem P is NP-hard then NP = co-NP
LEMMA [JPY88, Lemma 1]: There is a PLS-problem whose standard algorithm
requires exponential time and whose standard algorithm problem is NP-hard.
Reducibilities between problems in PLS
PLS-reducibility
DEFINITION [JPY88, p. 85]: PLS-problem P PLS-reduces
to PLS-problem Q is there are polynomial-time computable
functions f and g such that (i) f maps instances x of
P to instances f(x) of Q, (ii) g maps (solution of f(x),
x) pairs to solutions of x, and (iii) for all instances
x of P, if s is
a local optimum for a solution of f(x) then g(s, x) is
a local optimum for x.
LEMMA [JPY88, Lemma 5]: If P PLS-reduces to Q and Q PLS-reduces to R then
P PLS-reduces to R
LEMMA [JPY88, Lemma 6]: If P PLS-reduces to Q and there is a poly-time algorithm
for finding a local optimum for Q then there is a
poly-time algorithm for finding local optima of P.
Tight PLS-reducibility
DEFINITION [SY91, Definition 3.2] (bad paraphrase):
A PLS-reduction from PLS-problem P to PLS-problem Q
is tight if paths in the transition graph associated
with instance x of P are of length less than or equal
to the corresponding paths in the transition graph
associated with instance f(x) of Q.
LEMMA [SY91, p. 63]: If P tight PLS-reduces to Q and
Q tight PLS-reduces to R then P tight PLS-reduces to R
LEMMA [SY91, Lemma 3.3]: If P tight PLS-reduces to Q such
that instance x of P is transformed to instance f(x) of
Q and the standard algorithm on x requires time T in
the worst case (the standard algorithm problem for P is
NP-hard) then the standard algorithm on f(x) requires
time at least T (the standard algorithm problem for Q
is NP-hard).
Known Results:
Circuit / Flip is PLS-complete [JPY88, Theorem 1].
The following PLS-problems are PLS-complete by tight PLS-reduction
chains originating with Circuit / Flip [SY91, Corollary 5.12]:
Travelling Salesman / k-OPT and Travelling Salesman / Lin-Kernighan
Graph Partitioning / Kernighan-Lin
Max Cut / Flip
Max 2SAT / Flip
Stable Configuration for Hopfield Neural Networks / Flip
The verification problems associated with these PLS-complete problems
range between LOGSPACE [Kre90, Theorem 2.2] and P-complete [JPY88, Section 5] contra the conjecture in Section 5 of
Johnson, Papadimitriou, and Yannakakis (1988).
Finding local optima for all of these PLS-complete problems require
exponential time in the worst case [SY91, Theorem 5.15(1)] and the associated standard
algorithm problems are PSPACE-complete [PSY90, Theorem 6]; however, the unweighted versions
of the last four problems are P-complete [SY91, Corollary 4.6].
Positive result: Unweighted Hopfield Neural Nets are a universal
model of polynomial-time computation [PSY90, p. 440].
Where do we go from here?
Link between local search and approximability [AP95]
Connection to human problem-solving via local search.
References
Ausiello, G. and Protasi, M. (1995) "Local search, reducibility and approximability of
NP-optimization problems." Information Processing Letters, 54, 73-79.
Johnson, D.S., Papadimitriou, C.H., and Yannakakis, M. (1988) "How Easy is Local
Search?" Journal of Computer and System Sciences, 37, 79-100.
Krentel, M.W. (1990) "On Finding and Verifying Locally Optimal Solutions."
SIAM Journal on Computing, 19(4), 742-749.
Papadimitriou, C.H., Schaffer, A.A., and Yannakakis, M. (1990) "On the Complexity
of Local Search." In Proceedings of the 22nd Annual ACM Symposium on the Theory of
Computing (STOC'90). ACM Press. 438-445.
Schaeffer, A.A. and Yannakakis, M. (1991) "Simple Local Search Problems that are
Hard to Solve." SIAM Journal on Computing, 20(1), 56-87.
Yannakakis, M. (2003) "Computational Complexity." In E. Aarts and J.K. Lenstra (Eds.)
Local Search in Combinatorial Optimization. Princeton University Press.
19-55.
Created: January 25, 2010
Last Modified: January 26, 2010