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.

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[7] - 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[8] - 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][9] - 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-reducable[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[8] 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 incompete list of some known problems that are PLS-complete.

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]
• 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.[8]
• 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][8]
• 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.[7]
• 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.[12]
• 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.[13]
• 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.[8]
• 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.[8]
• 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][8]
• 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.[7]
• Weighted-Independent-Set/Change is claimed to be PLS-complete without proof.[2][8][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.[14]
• 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.[15]
• 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.[13]
• 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.[16]
• 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 the 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.[17]
• Finding the 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.[17]
• Finding a pure 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 [17] and also via a tight PLS-reduction from 2-Threshold-Games/Change to Directed-Network-Congestion-Games/Change.[18]
• Finding a pure 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.[18]
• Finding a pure 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.[18]
• 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.[18]
• 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.[18]
• 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.[7]
• 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.[7]
• (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.[19]
  • (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.[19]
  • (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.[19]
  • (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.[13] It is claimed that the reduction can be extended so tightness is obtained.[19]
• 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][8][16]
• 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]