PLS (complexity)

<h2 id="description">Description</h2>
When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> So to answer the question of how long it takes to find a local optimum, Johnson, Papadimitriou and Yannakakis <a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> introduced the complexity class PLS in their paper "How easy is local search?". It contains local search problems for which the local optimality can be verified in polynomial time.
A local search problem is in PLS, if the following properties are satisfied:

<ul><li>The size of every solution is polynomially bounded in the size of the instance 
 
 
 
 I
 
 
 {\displaystyle I}
 
.</li>
<li>It is possible to find some solution of a problem instance in polynomial time.</li>
<li>It is possible to calculate the cost of each solution in polynomial time.</li>
<li>It is possible to find all neighbors of each solution in polynomial time.</li></ul>
With these properties, it is possible to find for each solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 the best neighboring solution or if there is no such better neighboring solution, state that 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is a local optimum.

<h3>Example</h3>
Consider the following instance 
 
 
 
 I
 
 
 {\displaystyle I}
 
 of the <a href="/facts/2-satisfiability/cUMH5x2y">Max-2Sat</a> Problem: 
 
 
 
 (
 
 x
 
 1
 
 
 ∨
 
 x
 
 2
 
 
 )
 ∧
 (
 ¬
 
 x
 
 1
 
 
 ∨
 
 x
 
 3
 
 
 )
 ∧
 (
 ¬
 
 x
 
 2
 
 
 ∨
 
 x
 
 3
 
 
 )
 
 
 {\displaystyle (x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})}
 
. The aim is to find an assignment, that maximizes the sum of the satisfied clauses.
A solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 for that instance is a bit string that assigns every 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
 the value 0 or 1. In this case, a solution consists of 3 bits, for example 
 
 
 
 s
 =
 000
 
 
 {\displaystyle s=000}
 
, which stands for the assignment of 
 
 
 
 
 x
 
 1
 
 
 
 
 {\displaystyle x_{1}}
 
 to 
 
 
 
 
 x
 
 3
 
 
 
 
 {\displaystyle x_{3}}
 
 with the value 0. The set of solutions 
 
 
 
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle F_{L}(I)}
 
 is the set of all possible assignments of 
 
 
 
 
 x
 
 1
 
 
 
 
 {\displaystyle x_{1}}
 
, 
 
 
 
 
 x
 
 2
 
 
 
 
 {\displaystyle x_{2}}
 
 and 
 
 
 
 
 x
 
 3
 
 
 
 
 {\displaystyle x_{3}}
 
.
The cost of each solution is the number of satisfied clauses, so 
 
 
 
 
 c
 
 L
 
 
 (
 I
 ,
 s
 =
 000
 )
 =
 2
 
 
 {\displaystyle c_{L}(I,s=000)=2}
 
 because the second and third clause are satisfied.
The Flip-neighbor of a solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is reached by flipping one bit of the bit string 
 
 
 
 s
 
 
 {\displaystyle s}
 
, so the neighbors of 
 
 
 
 s
 
 
 {\displaystyle s}
 
 are 
 
 
 
 N
 (
 I
 ,
 000
 )
 =
 {
 100
 ,
 010
 ,
 001
 }
 
 
 {\displaystyle N(I,000)=\{100,010,001\}}
 
 with the following costs:

 
 
 
 
 c
 
 L
 
 
 (
 I
 ,
 100
 )
 =
 2
 
 
 {\displaystyle c_{L}(I,100)=2}

c
 
 L
 
 
 (
 I
 ,
 010
 )
 =
 2
 
 
 {\displaystyle c_{L}(I,010)=2}

c
 
 L
 
 
 (
 I
 ,
 001
 )
 =
 2
 
 
 {\displaystyle c_{L}(I,001)=2}

There are no neighbors with better costs than 
 
 
 
 s
 
 
 {\displaystyle s}
 
, if we are looking for a solution with maximum cost. Even though 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is not a global optimum (which for example would be a solution 
 
 
 
 
 s
 ′
 
 =
 111
 
 
 {\displaystyle s'=111}
 
 that satisfies all clauses and has 
 
 
 
 
 c
 
 L
 
 
 (
 I
 ,
 
 s
 ′
 
 )
 =
 3
 
 
 {\displaystyle c_{L}(I,s')=3}
 
), 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is a local optimum, because none of its neighbors has better costs.
Intuitively it can be argued that this problem lies in PLS, because:

<ul><li>It is possible to find a solution to an instance in polynomial time, for example by setting all bits to 0.</li>
<li>It is possible to calculate the cost of a solution in polynomial time, by going once through the whole instance and counting the clauses that are satisfied.</li>
<li>It is possible to find all neighbors of a solution in polynomial time, by taking the set of solutions that differ from 
 
 
 
 s
 
 
 {\displaystyle s}
 
 in exactly one bit.</li></ul>
If we are simply counting the number of satisfied clauses, the problem can be solved in polynomial time since the number of possible costs is polynomial. However, if we assign each clause a positive integer weight (and seek to locally maximize the sum of weights of satisfied clauses), the problem becomes PLS-complete (below).

<h2 id="formal-definition">Formal Definition</h2>
A local search problem 
 
 
 
 L
 
 
 {\displaystyle L}
 
 has a set 
 
 
 
 
 D
 
 L
 
 
 
 
 {\displaystyle D_{L}}
 
 of instances which are encoded using <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> over a finite <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
. For each instance 
 
 
 
 I
 
 
 {\displaystyle I}
 
 there exists a finite solution set 
 
 
 
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle F_{L}(I)}
 
. Let 
 
 
 
 R
 
 
 {\displaystyle R}
 
 be the relation that models 
 
 
 
 L
 
 
 {\displaystyle L}
 
. The relation 
 
 
 
 R
 ⊆
 
 D
 
 L
 
 
 ×
 
 F
 
 L
 
 
 (
 I
 )
 :=
 {
 (
 I
 ,
 s
 )
 ∣
 I
 ∈
 
 D
 
 L
 
 
 ,
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 }
 
 
 {\displaystyle R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}}
 
 is in PLS <a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> if:

<ul><li>The size of every solution 
 
 
 
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s\in F_{L}(I)}
 
 is polynomial bounded in the size of 
 
 
 
 I
 
 
 {\displaystyle I}
 
</li>
<li>Problem instances 
 
 
 
 I
 ∈
 
 D
 
 L
 
 
 
 
 {\displaystyle I\in D_{L}}
 
 and solutions 
 
 
 
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s\in F_{L}(I)}
 
 are polynomial time verifiable</li>
<li>There is a polynomial time computable function 
 
 
 
 A
 :
 
 D
 
 L
 
 
 →
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle A:D_{L}\rightarrow F_{L}(I)}
 
 that returns for each instance 
 
 
 
 I
 ∈
 
 D
 
 L
 
 
 
 
 {\displaystyle I\in D_{L}}
 
 some solution 
 
 
 
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s\in F_{L}(I)}
 
