PLS-Completeness of String Permutations

When encoding a combinatorial problem as a CNF formula $F$ (think of “is there a $k$-Ramsey graph on $n$ vertices?”), the formula will often contain many symmetries. To make the problem easier for SAT solvers, one can take the statement

The satisfying assignment $\alpha$ should be a local lexicographical minimum with respect to those symmetries,

encode it as a CNF formula $G$ and feed $F\wedge G$ to the SAT solver. Clearly, $F\wedge G$ is satisfiable if and only if $F$ is. In case that $F\wedge G$ is unsatisfiable, SAT solvers are often expected to produce a proof of unsatisfiability. A popular proof system used in this context is DRAT [15]. However, it is not known to what extend DRAT can handle symmetry breaking [7], that is, whether a short DRAT-refutation of $F\wedge G$ can be transformed into a short DRAT-refutation of $F$. In this context, Thapen [14] asked whether there exists a polynomial algorithm that, given a CNF formula $F$, a handful of symmetries thereof, and a satisfying assignment $\alpha$, finds a satisfying assignment $\beta$ that is a local lexicographical minimum with respect to those symmetries. In this paper, we show that this problem is PLS-complete, which is evidence that such a polynomial time algorithm might not exist.

The class FNP is the functional correspondent of NP. TFNP $\subset$ FNP is the subset of total search problems, i.e., problems that always have a solution. As this is a semantic class, TFNP has no known complete problems, and thus it is usually studied via its subclasses. These subclasses are based on the combinatorial principle that proves the existence of a solution. These principles include the existence of sinks in directed acyclic graphs (PLS)[8], the parity argument for directed and undirected graphs (PPAD, PPA) or the pigeonhole principle (PPP) (all introduced in [11]). Nonetheless, not all problems in TFNP can be categorized in one of the known subclasses, Factoring being a prime example.

By the above characterization, PLS requires finding a sink of a directed acyclic graph $G$. This would be possible in polynomial time if $G$ was given explicitly. Instead, $G$ is always given implicitly via a circuit that computes the successor list of a given node. To make sure that $G$ is acyclic, we have a second circuit computing a topological ordering, that is, a “cost” function that is strictly decreasing along the edges. A solution to the problem is a sink of $G$ or an edge $(u,v)$ with $\text{cost}(u)\le \text{cost}(v)$, i.e., violating the decreasing cost condition. This guarantees the totality of the problem.

An alternative definition is the following. For a PLS problem $P$ we have a set of instances $I$. Each instance $i\in I$ has a set of feasible solutions $S$ (e.g. for the Euclidean traveling salesman problem the solutions are exactly the Hamilton cycles of $K_n$). Additionally, we require the following polynomial-time computable algorithms (usually given as circuits):

1. 1.

   an algorithm that decides whether a given $s$ is a feasible solution.

2. 2.

   an algorithm that computes a starting solution $s\in S$

3. 3.

   an algorithm that computes for a feasible solution $s$ the neighborhood $N(s)$

4. 4.

   an algorithm that computes for a solution $s$ the cost $\text{cost}(s)$

A feasible solution $s$ is a local minimum if $\text{cost}(s)\le \text{cost}(s^{\prime })$ for all $s^{\prime }\in N(s)$. The definition is given for a minimization problem, but can be also defined in terms of a maximization problem.

We can easily transform this into a directed acyclic graph by keeping only those neighbors in $N(s)$ having strictly smaller cost–or even keeping only the one neighbor $s^{\prime }\in N(s)$ of minimal cost (breaking ties arbitrarily).

Similar to NP, there is also a hardness structure in PLS. Let $P$ and $Q$ be two problems in PLS. $P$ reduces to $Q$ via a PLS-reduction $(f,g)$ for functions $f$ and $g$ such that $f$ maps an instance $I$ from $P$ to an instance $f(I)$ of $Q$ and $g$ maps a solution $s$ of $f(I)$ to a solution $g(I,s)$ of $P$ so that if $s$ is a local minimum in $f(I)$ then also $g(I,s)$ is a local minimum in $I$. This was defined in [8] and the first natural PLS-complete problem is FLIP. There solutions are $n$-bit strings, the cost is calculated by a given circuit $C$ and the neighborhood are all $n$-bit strings with a Hamming distance of 1.

The obvious greedy algorithm to find a solution for a PLS-problem is as follows: Use the given algorithms to compute the start solution and always select the best neighbor until there is no better solution. This solution is called the standard solution and the algorithm the standard algorithm. For the problem FLIP, finding the standard solution for a given start solution is PSPACE-complete[12, Lemma 4].

