PLS (complexity)

Consider the following instance ${\displaystyle I}$ of the Max-2Sat Problem: ${\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 ${\displaystyle s}$ for that instance is a bit string that assigns every ${\displaystyle x_{i}}$ the value 0 or 1. In this case, a solution consists of 3 bits, for example ${\displaystyle s=000}$, which stands for the assignment of ${\displaystyle x_{1}}$ to ${\displaystyle x_{3}}$ with the value 0. The set of solutions ${\displaystyle F_{L}(I)}$ is the set of all possible assignments of ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$ and ${\displaystyle x_{3}}$.

The cost of each solution is the number of satisfied clauses, so ${\displaystyle c_{L}(I,s=000)=2}$ because the second and third clause are satisfied.

The Flip-neighbor of a solution ${\displaystyle s}$ is reached by flipping one bit of the bit string ${\displaystyle s}$, so the neighbors of ${\displaystyle s}$ are ${\displaystyle N(I,000)=\{100,010,001\}}$ with the following costs:

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

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

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

There are no neighbors with better costs than ${\displaystyle s}$, if we are looking for a solution with maximum cost. Even though ${\displaystyle s}$ is not a global optimum (which for example would be a solution ${\displaystyle s'=111}$ that satisfies all clauses and has ${\displaystyle c_{L}(I,s')=3}$), ${\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:

• It is possible to find a solution to an instance in polynomial time, for example by setting all bits to 0.
• 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.
• It is possible to find all neighbors of a solution in polynomial time, by taking the set of solutions that differ from ${\displaystyle s}$ in exactly one bit.

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).

The class PLS is the class containing all problems that can be reduced in polynomial time to the problem Sink-of-DAG[7] (also called Local-Opt [8]): Given two integers ${\displaystyle n}$ and ${\displaystyle m}$ and two Boolean circuits ${\displaystyle S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ such that ${\displaystyle S(0^{n})\neq 0^{n}}$ and ${\displaystyle V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}}$, find a vertex ${\displaystyle x\in \{0,1\}^{n}}$ such that ${\displaystyle S(x)\neq x}$ and either ${\displaystyle S(S(x))=S(x)}$ or ${\displaystyle V(S(x))\leq V(x)}$.

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