</li>
<li>There is a polynomial time computable function 
 
 
 
 B
 :
 
 D
 
 L
 
 
 ×
 
 F
 
 L
 
 
 (
 I
 )
 →
 
 
 R
 
 
 +
 
 
 
 
 {\displaystyle B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}}
 
 <a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> that returns for each solution 
 
 
 
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s\in F_{L}(I)}
 
 of an instance 
 
 
 
 I
 ∈
 
 D
 
 L
 
 
 
 
 {\displaystyle I\in D_{L}}
 
 the cost 
 
 
 
 
 c
 
 L
 
 
 (
 I
 ,
 s
 )
 
 
 {\displaystyle c_{L}(I,s)}
 
</li>
<li>There is a polynomial time computable function 
 
 
 
 N
 :
 
 D
 
 L
 
 
 ×
 
 F
 
 L
 
 
 (
 I
 )
 →
 P
 o
 w
 e
 r
 s
 e
 t
 (
 
 F
 
 L
 
 
 (
 I
 )
 )
 
 
 {\displaystyle N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))}
 
 that returns the set of neighbors for an instance-solution pair</li>
<li>There is a polynomial time computable function 
 
 
 
 C
 :
 
 D
 
 L
 
 
 ×
 
 F
 
 L
 
 
 (
 I
 )
 →
 N
 (
 I
 ,
 s
 )
 ∪
 {
 O
 P
 T
 }
 
 
 {\displaystyle C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}}
 
 that returns a neighboring solution 
 
 
 
 
 s
 ′
 
 
 
 {\displaystyle s'}
 
 with better cost than solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
, or states that 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is locally optimal</li>
<li>For every instance 
 
 
 
 I
 ∈
 
 D
 
 L
 
 
 
 
 {\displaystyle I\in D_{L}}
 
, 
 
 
 
 R
 
 
 {\displaystyle R}
 
 exactly contains the pairs 
 
 
 
 (
 I
 ,
 s
 )
 
 
 {\displaystyle (I,s)}
 
 where 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is a local optimal solution of 
 
 
 
 I
 
 
 {\displaystyle I}
 
</li></ul>
An instance 
 
 
 
 
 D
 
 L
 
 
 
 
 {\displaystyle D_{L}}
 
 has the structure of an <a href="/facts/Implicit_graph/ERbgYekg">implicit graph</a> (also called Transition graph <a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>), the vertices being the solutions with two solutions 
 
 
 
 s
 ,
 
 s
 ′
 
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s,s'\in F_{L}(I)}
 
 connected by a directed arc iff 
 
 
 
 
 s
 ′
 
 ∈
 N
 (
 I
 ,
 s
 )
 
 
 {\displaystyle s'\in N(I,s)}
 
.
A <a href="/facts/Local_optimum/f40GlzAw">local optimum</a> is a solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
, that has no neighbor with better costs. In the implicit graph, a local optimum is a sink. A neighborhood where every local optimum is a <a href="/facts/Maxima_and_minima/ADlgnyzV">global optimum</a>, which is a solution with the best possible cost, is called an exact neighborhood.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Alternative Definition</h3>
The class PLS is the class containing all problems that can be reduced in polynomial time to the problem Sink-of-<a href="/facts/Directed_acyclic_graph/k6zq1os9">DAG</a>[7] (also called Local-Opt <a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>):
Given two integers 
 
 
 
 n
 
 
 {\displaystyle n}
 
 and 
 
 
 
 m
 
 
 {\displaystyle m}
 
 and two <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a> 
 
 
 
 S
 :
 {
 0
 ,
 1
 
 }
 
 n
 
 
 →
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}
 
 such that 
 
 
 
 S
 (
 
 0
 
 n
 
 
 )
 ≠
 
 0
 
 n
 
 
 
 
 {\displaystyle S(0^{n})\neq 0^{n}}
 
 and 
 
 
 
 V
 :
 {
 0
 ,
 1
 
 }
 
 n
 
 
 →
 {
 0
 ,
 1
 ,
 .
 .
 ,
 
 2
 
 m
 
 
 −
 1
 }
 
 
 {\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}
 
, find a vertex 
 
 
 
 x
 ∈
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle x\in \{0,1\}^{n}}
 
 such that 
 
 
 
 S
 (
 x
 )
 ≠
 x
 
 
 {\displaystyle S(x)\neq x}
 
 and either 
 
 
 
 S
 (
 S
 (
 x
 )
 )
 =
 S
 (
 x
 )
 
 
 {\displaystyle S(S(x))=S(x)}
 
 or 
 
 
 
 V
 (
 S
 (
 x
 )
 )
 ≤
 V
 (
 x
 )
 
 
 {\displaystyle V(S(x))\leq V(x)}
 
.

<h3>Example neighborhood structures</h3>
Example neighborhood structures for problems with boolean variables (or bit strings) as solution:

<ul><li>Flip<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> - The neighborhood of a solution 
 
 
 
 s
 =
 
 x
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 x
 
 n
 
 
 
 
 {\displaystyle s=x_{1},...,x_{n}}
 
 can be achieved by negating (flipping) one arbitrary input bit 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
. So one solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 and all its neighbors 
 
 
 
 r
 ∈
 N
 (
 I
 ,
 s
 )
 
 
 {\displaystyle r\in N(I,s)}
 
 have <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> one: 
 
 
 
 H
 (
 s
 ,
 r
 )
 =
 1
 
 
 {\displaystyle H(s,r)=1}
 
.</li>
<li>Kernighan-Lin<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> - A solution 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is a neighbor of solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 if 
 
 
 
 r
 
 
 {\displaystyle r}
 
 can be obtained from 
 
 
 
 s
 
 
 {\displaystyle s}
 
 by a sequence of greedy flips, where no bit is flipped twice. This means, starting with 
 
 
 
 s
 
 
 {\displaystyle s}
 
, the Flip-neighbor 
 
 
 
 
 s
 
 1
 
 
 
 
 {\displaystyle s_{1}}
 
 of 
 
 
 
 s
 
 
 {\displaystyle s}
 
 with the best cost, or the least loss of cost, is chosen to be a neighbor of s in the Kernighan-Lin structure. As well as best (or least worst) neighbor of 
 
 
 
 
 s
 
 1
 
 
 
 
 {\displaystyle s_{1}}
 
 , and so on, until 
 
 
 
 
 s
 
 i
 
 
 
 
 {\displaystyle s_{i}}
 
 is a solution where every bit of 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is negated. Note that it is not allowed to flip a bit back, if it once has been flipped.</li>
<li>k-Flip<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> - A solution 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is a neighbor of solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
 if the <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> 
 
 
 
 H
 
 
 {\displaystyle H}
 
 between 
 
 
 
 s
 
 
 {\displaystyle s}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is at most 
 
 
 
 k
 
 
 {\displaystyle k}
 
, so 
 
 
 
 H
 (
 s
 ,
 r
 )
 ≤
 k
 
 
 {\displaystyle H(s,r)\leq k}
 
.</li></ul>
Example neighborhood structures for problems on graphs:

<ul><li>Swap<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> - A partition 
 
 
 
 (
 
 P
 
 2
 
 
 ,
 
 P
 
 3
 
 
 )
 
 
 {\displaystyle (P_{2},P_{3})}
 
 of nodes in a graph is a neighbor of a partition 
 
 
 
 (
 
 P
 
 0
 
 
 ,
 
 P
 
 1
 
 
 )
 
 
 {\displaystyle (P_{0},P_{1})}
 
 if 
 
 
 
 (
 
 P
 
 2
 
 
 ,
 
 P
 
 3
 
 
 )
 
 
 {\displaystyle (P_{2},P_{3})}
 
 can be obtained from 
 
 
 
 (
 
 P
 
 0
 
 
 ,
 
 P
 
 1
 
 
 )
 
 
 {\displaystyle (P_{0},P_{1})}
 
 by swapping one node 
 
 
 
 
 p
 
 0
 
 
 ∈
 
 P
 
 0
 
 
 
 
 {\displaystyle p_{0}\in P_{0}}
 
 with a node 
 
 
 
 
 p
 
 1
 
 
 ∈
 
 P
 
 1
 
 
 
 
 {\displaystyle p_{1}\in P_{1}}
 
.</li>
<li>Kernighan-Lin<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> - A partition 
 
 
 
 (
 
 P
 
 2
 
 
 ,
 
 P
 
 3
 
 
 )
 
 
 {\displaystyle (P_{2},P_{3})}
 
 is a neighbor of 
 
 
 
 (
 
 P
 
 0
 
 
 ,
 
 P
 
 1
 
 
 )
 
 
 {\displaystyle (P_{0},P_{1})}
 
 if 
 
 
 
 (
 
 P
 
 2
 
 
 ,
 
 P
 
 3
 
 
 )
 
 
 {\displaystyle (P_{2},P_{3})}
 
 can be obtained by a greedy sequence of swaps from nodes in 
 
 
 
 
 P
 
 0
 
 
 
 
 {\displaystyle P_{0}}
 
 with nodes in 
 
 
 
 
 P
 
 1
 
 
 
 
 {\displaystyle P_{1}}
 
. This means the two nodes 
 
 
 
 
 p
 
 0
 
 
 ∈
 
 P
 
 0
 
 
 
 
 {\displaystyle p_{0}\in P_{0}}
 
 and 
 
 
 
 
 p
 
 1
 
 
 ∈
 
 P
 
 1
 
 
 
 
 {\displaystyle p_{1}\in P_{1}}
 
 are swapped, where the partition 
 
 
 
 (
 (
 
 P
 
 0
 
 
 ∖
 
 p
 
 0
 
 
 )
 ∪
 p
 1
 ,
 (
 
 P
 
 1
 
 
 ∖
 
 p
 
 1
 
 
 )
 ∪
 
 p
 
 0
 
 
 )
 
 
 {\displaystyle ((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})}
 
 gains the highest possible weight, or loses the least possible weight. Note that no node is allowed to be swapped twice. This rule is based on the <a href="/facts/Kernighan%E2%80%93Lin_algorithm/oJ5F0dN5">Kernighan–Lin heuristic for graph partition</a>.</li>
<li>Fiduccia-Matheyses <a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> - This neighborhood is similar to the Kernighan-Lin neighborhood structure, it is a greedy sequence of swaps, except that each swap happens in two steps. First the 
 
 
 
 
 p
 
 0
 
 
 ∈
 
 P
 
 0
 
 
 
 
 {\displaystyle p_{0}\in P_{0}}
 
 with the most gain of cost, or the least loss of cost, is swapped to 
 
 
 
 
 P
 
 1
 
 
 
 
 {\displaystyle P_{1}}
 
, then the node 
 
 
 
 
 p
 
 1
 
 
 ∈
 
 P
 
 1
 
 
 
 
 {\displaystyle p_{1}\in P_{1}}
 
 with the most cost, or the least loss of cost is swapped to 
 
 
 
 
 P
 
 0
 
 
 
 
 {\displaystyle P_{0}}
 
 to balance the partitions again. Experiments have shown that Fiduccia-Mattheyses has a smaller run time in each iteration of the standard algorithm, though it sometimes finds an inferior local optimum.</li>
<li>FM-Swap<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> - This neighborhood structure is based on the Fiduccia-Mattheyses neighborhood structure. Each solution 
 
 
 
 s
 =
 (
 
 P
 
 0
 
 
 ,
 
 P
 
 1
 
 
 )
 
 
 {\displaystyle s=(P_{0},P_{1})}
 
 has only one neighbor, the partition obtained after the first swap of the Fiduccia-Mattheyses.</li></ul>
<h2 id="the-standard-algorithm">The standard Algorithm</h2>
Consider the following computational problem:
Given some instance 
 
 
 
 I
 
 
 {\displaystyle I}
 
 of a PLS problem 
 
 
 
 L
 
 
 {\displaystyle L}
 
, find a locally optimal solution 
 
 
 
 s
 ∈
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle s\in F_{L}(I)}
 
 such that 
 
 
 
 
 c
 
 L
 
 
 (
 I
 ,
 
 s
 ′
 
 )
 ≥
 
 c
 
 L
 
 
 (
 I
 ,
 s
 )
 
 
 {\displaystyle c_{L}(I,s')\geq c_{L}(I,s)}
 
 for all 
 
 
 
 
 s
 ′
 
 ∈
 N
 (
 I
 ,
 s
 )
 
 
 {\displaystyle s'\in N(I,s)}
 
.
Every local search problem can be solved using the following iterative improvement algorithm:<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<ol><li>Use 
 
 
 
 
 A
 
 L
 
 
 
 
 {\displaystyle A_{L}}
 
 to find an initial solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
</li>
<li>Use algorithm 
 
 
 
 
 C
 
 L
 
 
 
 
 {\displaystyle C_{L}}
 
 to find a better solution 
 
 
 
 
 s
 ′
 
 ∈
 N
 (
 I
 ,
 s
 )
 
 
 {\displaystyle s'\in N(I,s)}
 
. If such a solution exists, replace 
 
 
 
 s
 
 
 {\displaystyle s}
 
 by 
 
 
 
 
 s
 ′
 
 
 
 {\displaystyle s'}
 
 and repeat step 2, else return 
 
 
 
 s
 
 
 {\displaystyle s}
 
</li></ol>
Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem 
 
 
 
 L
 
 
 {\displaystyle L}
 
 can be solved exactly in polynomial time.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> It is not necessary always to use the standard algorithm, there may be a different, faster algorithm for a certain problem. For example a local search algorithm used for <a href="/facts/Linear_programming/GduXFQxT">Linear programming</a> is the <a href="/facts/Simplex_algorithm/9fndF6cq">Simplex algorithm</a>.
The run time of the standard algorithm is <a href="/facts/Pseudo-polynomial_time/7a35x5wN">pseudo-polynomial</a> in the number of different costs of a solution.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>
The space the standard algorithm needs is only polynomial. It only needs to save the current solution 
 
 
 
 s
 
 
 {\displaystyle s}
 
, which is polynomial bounded by definition.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>

<h2 id="reductions">Reductions</h2>
A <a href="/facts/Reduction_(complexity)/IVWF7a1c">Reduction</a> of one problem to another may be used to show that the second problem is at least as difficult as the first. In particular, a PLS-reduction is used to prove that a local search problem that lies in PLS is also PLS-complete, by reducing a PLS-complete Problem to the one that shall be proven to be PLS-complete.

<h3>PLS-reduction</h3>
A local search problem 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
 is PLS-reducible<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> to a local search problem 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
 if there are two polynomial time functions 
 
 
 
 f
 :
 
 D
 
 1
 
 
 →
 
 D
 
 2
 
 
 
 
 {\displaystyle f:D_{1}\rightarrow D_{2}}
 
 and 
 
 
 
 g
 :
 
 D
 
 1
 
 
 ×
 
 F
 
 2
 
 
 (
 f
 (
 
 I
 
 1
 
 
 )
 )
 →
 
 F
 
 1
 
 
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}
 
 such that:

<ul><li>if 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
 is an instance of 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
 , then 
 
 
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle f(I_{1})}
 
 is an instance of 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
</li>
<li>if 
 
 
 
 
 s
 
 2
 
 
 
 
 {\displaystyle s_{2}}
 
 is a solution for 
 
 
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle f(I_{1})}
 
 of 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
 , then 
 
 
 
 g
 (
 
 I
 
 1
 
 
 ,
 
 s
 
 2
 
 
 )
 
 
 {\displaystyle g(I_{1},s_{2})}
 
 is a solution for 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
 of 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
</li>
<li>if 
 
 
 
 
 s
 
 2
 
 
 
 
 {\displaystyle s_{2}}
 
 is a local optimum for instance 
 
 
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle f(I_{1})}
 
 of 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
 , then 
 
 
 
 g
 (
 
 I
 
 1
 
 
 ,
 
 s
 
 2
 
 
 )
 
 
 {\displaystyle g(I_{1},s_{2})}
 
 has to be a local optimum for instance 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
 of 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
</li></ul>
It is sufficient to only map the local optima of 
 
 
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle f(I_{1})}
 
 to the local optima of 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
