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.
• Some basic facts about PLS
  • LEMMA [JPY88, Lemma 3]: P_S \subseteq PLS \subseteq NP_S
  • 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