• Flip[2] - The neighborhood of a solution ${\displaystyle s=x_{1},...,x_{n}}$ can be achieved by negating (flipping) one arbitrary input bit ${\displaystyle x_{i}}$. So one solution ${\displaystyle s}$ and all its neighbors ${\displaystyle r\in N(I,s)}$ have Hamming distance one: ${\displaystyle H(s,r)=1}$.
• Kernighan-Lin[2][6] - A solution ${\displaystyle r}$ is a neighbor of solution ${\displaystyle s}$ if ${\displaystyle r}$ can be obtained from ${\displaystyle s}$ by a sequence of greedy flips, where no bit is flipped twice. This means, starting with ${\displaystyle s}$, the Flip-neighbor ${\displaystyle s_{1}}$ of ${\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 ${\displaystyle s_{1}}$ , and so on, until ${\displaystyle s_{i}}$ is a solution where every bit of ${\displaystyle s}$ is negated. Note that it is not allowed to flip a bit back, if it once has been flipped.
• k-Flip[9] - A solution ${\displaystyle r}$ is a neighbor of solution ${\displaystyle s}$ if the Hamming distance ${\displaystyle H}$ between ${\displaystyle s}$ and ${\displaystyle r}$ is at most ${\displaystyle k}$, so ${\displaystyle H(s,r)\leq k}$.

Example neighborhood structures for problems on graphs:

• Swap[10] - A partition ${\displaystyle (P_{2},P_{3})}$ of nodes in a graph is a neighbor of a partition ${\displaystyle (P_{0},P_{1})}$ if ${\displaystyle (P_{2},P_{3})}$ can be obtained from ${\displaystyle (P_{0},P_{1})}$ by swapping one node ${\displaystyle p_{0}\in P_{0}}$ with a node ${\displaystyle p_{1}\in P_{1}}$.
• Kernighan-Lin[1][2] - A partition ${\displaystyle (P_{2},P_{3})}$ is a neighbor of ${\displaystyle (P_{0},P_{1})}$ if ${\displaystyle (P_{2},P_{3})}$ can be obtained by a greedy sequence of swaps from nodes in ${\displaystyle P_{0}}$ with nodes in ${\displaystyle P_{1}}$. This means the two nodes ${\displaystyle p_{0}\in P_{0}}$ and ${\displaystyle p_{1}\in P_{1}}$ are swapped, where the partition ${\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.
• Fiduccia-Matheyses [1][11] - 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 ${\displaystyle p_{0}\in P_{0}}$ with the most gain of cost, or the least loss of cost, is swapped to ${\displaystyle P_{1}}$, then the node ${\displaystyle p_{1}\in P_{1}}$ with the most cost, or the least loss of cost is swapped to ${\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.
• FM-Swap[1] - This neighborhood structure is based on the Fiduccia-Mattheyses neighborhood structure. Each solution ${\displaystyle s=(P_{0},P_{1})}$ has only one neighbor, the partition obtained after the first swap of the Fiduccia-Mattheyses.

A local search problem ${\displaystyle L_{1}}$ is PLS-reducible[2] to a local search problem ${\displaystyle L_{2}}$ if there are two polynomial time functions ${\displaystyle f:D_{1}\rightarrow D_{2}}$ and ${\displaystyle g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})}$ such that:

• if ${\displaystyle I_{1}}$ is an instance of ${\displaystyle L_{1}}$ , then ${\displaystyle f(I_{1})}$ is an instance of ${\displaystyle L_{2}}$
• if ${\displaystyle s_{2}}$ is a solution for ${\displaystyle f(I_{1})}$ of ${\displaystyle L_{2}}$ , then ${\displaystyle g(I_{1},s_{2})}$ is a solution for ${\displaystyle I_{1}}$ of ${\displaystyle L_{1}}$
• if ${\displaystyle s_{2}}$ is a local optimum for instance ${\displaystyle f(I_{1})}$ of ${\displaystyle L_{2}}$ , then ${\displaystyle g(I_{1},s_{2})}$ has to be a local optimum for instance ${\displaystyle I_{1}}$ of ${\displaystyle L_{1}}$

It is sufficient to only map the local optima of ${\displaystyle f(I_{1})}$ to the local optima of ${\displaystyle I_{1}}$, and to map all other solutions for example to the standard solution returned by ${\displaystyle A_{1}}$.[6]

PLS-reductions are transitive.[2]

The transition graph[6] ${\displaystyle T_{I}}$ of an instance ${\displaystyle I}$ of a problem ${\displaystyle L}$ is a directed graph. The nodes represent all elements of the finite set of solutions ${\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 ${\displaystyle v}$ is the length of the shortest path from ${\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.

A PLS-reduction ${\displaystyle (f,g)}$ from a local search problem ${\displaystyle L_{1}}$ to a local search problem ${\displaystyle L_{2}}$ is a tight PLS-reduction[10] if for any instance ${\displaystyle I_{1}}$ of ${\displaystyle L_{1}}$, a subset ${\displaystyle R}$ of solutions of instance ${\displaystyle I_{2}=f(I_{1})}$ of ${\displaystyle L_{2}}$ can be chosen, so that the following properties are satisfied:

• ${\displaystyle R}$ contains, among other solutions, all local optima of ${\displaystyle I_{2}}$
• For every solution ${\displaystyle p}$ of ${\displaystyle I_{1}}$ , a solution ${\displaystyle q\in R}$ of ${\displaystyle I_{2}=f(I_{1})}$ can be constructed in polynomial time, so that ${\displaystyle g(I_{1},q)=p}$
• If the transition graph ${\displaystyle T_{f(I_{1})}}$ of ${\displaystyle f(I_{1})}$ contains a direct path from ${\displaystyle q}$ to ${\displaystyle q_{0}}$, and ${\displaystyle q,q_{0}\in R}$, but all internal path vertices are outside ${\displaystyle R}$, then for the corresponding solutions ${\displaystyle p=g(I_{1},q)}$ and ${\displaystyle p_{0}=g(I_{1},q_{0})}$ holds either ${\displaystyle p=p_{0}}$ or ${\displaystyle T_{I_{1}}}$ contains an edge from ${\displaystyle p}$ to ${\displaystyle p_{0}}$

A local search problem ${\displaystyle L}$ is PLS-complete,[2] if

• ${\displaystyle L}$ is in PLS
• every problem in PLS can be PLS-reduced to ${\displaystyle L}$

The optimization version of the circuit problem under the Flip neighborhood structure has been shown to be a first PLS-complete problem.[2]

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.

Overview of PLS-complete problems and how they are reduced to each other. Syntax: Optimization-Problem/Neighborhood structure. Dotted arrow: PLS-reduction from a problem ${\displaystyle L}$ to a problem ${\displaystyle Q:L\leftarrow Q}$. Black arrow: Tight PLS-reduction.[4]

Notation: Problem / Neighborhood structure

• Min/Max-circuit/Flip has been proven to be the first PLS-complete problem.[2]
• Sink-of-DAG is complete by definition.
• 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.[10]
• 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.[1]
• Max-2Sat/Flip has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-2Sat/Flip.[1][10]
• Min-4Sat-B/Flip has been proven to be PLS-complete via a tight PLS-reduction from Min-circuit/Flip to Min-4Sat-B/Flip.[9]
• 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.[14]
• 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.[15]
• Max-Uniform-Graph-Partitioning/Swap has been proven to be PLS-complete via a tight PLS-reduction from Max-Cut/Flip to Max-Uniform-Graph-partitioning/Swap.[10]
• Max-Uniform-Graph-Partitioning/Fiduccia-Matheyses is stated to be PLS-complete without proof.[1]
• Max-Uniform-Graph-Partitioning/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.[10]
• Max-Uniform-Graph-Partitioning/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.[2] There is also a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Kernighan-Lin to Max-Uniform-Graph-Partitioning/Kernighan-Lin.[1]
• Max-Cut/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.[1][10]
• Max-Cut/Kernighan-Lin is claimed to be PLS-complete without proof.[6]
• 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.[9]
• Weighted-Independent-Set/Change is claimed to be PLS-complete without proof.[2][10][6]
• 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.[16]
• Set-Cover/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.[17]
• Metric-TSP/k-Change has been proven to be PLS-complete via a PLS-reduction from Max-4Sat-B/Flip to Metric-TSP/k-Change.[15]
• Metric-TSP/Lin-Kernighan has been proven to be PLS-complete via a tight PLS-reduction from Max-2Sat/Flip to Metric-TSP/Lin-Kernighan.[18]
• Local-Multi-Processor-Scheduling/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.[5]
• 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.[5]
• Finding a pure Nash Equilibrium in a General-Congestion-Game/Change has been proven PLS-complete via a tight PLS-reduction from Positive-not-all-equal-max-3Sat/Flip to General-Congestion-Game/Change.[19]
• Finding a pure Nash Equilibrium 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.[19]
• Finding a pure Nash Equilibrium 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 [19] and also via a tight PLS-reduction from 2-Threshold-Games/Change to Directed-Network-Congestion-Games/Change.[20]
• Finding a pure Nash Equilibrium 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.[20]
• Finding a pure Nash Equilibrium 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.[21]
• Finding a pure Nash Equilibrium 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.[20]
• Finding a pure Nash Equilibrium 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.[20]
• Finding a pure Nash Equilibrium 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.[20]
• Min-0-1-Integer Programming/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.[9]
• Max-0-1-Integer Programming/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.[9]
• (p, q, r)-Max-Constraint-Assignment
  • (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.[22]
  • (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.[22]
  • (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.[22]
  • (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.[15] It is claimed that the reduction can be extended so tightness is obtained.[22]
• Nearest-Colorful-Polytope/Change has been proven to be PLS-complete via a PLS-reduction from Max-2Sat/Flip to Nearest-Colorful-Polytope/Change.[3]
• Stable-Configuration/Flip in a Hopfield network 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.[1][10][18]
• Weighted-3Dimensional-Matching/(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.[5]
• The problem Real-Local-Opt (finding the ɛ local optimum of a λ-Lipschitz continuous objective function ${\displaystyle V:[0,1]^{3}\rightarrow [0,1]}$ and a neighborhood function ${\displaystyle S:[0,1]^{3}\rightarrow [0,1]^{3}}$) is PLS-complete.[8]
• Finding a local fitness peak in a biological fitness landscapes specified by the NK-model/Point-mutation with K ≥ 2 was proven to be PLS-complete via a tight PLS-reduction from Max-2SAT/Flip.[23]