, and to map all other solutions for example to the standard solution returned by 
 
 
 
 
 A
 
 1
 
 
 
 
 {\displaystyle A_{1}}
 
.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>
PLS-reductions are <a href="/facts/Transitive_relation/9r90y50r">transitive</a>.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>

<h3>Tight PLS-reduction</h3>
<h4>Definition Transition graph</h4>
The transition graph<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a> 
 
 
 
 
 T
 
 I
 
 
 
 
 {\displaystyle T_{I}}
 
 of an instance 
 
 
 
 I
 
 
 {\displaystyle I}
 
 of a problem 
 
 
 
 L
 
 
 {\displaystyle L}
 
 is a directed graph. The nodes represent all elements of the finite set of solutions 
 
 
 
 
 F
 
 L
 
 
 (
 I
 )
 
 
 {\displaystyle F_{L}(I)}
 
 and the edges point from one solution to the neighbor with strictly better cost. Therefore it is an acyclic graph. A sink, which is a node with no outgoing edges, is a local optimum.
The height of a vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 is the length of the shortest path from 
 
 
 
 v
 
 
 {\displaystyle v}
 
 to the nearest sink.
The height of the transition graph is the largest of the heights of all vertices, so it is the height of the largest shortest possible path from a node to its nearest sink.

<h4>Definition Tight PLS-reduction</h4>
A PLS-reduction 
 
 
 
 (
 f
 ,
 g
 )
 
 
 {\displaystyle (f,g)}
 
 from a local search problem 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
 to a local search problem 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
 is a
tight PLS-reduction<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a> if for any instance 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
 of 
 
 
 
 
 L
 
 1
 
 
 
 
 {\displaystyle L_{1}}
 
, a subset 
 
 
 
 R
 
 
 {\displaystyle R}
 
 of solutions
of instance 
 
 
 
 
 I
 
 2
 
 
 =
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle I_{2}=f(I_{1})}
 
 of 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L_{2}}
 
 can be chosen, so that the following properties are satisfied:

<ul><li>
 
 
 
 R
 
 
 {\displaystyle R}
 
 contains, among other solutions, all local optima of 
 
 
 
 
 I
 
 2
 
 
 
 
 {\displaystyle I_{2}}
 
</li>
<li>For every solution 
 
 
 
 p
 
 
 {\displaystyle p}
 
 of 
 
 
 
 
 I
 
 1
 
 
 
 
 {\displaystyle I_{1}}
 
 , a solution 
 
 
 
 q
 ∈
 R
 
 
 {\displaystyle q\in R}
 
 of 
 
 
 
 
 I
 
 2
 
 
 =
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle I_{2}=f(I_{1})}
 
 can be constructed in polynomial time, so that 
 
 
 
 g
 (
 
 I
 
 1
 
 
 ,
 q
 )
 =
 p
 
 
 {\displaystyle g(I_{1},q)=p}
 
</li>
<li>If the transition graph 
 
 
 
 
 T
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 
 
 {\displaystyle T_{f(I_{1})}}
 
 of 
 
 
 
 f
 (
 
 I
 
 1
 
 
 )
 
 
 {\displaystyle f(I_{1})}
 
 contains a direct path from 
 
 
 
 q
 
 
 {\displaystyle q}
 
 to 
 
 
 
 
 q
 
 0
 
 
 
 
 {\displaystyle q_{0}}
 
, and 
 
 
 
 q
 ,
 
 q
 
 0
 
 
 ∈
 R
 
 
 {\displaystyle q,q_{0}\in R}
 
, but all internal path vertices are outside 
 
 
 
 R
 
 
 {\displaystyle R}
 
, then for the corresponding solutions 
 
 
 
 p
 =
 g
 (
 
 I
 
 1
 
 
 ,
 q
 )
 
 
 {\displaystyle p=g(I_{1},q)}
 
 and 
 
 
 
 
 p
 
 0
 
 
 =
 g
 (
 
 I
 
 1
 
 
 ,
 
 q
 
 0
 
 
 )
 
 
 {\displaystyle p_{0}=g(I_{1},q_{0})}
 
 holds either 
 
 
 
 p
 =
 
 p
 
 0
 
 
 
 
 {\displaystyle p=p_{0}}
 
 or 
 
 
 
 
 T
 
 
 I
 
 1
 
 
 
 
 
 
 {\displaystyle T_{I_{1}}}
 
 contains an edge from 
 
 
 
 p
 
 
 {\displaystyle p}
 
 to 
 
 
 
 
 p
 
 0
 
 
 
 
 {\displaystyle p_{0}}
 