Reductions that preserve the PSPACE-completeness are called tight[13]. For this, we consider the transition graph $TG(I)$ of an instance $I$ of the problem $P$, that has a directed edge from each feasible solution $x$ to all of its neighbors $N(x)$.

A PLS-reduction $(f,g)$ from $P$ to $Q$ is called tight if for every instance $I$ of $P$ there exists a set $ℛ$ of feasible solutions for $f(I)$ such that

1. 1.

   $ℛ$ contains all local optima of $f(I)$

2. 2.

   For every solution $s$ of $I$ it is possible to construct in polynomial time a feasible solution $t\in ℛ$ such that $g(I,t)=s$

3. 3.

   If the transition graph of $TG(f(I))$ contains a path from $q$ to $q^{\prime }$ such that both $q$ and $q^{\prime }$ are in $ℛ$ and all other intermediate nodes are not in $ℛ$, let $p=g(I,q)$ and $p^{\prime }=g(I,q^{\prime })$ be the corresponding solutions in $P$. Then either $p=p^{\prime }$ or there is an arc from $p$ to $p^{\prime }$ in $TG(I)$.

An interesting subclass of PLS is CLS that is supposed to capture continuous local search problems. Recently, it was shown that CLS $=$ PLS $\cap$ PPAD[5].

A permutation of a set $V$ is a bijection $\pi :V\to V$. For permutations ${\pi }_1,\mathrm{\dots },{\pi }_k$, we denote by $⟨{\pi }_1,\mathrm{\dots },{\pi }_k⟩$ the subgroup of $S_V$ generated by the ${\pi }_i$. Checking membership $\pi \in ⟨{\pi }_1,\mathrm{\dots },{\pi }_k⟩$ is non-trivial but can be done in polynomial time [6, Section 1].

The problem is efficiently solvable when $k=1$, i.e., we are only given a single permutation $\pi$. We describe a different way of solving it in contrast to [9]. We can transform $\pi$ into the cycle notation and annotate each element with the bit that it is mapped to by the string $𝐱\in {\{0,1\}}^n$. We call a cycle interesting if $𝐱$ is non-constant on it. Additionally, we identify each cycle with its smallest member.

Consider the permutation $(\mathrm{1\; 2\; 5})(\mathrm{3\; 4})(\mathrm{7\; 8})$ and the string $001001$ depicted in Figure 1. We color an element green if it is mapped to zero and orange if it is mapped to one by the string. The left cycle is the cycle of $1$ and not interesting whereas the other two are which are identified by $3$ and $7$.

The permutation has no effect on elements on non-interesting cycles. Due to the cost function, lower indices are more costly than higher indices. We look for the interesting cycle that contains the position with the least index among all interesting cycles and let $l$ be the smallest index on it. There are indices $i$ and $j:=\pi (i)$ on this cycle with $x_i=0$ and $x_j=1$. Let $k$ be such that ${\pi }^k(l)=i$. Then $𝐱\circ {\pi }^k$ has a $0$ at position $i$ but $𝐱\circ {\pi }^{k+1}$ has a $1$. In other words, $𝐱\circ {\pi }^k$ is a local optimum

In example in Figure 1 we have $x=3$, $j=4$ and $d=1$. The local optimal permutation is hence $\pi$.

This follows via a reduction from Independent Set where we encode a graph as a bit string, one bit per potential edge, and the permutations basically allow us to move the vertices of the independent set $I$ to the front, generating a large prefix of $\left(\genfrac{}{}{0pt}{}{|I|}{2}\right)$ many $0$’s.

Since $1$-Permutation Local Orbit Minimum was so clearly solvable in polynomial time (even by the greedy algorithm), it comes as a surprise that global optimization, even for one permutation, is NP-hard:

We will define an intermediate NP-complete problem called Disjunctive Chinese Remainder, short DCR. For two numbers $t,m\in \mathbb{N}$ and a set $S\subseteq \mathbb{N}$, we write

to state that $t\not\equiv smodm$ for all $s\in S$. Now in the DCR decision problem, we are given moduli $m_1,\mathrm{\dots },m_l$ and sets of “forbidden remainders” $S_1,\mathrm{\dots },S_l$ with $S_i\subseteq {\mathbb{Z}}_{m_i}:=\{0,1,\mathrm{\dots },m_i-1\}$. All numbers are given in unary and the moduli are not required to be pairwise co-prime. DCR asks for a solution $t\in \mathbb{N}$ of the system