</li></ul>
<h2 id="relationship-to-other-complexity-classes">Relationship to other complexity classes</h2>
PLS lies between the functional versions of <a href="/facts/P_(complexity)/2TYvck4k">P</a> and <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>: <a href="/facts/FP_(complexity)/FSK2uwKz">FP</a> ⊆ PLS ⊆ <a href="/facts/FNP_(complexity)/m4MVkn3w">FNP</a>.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a>
PLS also is a subclass of <a href="/facts/TFNP/JwCmUwSV">TFNP</a>,<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a> that describes computational problems in which a solution is guaranteed to exist and can be recognized in polynomial time. For a problem in PLS, a solution is guaranteed to exist because the minimum-cost vertex of the entire graph is a valid solution, and the validity of a solution can be checked by computing its neighbors and comparing the costs of each one to another.
It is also proven that if a PLS problem is <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>, then NP = <a href="/facts/Co-NP/M67JgWNa">co-NP</a>.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a>

<h2 id="pls-completeness">PLS-completeness</h2>
<h3>Definition</h3>
A local search problem 
 
 
 
 L
 
 
 {\displaystyle L}
 
 is PLS-complete,<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> if

<ul><li>
 
 
 
 L
 
 
 {\displaystyle L}
 
 is in PLS</li>
<li>every problem in PLS can be PLS-reduced to 
 
 
 
 L
 
 
 {\displaystyle L}
 
</li></ul>
The optimization version of the <a href="/facts/Circuit_satisfiability_problem/LDkc2Yc0">circuit</a> problem under the Flip neighborhood structure has been shown to be a first PLS-complete problem.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a>

<h3>List of PLS-complete Problems</h3>
This is an incomplete list of some known problems that are PLS-complete. The problems here are the weighted versions; for example, Max-2SAT/Flip is weighted even though Max-2SAT ordinarily refers to the unweighted version.

Notation: Problem / Neighborhood structure