This is clearly in NP: if there is a solution $x\in \mathbb{N}$, then there is one with $0\le t\le \mathrm{lcm}(m_1,m_2,\mathrm{\dots }{m}_l)$ and thus $t$ has polynomially many bits in binary. Verifying that this $t$ is a solution can now be done by division with remainder.

We reduce from the PLS-complete problem FLIP. This problem is especially suitable since it uses a lexicographic cost function, too. Formally FLIP is defined as follows:

We use an idea by Krentel[10] and have $n+1$ copies $C_0,C_1,\mathrm{\dots },C_n$ of the circuit $C$, where $C_0$ is fed as an input $𝐱$ and $C_i$ is fed as an input $𝐱\oplus {𝐞}_i$, i.e., $𝐱$ with the $i$-th bit flipped. The setup is depicted in Figure 2.

The permutation group consists of two types of permutations. The first kind ${\pi }_i^j$ simulates flipping the output of gate $i$ in circuit $j$; we allow for gates and hence circuits to be temporarily evaluated incorrectly. The input and output of a gate are not saved anywhere but syntactically built into the permutations and string. An exception is the input and output of the circuit, which we save for later usage. We use some positions as very important control bits to ensure that the correct evaluation is always possible.

The second type of permutation ${\sigma }_j$ swaps the circuit $0$ with the circuit $j$ and flips the $j$-th input bit for all other circuits. This simulates a step in the FLIP-problem.

We assume without loss of generality that the circuit $C$ consists only of NAND-gates. Additionally, we assume that no input is directly passed to an output, i.e. on every path from an input to an output, there is at least one gate.

We will now describe the set $V$ of positions, the permutations in $S_V$, and how strings in ${\{0,1\}}^V$, called assignments, correspond to the circuits $C_0,\mathrm{\dots },C_n$ computing their values on an input $𝐱$ and its neighbors $𝐱\oplus {𝐞}_i$. We face two main challenges:

1. 1.

   We need an operation of the form “flip bit $i$”, but permutations can only permute positions, not flip bits. We solve this by replacing position $i$ by two positions $i_0,i_1$ and encoding $[y_i=0]$ by $[y_{i_0}=0,y_{i_1}=1]$ and $[y_i=1]$ by $[y_{i_0}=1,y_{i_1}=0]$. Flipping bit $i$ then corresponds to the permutation that swaps $i_0$ and $i_1$, i.e., the transposition $(i_0,i_1)$. We call the one-position-per-bit view the condensed view and the two-positions-per-bit view the expanded view. We will give details in the full version due to space restrictions. For now, we phrase things in the condensed view.

2. 2.

   Usually, when we flip an input $x_i$ to a circuit $C$, we imagine the change propagating instantaneously through the circuit $C$, potentially changing its output. Here, we need to allow for a way for this change to proceed gradually; therefore, we allow gates to be temporarily in an incorrect state.

When we have a position $i\in V$ and an assignment $𝐲\in {\{0,1\}}^V$ and $y_i=b$, we sometimes say $i$ is assigned value $b$ and sometimes the label of $i$ is $b$.

We have promised to use a lexicographic ordering as a cost function. That is, if $𝐲,{𝐲}^{\prime }\in {\{0,1\}}^V$ are two assignments, then $𝐲$ is better than ${𝐲}^{\prime }$ (meaning lower cost) if $𝐲{\prec }_{\mathrm{lex}}{𝐲}^{\prime }$. Thus, to define the cost function it suffices to specify an ordering on the positions in $V$.

• $\mathrm{■}$

  Positions in $C_0$ come before positions in $C_1$ and so on.

• $\mathrm{■}$

  Within a circuit, most important are the control positions $g_{11}$ of the gates, followed by the output gates, followed by all remaining positions.

• $\mathrm{■}$

  Within control positions in the same circuit, the order follows the topological ordering of the circuit, i.e., if $g$ feeds into $h$, then $g$’s control position comes before $h$’s.

In this section we now prove the correctness and tightness of our reduction. In order to show the correctness we have to show that if $\pi \in G$ is a local optimum of the $k$-Permutation Local Orbit Minimum instance, i.e., if the assignment $𝐲:={𝐲}_{\mathrm{start}}\circ \pi$ cannot be further improved by applying a ${\pi }_g$ or a ${\sigma }_j$, then the input to $C_0$ encoded in $𝐲$ corresponds to a local optimum of FLIP.

Well-behaved permutations for a string $s$ and a circuit $C$ are interesting, because they realize the evaluation of the circuit somehow. The only problem is that the gate does not have the correct output in the current permutation with the string $s$ compared to $C$.