<ul><li><a href="/facts/Circuit_satisfiability_problem/LDkc2Yc0">Min/Max-circuit/Flip</a> has been proven to be the first PLS-complete problem.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a></li>
<li>Sink-of-<a href="/facts/Directed_acyclic_graph/k6zq1os9">DAG</a> is complete by definition.</li>
<li>Positive-not-all-equal-max-3Sat/Flip has been proven to be PLS-complete via a tight PLS-reduction from Min/Max-circuit/Flip to Positive-not-all-equal-max-3Sat/Flip. Note that Positive-not-all-equal-max-3Sat/Flip can be reduced from Max-Cut/Flip too.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a></li>
<li>Positive-not-all-equal-max-3Sat/Kernighan-Lin has been proven to be PLS-complete via a tight PLS-reduction from Min/Max-circuit/Flip to Positive-not-all-equal-max-3Sat/Kernighan-Lin.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a></li>
<li><a href="/facts/2-satisfiability/cUMH5x2y">Max-2Sat</a>/Flip has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-2Sat/Flip.<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a><a class="footnote-ref" id="fnref:39" href="#fn:39">39</a></li>
<li><a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Min-4Sat-B</a>/Flip has been proven to be PLS-complete via a tight PLS-reduction from Min-circuit/Flip to Min-4Sat-B/Flip.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a></li>
<li>Max-4Sat-B/Flip(or CNF-SAT) has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip to Max-4Sat-B/Flip.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a></li>
<li>Max-4Sat-(B=3)/Flip has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip to Max-4Sat-(B=3)/Flip.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a></li>
<li><a href="/facts/Graph_partition/MSQF0WyD">Max-Uniform-Graph-Partitioning</a>/Swap has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-Uniform-Graph-partitioning/Swap.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a></li>
<li><a href="/facts/Graph_partition/MSQF0WyD">Max-Uniform-Graph-Partitioning</a>/Fiduccia-Matheyses is stated to be PLS-complete without proof.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a></li>
<li><a href="/facts/Graph_partition/MSQF0WyD">Max-Uniform-Graph-Partitioning</a>/FM-Swap has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-Uniform-Graph-partitioning/FM-Swap.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a></li>
<li><a href="/facts/Graph_partition/MSQF0WyD">Max-Uniform-Graph-Partitioning</a>/Kernighan-Lin has been proven to be PLS-complete via a PLS-reduction from Min/Max-circuit/Flip to Max-Uniform-Graph-Partitioning/Kernighan-Lin.<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> There is also a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Kernighan-Lin to Max-Uniform-Graph-Partitioning/Kernighan-Lin.<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a></li>
<li><a href="/facts/Maximum_cut/9rulcdeW">Max-Cut</a>/Flip has been proven to be PLS-complete via a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Flip to Max-Cut/Flip.<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a><a class="footnote-ref" id="fnref:49" href="#fn:49">49</a></li>
<li><a href="/facts/Maximum_cut/9rulcdeW">Max-Cut</a>/Kernighan-Lin is claimed to be PLS-complete without proof.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a></li>
<li>Min-Independent-Dominating-Set-B/k-Flip has been proven to be PLS-complete via a tight PLS-reduction from Min-4Sat-B′/Flip to Min-Independent-Dominating-Set-B/k-Flip.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a></li>
<li><a href="/facts/Independent_set_(graph_theory)/ksu46kdz">Weighted-Independent-Set</a>/Change is claimed to be PLS-complete without proof.<a class="footnote-ref" id="fnref:52" href="#fn:52">52</a><a class="footnote-ref" id="fnref:53" href="#fn:53">53</a><a class="footnote-ref" id="fnref:54" href="#fn:54">54</a></li>
<li>Maximum-Weighted-Subgraph-with-property-P/Change is PLS-complete if property P = "has no edges", as it then equals Weighted-Independent-Set/Change. It has also been proven to be PLS-complete for a general hereditary, non-trivial property P via a tight PLS-reduction from Weighted-Independent-Set/Change to Maximum-Weighted-Subgraph-with-property-P/Change.<a class="footnote-ref" id="fnref:55" href="#fn:55">55</a></li>
<li><a href="/facts/Set_cover_problem/MVzyBYs1">Set-Cover</a>/k-change has been proven to be PLS-complete for each k ≥ 2 via a tight PLS-reduction from (3, 2, r)-Max-Constraint-Assignment/Change to Set-Cover/k-change.<a class="footnote-ref" id="fnref:56" href="#fn:56">56</a></li>
<li><a href="/facts/Travelling_salesman_problem/2WEKVLnV">Metric-TSP</a>/k-Change has been proven to be PLS-complete via a PLS-reduction from Max-4Sat-B/Flip to Metric-TSP/k-Change.<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a></li>
<li><a href="/facts/Travelling_salesman_problem/2WEKVLnV">Metric-TSP</a>/Lin-Kernighan has been proven to be PLS-complete via a tight PLS-reduction from Max-2Sat/Flip to Metric-TSP/Lin-Kernighan.<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a></li>
<li><a href="/facts/Job_shop_scheduling/1JjAvD3m">Local-Multi-Processor-Scheduling</a>/k-change has been proven to be PLS-complete via a tight PLS-reduction from Weighted-3Dimensional-Matching/(p, q)-Swap to Local-Multi-Processor-scheduling/(2p+q)-change, where (2p + q) ≥ 8.<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a></li>
<li>Selfish-Multi-Processor-Scheduling/k-change-with-property-t has been proven to be PLS-complete via a tight PLS-reduction from Weighted-3Dimensional-Matching/(p, q)-Swap to (2p+q)-Selfish-Multi-Processor-Scheduling/k-change-with-property-t, where (2p + q) ≥ 8.<a class="footnote-ref" id="fnref:60" href="#fn:60">60</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in a <a href="/facts/Congestion_game/Q3qGGp7u">General-Congestion-Game</a>/Change has been proven PLS-complete via a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Flip to General-Congestion-Game/Change.<a class="footnote-ref" id="fnref:61" href="#fn:61">61</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in a Symmetric General-Congestion-Game/Change has been proven to be PLS-complete via a tight PLS-reduction from an asymmetric General-Congestion-Game/Change to symmetric General-Congestion-Game/Change.<a class="footnote-ref" id="fnref:62" href="#fn:62">62</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in an Asymmetric Directed-Network-Congestion-Games/Change has been proven to be PLS-complete via a tight reduction from Positive-not-all-equal-max-3Sat/Flip to Directed-Network-Congestion-Games/Change <a class="footnote-ref" id="fnref:63" href="#fn:63">63</a> and also via a tight PLS-reduction from 2-Threshold-Games/Change to Directed-Network-Congestion-Games/Change.<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in an Asymmetric Undirected-Network-Congestion-Games/Change has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games/Change to Asymmetric Undirected-Network-Congestion-Games/Change.<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in a Symmetric Distance-Bounded-Network-Congestion-Games has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games to Symmetric Distance-Bounded-Network-Congestion-Games.<a class="footnote-ref" id="fnref:66" href="#fn:66">66</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in a 2-Threshold-Game/Change has been proven to be PLS-complete via a tight reduction from Max-Cut/Flip to 2-Threshold-Game/Change.<a class="footnote-ref" id="fnref:67" href="#fn:67">67</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in Market-Sharing-Game/Change with polynomial bounded costs has been proven to be PLS-complete via a tight PLS-reduction from 2-Threshold-Games/Change to Market-Sharing-Game/Change.<a class="footnote-ref" id="fnref:68" href="#fn:68">68</a></li>
<li>Finding a <a href="/facts/Nash_equilibrium/l74xzIHd">pure Nash Equilibrium</a> in an Overlay-Network-Design/Change has been proven to be PLS-complete via a reduction from 2-Threshold-Games/Change to Overlay-Network-Design/Change. Analogously to the proof of asymmetric Directed-Network-Congestion-Game/Change, the reduction is tight.<a class="footnote-ref" id="fnref:69" href="#fn:69">69</a></li>
<li><a href="/facts/Integer_programming/MDaaadoA">Min-0-1-Integer Programming</a>/k-Flip has been proven to be PLS-complete via a tight PLS-reduction from Min-4Sat-B′/Flip to Min-0-1-Integer Programming/k-Flip.<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a></li>
<li><a href="/facts/Integer_programming/MDaaadoA">Max-0-1-Integer Programming</a>/k-Flip is claimed to be PLS-complete because of PLS-reduction to Max-0-1-Integer Programming/k-Flip, but the proof is left out.<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a></li>
<li><a href="/facts/Constraint_satisfaction_problem/oKCeIV2L">(p, q, r)-Max-Constraint-Assignment</a>
<ul><li>(3, 2, 3)-Max-Constraint-Assignment-3-partite/Change has been proven to be PLS-complete via a tight PLS-reduction from Circuit/Flip to (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change.<a class="footnote-ref" id="fnref:72" href="#fn:72">72</a></li>
<li>(2, 3, 6)-Max-Constraint-Assignment-2-partite/Change has been proven to be PLS-complete via a tight PLS-reduction from Circuit/Flip to (2, 3, 6)-Max-Constraint-Assignment-2-partite/Change.<a class="footnote-ref" id="fnref:73" href="#fn:73">73</a></li>
<li>(6, 2, 2)-Max-Constraint-Assignment/Change has been proven to be PLS-complete via a tight reduction from Circuit/Flip to (6,2, 2)-Max-Constraint-Assignment/Change.<a class="footnote-ref" id="fnref:74" href="#fn:74">74</a></li>
<li>(4, 3, 3)-Max-Constraint-Assignment/Change equals Max-4Sat-(B=3)/Flip and has been proven to be PLS-complete via a PLS-reduction from Max-circuit/Flip.<a class="footnote-ref" id="fnref:75" href="#fn:75">75</a> It is claimed that the reduction can be extended so tightness is obtained.<a class="footnote-ref" id="fnref:76" href="#fn:76">76</a></li></ul></li>
<li>Nearest-Colorful-Polytope/Change has been proven to be PLS-complete via a PLS-reduction from Max-2Sat/Flip to Nearest-Colorful-Polytope/Change.<a class="footnote-ref" id="fnref:77" href="#fn:77">77</a></li>
<li>Stable-Configuration/Flip in a <a href="/facts/Hopfield_network/xUBr6rpm">Hopfield network</a> has been proven to be PLS-complete if the thresholds are 0 and the weights are negative via a tight PLS-reduction from Max-Cut/Flip to Stable-Configuration/Flip.<a class="footnote-ref" id="fnref:78" href="#fn:78">78</a><a class="footnote-ref" id="fnref:79" href="#fn:79">79</a><a class="footnote-ref" id="fnref:80" href="#fn:80">80</a></li>
<li><a href="/facts/3-dimensional_matching/WFr6DxFj">Weighted-3Dimensional-Matching</a>/(p, q)-Swap has been proven to be PLS-complete for p ≥9 and q ≥ 15 via a tight PLS-reduction from (2, 3, r)-Max-Constraint-Assignment-2-partite/Change to Weighted-3Dimensional-Matching/(p, q)-Swap.<a class="footnote-ref" id="fnref:81" href="#fn:81">81</a></li>
<li>The problem Real-Local-Opt (finding the ɛ local optimum of a <a href="/facts/Lipschitz_continuity/Hw20EPEU">λ-Lipschitz continuous</a> objective function 
 
 
 
 V
 :
 [
 0
 ,
 1
 
 ]
 
 3
 
 
 →
 [
 0
 ,
 1
 ]
 
 
 {\displaystyle V:[0,1]^{3}\rightarrow [0,1]}
 
 and a neighborhood function 
 
 
 
 S
 :
 [
 0
 ,
 1
 
 ]
 
 3
 
 
 →
 [
 0
 ,
 1
 
 ]
 
 3
 
 
 
 
 {\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}
 
) is PLS-complete.<a class="footnote-ref" id="fnref:82" href="#fn:82">82</a></li>
<li>Finding a local fitness peak in a biological <a href="/facts/Fitness_landscapes/XrqwdjWR">fitness landscapes</a> specified by the <a href="/facts/NK_model/Ka7cn72N">NK-model</a>/Point-mutation with K ≥ 2 was proven to be PLS-complete via a tight PLS-reduction from Max-2SAT/Flip.<a class="footnote-ref" id="fnref:83" href="#fn:83">83</a></li></ul>
<h2 id="relations-to-other-complexity-classes">Relations to other complexity classes</h2>
Fearnley, Goldberg, Hollender and Savani<a class="footnote-ref" id="fnref:84" href="#fn:84">84</a> proved that a complexity class called CLS is equal to the intersection of <a href="/facts/PPAD_(complexity)/EKaF3W9c">PPAD</a> and PLS.

<h2 id="further-reading">Further reading</h2>
<ul><li>Equilibria, fixed points, and complexity classes: a survey.<a class="footnote-ref" id="fnref:85" href="#fn:85">85</a></li></ul>

<ul><li><a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Yannakakis, Mihalis</a> (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.371.5034">10.1.1.371.5034</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.cosrev.2009.03.004">10.1016/j.cosrev.2009.03.004</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Mulzer, Wolfgang; Stein, Yannik (14 March 2018). "Computational Aspects of the Colorful Caratheodory Theorem". Discrete & Computational Geometry. 60 (3): 720–755. arXiv:1412.3347. Bibcode:2014arXiv1412.3347M. doi:10.1007/s00454-018-9979-y. S2CID 254024141. <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Borzechowski, Michaela. "The complexity class Polynomial Local Search (PLS) and PLS-complete problems" (PDF). <a href="http://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/download/Borzechowski16.pdf" target="_blank">http://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/download/Borzechowski16.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "Multiprocessor Scheduling is PLS-Complete". System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on: 1–10. <a href="https://www.researchgate.net/publication/224373381" target="_blank">https://www.researchgate.net/publication/224373381</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Daskalakis, Constantinos; Papadimitriou, Christos (23 January 2011). "Continuous Local Search". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms: 790–804. doi:10.1137/1.9781611973082.62. ISBN 978-0-89871-993-2. S2CID 2056144. <a href="978-0-89871-993-2" target="_blank">978-0-89871-993-2</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99. <a href="https://www.researchgate.net/publication/221209488" target="_blank">https://www.researchgate.net/publication/221209488</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Fiduccia, C. M.; Mattheyses, R. M. (1982). "A Linear-time Heuristic for Improving Network Partitions". Proceedings of the 19th Design Automation Conference: 175–181. ISBN 9780897910200. <a href="9780897910200" target="_blank">9780897910200</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Angel, Eric; Christopoulos, Petros; Zissimopoulos, Vassilis (2014). Paradigms of Combinatorial Optimization: Problems and New Approaches - Local Search: Complexity and Approximation (2 ed.). John Wiley & Sons, Inc., Hoboken. pp. 435–471. doi:10.1002/9781119005353.ch14. ISBN 9781119005353. <a href="9781119005353" target="_blank">9781119005353</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Megiddo, Nimrod; Papadimitriou, Christos H (1991). "On total functions, existence theorems and computational complexity". Theoretical Computer Science. 81 (2): 317–324. CiteSeerX 10.1.1.75.4797. doi:10.1016/0304-3975(91)90200-L. <a href="https://doi.org/10.1016%2F0304-3975%2891%2990200-L" target="_blank">https://doi.org/10.1016%2F0304-3975%2891%2990200-L</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99. <a href="https://www.researchgate.net/publication/221209488" target="_blank">https://www.researchgate.net/publication/221209488</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Krentel, M. (1 August 1990). "On Finding and Verifying Locally Optimal Solutions". SIAM Journal on Computing. 19 (4): 742–749. doi:10.1137/0219052. ISSN 0097-5397. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Krentel, Mark W. (1989). "Structure in locally optimal solutions". 30th Annual Symposium on Foundations of Computer Science. pp. 216–221. doi:10.1109/SFCS.1989.63481. ISBN 0-8186-1982-1. S2CID 32686790. <a href="0-8186-1982-1" target="_blank">0-8186-1982-1</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99. <a href="https://www.researchgate.net/publication/221209488" target="_blank">https://www.researchgate.net/publication/221209488</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Johnson, David S; Papadimitriou, Christos H; Yannakakis, Mihalis (1988). "How easy is local search?". Journal of Computer and System Sciences. 37 (1): 79–100. doi:10.1016/0022-0000(88)90046-3. <a href="https://doi.org/10.1016%2F0022-0000%2888%2990046-3" target="_blank">https://doi.org/10.1016%2F0022-0000%2888%2990046-3</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Michiels, Wil; Aarts, Emile; Korst, Jan (2010). Theoretical aspects of local search. Springer Science & Business Media. ISBN 9783642071485. <a href="9783642071485" target="_blank">9783642071485</a> <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Shimozono, Shinichi (1997). "Finding optimal subgraphs by local search". Theoretical Computer Science. 172 (1): 265–271. doi:10.1016/S0304-3975(96)00135-1. <a href="https://doi.org/10.1016%2FS0304-3975%2896%2900135-1" target="_blank">https://doi.org/10.1016%2FS0304-3975%2896%2900135-1</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">Dumrauf, Dominic; Süß, Tim (2010). "On the Complexity of Local Search for Weighted Standard Set Problems". CiE 2010: Programs, Proofs, Processes. Lecture Notes in Computer Science. Vol. 6158. Springer, Berlin, Heidelberg. pp. 132–140. CiteSeerX 10.1.1.762.6801. doi:10.1007/978-3-642-13962-8_15. ISBN 978-3-642-13961-1. S2CID 14099014. <a href="978-3-642-13961-1" target="_blank">978-3-642-13961-1</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">Krentel, Mark W. (1989). "Structure in locally optimal solutions". 30th Annual Symposium on Foundations of Computer Science. pp. 216–221. doi:10.1109/SFCS.1989.63481. ISBN 0-8186-1982-1. S2CID 32686790. <a href="0-8186-1982-1" target="_blank">0-8186-1982-1</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Papadimitriou, C.H.; Schäffer, A. A.; Yannakakis, M. (1990). "On the complexity of local search". Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. pp. 438–445. doi:10.1145/100216.100274. ISBN 0897913612. S2CID 16877206. <a href="0897913612" target="_blank">0897913612</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "Multiprocessor Scheduling is PLS-Complete". System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on: 1–10. <a href="https://www.researchgate.net/publication/224373381" target="_blank">https://www.researchgate.net/publication/224373381</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "Multiprocessor Scheduling is PLS-Complete". System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on: 1–10. <a href="https://www.researchgate.net/publication/224373381" target="_blank">https://www.researchgate.net/publication/224373381</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. ACM. pp. 604–612. CiteSeerX 10.1.1.3.7861. doi:10.1145/1007352.1007445. ISBN 978-1581138528. S2CID 1037326. <a href="978-1581138528" target="_blank">978-1581138528</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. ACM. pp. 604–612. CiteSeerX 10.1.1.3.7861. doi:10.1145/1007352.1007445. ISBN 978-1581138528. S2CID 1037326. <a href="978-1581138528" target="_blank">978-1581138528</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. ACM. pp. 604–612. CiteSeerX 10.1.1.3.7861. doi:10.1145/1007352.1007445. ISBN 978-1581138528. S2CID 1037326. <a href="978-1581138528" target="_blank">978-1581138528</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913. doi:10.1145/1455248.1455249. ISSN 0004-5411. S2CID 3070710. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913. doi:10.1145/1455248.1455249. ISSN 0004-5411. S2CID 3070710. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Yang, Yichen; Jia, Kai; Rinard, Martin (2022). "On the Impact of Player Capability on Congestion Games". Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 13584. pp. 311–328. arXiv:2205.09905. doi:10.1007/978-3-031-15714-1_18. ISBN 978-3-031-15713-4. <a href="978-3-031-15713-4" target="_blank">978-3-031-15713-4</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913. doi:10.1145/1455248.1455249. ISSN 0004-5411. S2CID 3070710. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913. doi:10.1145/1455248.1455249. ISSN 0004-5411. S2CID 3070710. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2008). "On the Impact of Combinatorial Structure on Congestion Games". J. ACM. 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913. doi:10.1145/1455248.1455249. ISSN 0004-5411. S2CID 3070710. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99. <a href="https://www.researchgate.net/publication/221209488" target="_blank">https://www.researchgate.net/publication/221209488</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Klauck, Hartmut (1996). "On the hardness of global and local approximation". Proceedings of the 5th Scandinavian Workshop on Algorithm Theory: 88–99. <a href="https://www.researchgate.net/publication/221209488" target="_blank">https://www.researchgate.net/publication/221209488</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
<li id="fn:72">Dumrauf, Dominic; Monien, Burkhard (2013). "On the PLS-complexity of Maximum Constraint Assignment". Theor. Comput. Sci. 469: 24–52. doi:10.1016/j.tcs.2012.10.044. ISSN 0304-3975. <a href="https://doi.org/10.1016%2Fj.tcs.2012.10.044" target="_blank">https://doi.org/10.1016%2Fj.tcs.2012.10.044</a> <a href="#fnref:72" class="footnote-back-ref">↩</a></li>
<li id="fn:73">Dumrauf, Dominic; Monien, Burkhard (2013). "On the PLS-complexity of Maximum Constraint Assignment". Theor. Comput. Sci. 469: 24–52. doi:10.1016/j.tcs.2012.10.044. ISSN 0304-3975. <a href="https://doi.org/10.1016%2Fj.tcs.2012.10.044" target="_blank">https://doi.org/10.1016%2Fj.tcs.2012.10.044</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></li>
<li id="fn:74">Dumrauf, Dominic; Monien, Burkhard (2013). "On the PLS-complexity of Maximum Constraint Assignment". Theor. Comput. Sci. 469: 24–52. doi:10.1016/j.tcs.2012.10.044. ISSN 0304-3975. <a href="https://doi.org/10.1016%2Fj.tcs.2012.10.044" target="_blank">https://doi.org/10.1016%2Fj.tcs.2012.10.044</a> <a href="#fnref:74" class="footnote-back-ref">↩</a></li>
<li id="fn:75">Krentel, Mark W. (1989). "Structure in locally optimal solutions". 30th Annual Symposium on Foundations of Computer Science. pp. 216–221. doi:10.1109/SFCS.1989.63481. ISBN 0-8186-1982-1. S2CID 32686790. <a href="0-8186-1982-1" target="_blank">0-8186-1982-1</a> <a href="#fnref:75" class="footnote-back-ref">↩</a></li>
<li id="fn:76">Dumrauf, Dominic; Monien, Burkhard (2013). "On the PLS-complexity of Maximum Constraint Assignment". Theor. Comput. Sci. 469: 24–52. doi:10.1016/j.tcs.2012.10.044. ISSN 0304-3975. <a href="https://doi.org/10.1016%2Fj.tcs.2012.10.044" target="_blank">https://doi.org/10.1016%2Fj.tcs.2012.10.044</a> <a href="#fnref:76" class="footnote-back-ref">↩</a></li>
<li id="fn:77">Mulzer, Wolfgang; Stein, Yannik (14 March 2018). "Computational Aspects of the Colorful Caratheodory Theorem". Discrete & Computational Geometry. 60 (3): 720–755. arXiv:1412.3347. Bibcode:2014arXiv1412.3347M. doi:10.1007/s00454-018-9979-y. S2CID 254024141. <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:77" class="footnote-back-ref">↩</a></li>
<li id="fn:78">Yannakakis, Mihalis (2003). Local search in combinatorial optimization - Computational complexity. Princeton University Press. pp. 19–55. ISBN 9780691115221. <a href="9780691115221" target="_blank">9780691115221</a> <a href="#fnref:78" class="footnote-back-ref">↩</a></li>
<li id="fn:79">Schäffer, Alejandro A.; Yannakakis, Mihalis (February 1991). "Simple Local Search Problems that are Hard to Solve". SIAM Journal on Computing. 20 (1): 56–87. doi:10.1137/0220004. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:79" class="footnote-back-ref">↩</a></li>
<li id="fn:80">Papadimitriou, C.H.; Schäffer, A. A.; Yannakakis, M. (1990). "On the complexity of local search". Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. pp. 438–445. doi:10.1145/100216.100274. ISBN 0897913612. S2CID 16877206. <a href="0897913612" target="_blank">0897913612</a> <a href="#fnref:80" class="footnote-back-ref">↩</a></li>
<li id="fn:81">Dumrauf, Dominic; Monien, Burkhard; Tiemann, Karsten (2009). "Multiprocessor Scheduling is PLS-Complete". System Sciences, 2009. HICSS'09. 42nd Hawaii International Conference on: 1–10. <a href="https://www.researchgate.net/publication/224373381" target="_blank">https://www.researchgate.net/publication/224373381</a> <a href="#fnref:81" class="footnote-back-ref">↩</a></li>
<li id="fn:82">Daskalakis, Constantinos; Papadimitriou, Christos (23 January 2011). "Continuous Local Search". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms: 790–804. doi:10.1137/1.9781611973082.62. ISBN 978-0-89871-993-2. S2CID 2056144. <a href="978-0-89871-993-2" target="_blank">978-0-89871-993-2</a> <a href="#fnref:82" class="footnote-back-ref">↩</a></li>
<li id="fn:83">Kaznatcheev, Artem (2019). "Computational Complexity as an Ultimate Constraint on Evolution". Genetics. 212 (1): 245–265. doi:10.1534/genetics.119.302000. PMC 6499524. PMID 30833289. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6499524" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6499524</a> <a href="#fnref:83" class="footnote-back-ref">↩</a></li>
<li id="fn:84">Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv:2011.01929. doi:10.1145/3568163. ISSN 0004-5411. S2CID 263706261. <a href="https://doi.org/10.1145/3568163" target="_blank">https://doi.org/10.1145/3568163</a> <a href="#fnref:84" class="footnote-back-ref">↩</a></li>
<li id="fn:85">Yannakakis, Mihalis (2009-05-01). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. arXiv:0802.2831. doi:10.1016/j.cosrev.2009.03.004. ISSN 1574-0137. <a href="https://www.sciencedirect.com/science/article/pii/S1574013709000161" target="_blank">https://www.sciencedirect.com/science/article/pii/S1574013709000161</a> <a href="#fnref:85" class="footnote-back-ref">↩</a></li>
</ol>

PLS (complexity) open-in-new

PLS (complexity)