Unique End of Potential Line

Introduction

The complexity class $\mathsf{TFNP}$ contains search problems that are guaranteed to have a solution, and whose solutions can be verified in polynomial time . While it is a semantically defined complexity class and thus unlikely to contain complete problems, a number of syntactically defined subclasses of $\mathsf{TFNP}$ have proven very successful at capturing the complexity of total search problems. In this paper, we focus on two in particular, $\mathsf{PPAD}$ and $\mathsf{PLS}$. The class $\mathsf{PPAD}$ was introduced in to capture the difficulty of problems that are guaranteed total by a parity argument. It has attracted intense attention in the past decade, culminating in a series of papers showing that the problem of computing a Nash-equilibrium in two-player games is $\mathsf{PPAD}$-complete , and more recently a conditional lower bound that rules out a PTAS for the problem . No polynomial-time algorithms for $\mathsf{PPAD}$-complete problems are known, and recent work suggests that no such algorithms are likely to exist . $\mathsf{PLS}$ is the class of problems that can be solved by local search algorithms (in perhaps exponentially-many steps). It has also attracted much interest since it was introduced in , and looks similarly unlikely to have polynomial-time algorithms. Examples of problems that are complete for $\mathsf{PLS}$ include the problem of computing a pure Nash equilibrium in a congestion game , a locally optimal max cut , or a stable outcome in a hedonic game .

Continuous Local Search.

If a problem lies in both $\mathsf{PPAD}$ and $\mathsf{PLS}$ then it is unlikely to be complete for either class, since this would imply an extremely surprising containment of one class in the other. In their 2011 paper , Daskalakis and Papadimitriou observed that there are several prominent total function problems in $\mathsf{PPAD}\cap\mathsf{PLS}$ for which researchers have not been able to design polynomial-time algorithms. Motivated by this they introduced the class $\mathsf{CLS}$, a syntactically defined subclass of $\mathsf{PPAD}\cap\mathsf{PLS}$. $\mathsf{CLS}$ is intended to capture the class of optimization problems over a continuous domain in which a continuous potential function is being minimized and the optimization algorithm has access to a polynomial-time continuous improvement function. They showed that many classical problems of unknown complexity are in $\mathsf{CLS}$, including the problem of solving a simple stochastic game, the more general problems of solving a Linear Complementarity Problem with a P-matrix, finding an approximate fixpoint to a contraction map, finding an approximate stationary point of a multivariate polynomial, and finding a mixed Nash equilibrium of a congestion game.

CLS problems with unique solutions.

In this paper we study an interesting subset of problems that lie within $\mathsf{CLS}$, and have unique solutions.

The P-matrix linear complementarity problem (P-LCP) is a variant of the linear complementarity problem in which the input matrix is a P-matrix . An interesting property of this problem is that, if the input matrix actually is a P-matrix, then the problem is guaranteed to have a unique solution . Designing a polynomial-time algorithm for P-LCP has been open for decades, at least since the 1978 paper of Murty that provided exponential-time examples for Lemke’s algorithm for P-LCPs.

A unique sink orientation (USO) is an orientation of the edges of an $n$-dimensional hypercube such that every face of the cube has a unique sink. Since the entire cube is a face of itself, this means that there is a unique vertex of the cube that is a sink, meaning that all edges are oriented inwards. The USO problem is to find this unique sink.

All of these problems are most naturally stated as promise problems. This is because we have no way of verifying up front whether a function is contracting, whether a matrix is a P-matrix, or whether an orientation is a USO. Hence, it makes sense, for example, to study the contraction problem where it is promised that the function $f$ is contracting, and likewise for the other two.

So Contraction can be formulated as the non-promise problem of either finding a solution, or finding a violation. This problem is in $\mathsf{TFNP}$ because in the case where there is not a unique solution, there must exist a violation of the promise. The P-LCP and USO problems also have violations that can be witnessed by short certificates, and so they can be turned into non-promise problems contained in the same way, and these problems also lie in $\mathsf{TFNP}$.

For Contraction and P-LCP we actually have the stronger result that both problems are in $\mathsf{CLS}$ . Prior to this work USO was not known to lie in any non-trivial subclass of $\mathsf{TFNP}$, and placing USO into a non-trivial subclass of $\mathsf{TFNP}$ was identified as an interesting open problem by Kalai [51, Problem 6].

We remark that not every problem in CLS has the uniqueness properties that we identify above. For example, the KKT problem lies in $\mathsf{CLS}$, but has no apparent notion of having a unique solution. The problems that we identify here seem to share the special property that there is a natural promise version of the problem, and that promise problem always has a unique solution.

1 Our contribution

In this paper, we define a complexity class that naturally captures the properties exhibited by problems like Contraction, P-LCP, and USO. In fact, we define two new sub-classes of $\mathsf{CLS}$.

The complexity class $\mathsf{EOPL}$ contains every problem that can be reduced in polynomial time to the problem EndOfPotentialLine, which we define in this paper (Definition 9). The EndOfPotentialLine problem unifies in an extremely natural way the circuit-based views of $\mathsf{PPAD}$ and of $\mathsf{PLS}$. The canonical $\mathsf{PPAD}$-complete problem is EndOfLine, a problem that provides us with an exponentially large graph consisting of lines and cycles, and asks us to find the end of one of the lines. The canonical $\mathsf{PLS}$-complete problem provides us with an exponentially large DAG, whose acyclicity is guaranteed by the existence of a potential function that increases along each edge. The problem EndOfPotentialLine is an instance of EndOfLine that also has a potential function that increases along each edge.

So the class $\mathsf{EOPL}$ captures problems that admit a single combinatorial proof of their joint membership in the classes $\mathsf{PPAD}$ of fixpoint problems and $\mathsf{PLS}$ of local search problems, and is a combinatorially-defined alternative to the class $\mathsf{CLS}$. We are able to show that $\mathsf{EOPL}\subseteq\mathsf{CLS}$ (Corollary 11), by providing a polynomial-time reduction from EndOfPotentialLine to the EndOfMeteredLine problem defined by Hubáček and Yogev , which they have shown to lie in $\mathsf{CLS}$.

We remark that it is an interesting open problem to determine whether $\mathsf{EOPL}=\mathsf{CLS}$. The inspiration behind both classes was to capture problems in $\mathsf{PPAD}\cap\mathsf{PLS}$. The class $\mathsf{CLS}$ does this by affixing a potential function to the $\mathsf{PPAD}$-complete Brouwer fixpoint problem, while $\mathsf{EOPL}$ does this affixing a potential function to the $\mathsf{PPAD}$-complete problem EndOfLine. The class $\mathsf{EOPL}$ is not the main focus of this paper, however.

Unique end of potential line.

An EndOfPotentialLine instance consists of an exponentially large graph that contains only lines (the cycles that can appear in EndOfLine instances are ruled out by the potential function.) The problem explicitly gives us the start of one of these lines. A solution to the problem is a vertex that is at the end of any line, other than the given start vertex. We could find a solution by following the line from the start vertex until we find the other end, although that may take exponential time. There may be many other lines in the graph though, and the starts and ends of these lines are also solutions.

We define the promise-problem PromiseUniqueEOPL, in which it is promised that there is a unique line in the graph. This line must be the one that begins at the given starting vertex, and so the only solution to the problem is the other end of that line. Thus, if the promise is satisfied, the problem has a unique solution. We can define the promise-class $\mathsf{PromiseUEOPL}$ which contains all promise-problems that can be reduced in polynomial-time to PromiseUniqueEOPL.

We are not just studying promise problems in this paper, however. We can turn PromiseUniqueEOPL into a non-promise problem by defining appropriate violations. One might imagine that a suitable violation would be a vertex that is the start of a second line. Indeed, if we are given the promise that there is no start to a second line, then we do obtain the problem PromiseUniqueEOPL. However, with just this violation, we obtain a problem that is identical to EndOfPotentialLine, which is not what we are intending to capture.

Instead we add a violation that captures any pair of vertices $v$ and $u$ that are provably on different lines, even if $v$ and $u$ are in the middle of their respective lines. We do this by using the potential function: if $v$ and $u$ have the same potential, then they must be on different lines, and likewise if the potential of $u$ lies between the potential of $v$ and the potential of the successor of $v$. We formalise this as the problem UniqueEOPL (Definition 12), and we define the complexity class $\mathsf{UniqueEOPL}$ to contain all (non-promise) problems that can be reduced in polynomial-time to UniqueEOPL.

We have that $\mathsf{UniqueEOPL}\subseteq\mathsf{EOPL}$ by definition, since UniqueEOPL simply adds an extra type of violation to EndOfPotentialLine. We remark that this new violation makes the problem substantially different from EndOfPotentialLine. In EndOfPotentialLine only the starts and ends of lines are solutions, while in UniqueEOPL there are many more solutions whenever there is more than one line in the instance. As such, we view $\mathsf{UniqueEOPL}$ as capturing a distinct subclass of problems in $\mathsf{EOPL}$, and we view it as the natural class for promise-problems in $\mathsf{PPAD}\cap\mathsf{PLS}$ that have unique solutions.

UEOPL containment results.

We show that USO, P-LCP, and a variant of the Contraction problem all lie in $\mathsf{UniqueEOPL}$. We define the concept of a promise-preserving reduction, which is a polynomial-time reduction between two problems A and B, with the property that if A is promised to have a unique solution, then the instance of B that is produced by the reduction will also have a unique solution. All of the reductions that we produce in this paper are promise-preserving, which means that whenever we show that a problem is in $\mathsf{UniqueEOPL}$, we also get that the corresponding promise problem lies in $\mathsf{PromiseUEOPL}$.

USO is in $\mathsf{UniqueEOPL}$ under promise-preserving reductions.

For the USO problem, our $\mathsf{UniqueEOPL}$ containment result substantially advances our knowledge about the problem. Prior to this work, the problem was only known to lie in $\mathsf{TFNP}$, and Kalai [51, Problem 6] had posed the challenge to place it in some non-trivial subclass of $\mathsf{TFNP}$. Our result places USO in $\mathsf{UniqueEOPL}$, $\mathsf{EOPL}$, $\mathsf{CLS}$, $\mathsf{PPAD}$ (and hence $\mathsf{PPA}$ and $\mathsf{PPP}$), and $\mathsf{PLS}$, and so we answer Kalai’s challenge by placing the problem in all of the standard subclasses of $\mathsf{TFNP}$.

This result is in some sense surprising. Although every face of a USO has a unique sink, the orientation itself may contain cycles, and so there is no obvious way to define a potential function for the problem. Moreover, none of the well-known algorithms for solving USOs have the line-following nature needed to produce an EndOfLine instance. Nevertheless, our result shows that one can produce an EndOfLine instance that has potential function for the USO problem.

There are two different variants of the P-LCP problem, both of which lie in $\mathsf{UniqueEOPL}$ under promise-preserving reductions.

We actually provide two different promise-preserving reductions from P-LCP to UniqueEOPL. The issue here is that there are many possible types of violation that one can define for P-LCP. So far, the standard formulation of P-LCP either asks for a solution, or a non-positive principle minor of the input matrix. A matrix is a P-matrix if and only if all of its principle minors are positive, and so this is sufficient to define a total problem.

The reduction from P-LCP to EndOfLine can map the start and end of each line back to either a solution or a non-positive principle minor. Our problem is that the extra violations in the UniqueEOPL instance, corresponding to a proof that there are multiple lines, do not easily map back to non-positive principle minors. They do however map back to other short certificates that the input matrix is not a P-matrix. For example, a matrix is a P-matrix if and only if it does not reverse the sign of any non-zero vector . So we can also formulate P-LCP as a total problem that asks for a solution, or a non-zero vector whose sign is reversed.

We study the following variants of P-LCP. The first variant asks us to either find a solution, or find a non-positive principle minor, or find a non-zero vector whose sign is reversed. The second variant asks us to either find a solution, or a non-positive principle minor, or a third type of violation whose definition is inspired by a violation of the USO property. In all cases, we either solve the problem, or obtain a short certificate that the input was not a P-matrix, although the format of these certificates can vary.

It is not clear whether these variants are equivalent under polynomial-time reductions, as one would need to be able to map one type of violation to the other efficiently. We remark that if one is only interested in the promise problem, then the choice of violations is irrelevant. Both of our reductions show that promise P-LCP lies in $\mathsf{PromiseUEOPL}$.

Prior work has avoided this issue by instead asking for an approximate fixpoint, and the problem of finding an approximate fixpoint of a contraction map specified by an arithmetic circuit lies in $\mathsf{CLS}$ . However, if we look for approximate fixpoints, then we destroy the uniqueness property that we are interested in, because there are infinitely many approximate fixpoint solutions surrounding any exact fixpoint.

So, we study the problem where the function is represented by a $\mathsf{LinearFIXP}$ arithmetic circuit , which is a circuit in which the multiplication of two variables is disallowed. This ensures that, when the function actually is contracting, there is a unique rational fixpoint that we can produce. We note that this is still an interesting class of contraction maps, since it is powerful enough to represent simple-stochastic games .

We place this problem in $\mathsf{UniqueEOPL}$ via a promise-preserving reduction. Our reduction can produce multiple types of violation. In addition to the standard violation of a pair of points at which $f$ is not contracting, our reduction sometimes produces a different type of violation (cf. Definition 32), which while not giving an explicit violation of contraction, still gives a short certificate that $f$ is not contracting.

The following problems are in $\mathsf{UniqueEOPL}$

Finally, we observe that our results prove that several other problems lie in $\mathsf{UniqueEOPL}$. The simple-stochastic game (SSG) problem is known to reduce to Contraction and to P-LCP , and thus our two results give two separate proofs that the SSG problem lies in $\mathsf{UniqueEOPL}$. It is known that discounted games can be reduced to SSGs , mean-payoff games can be reduced to discounted games , and parity games can be reduced to mean-payoff games . So all of these problems lie in $\mathsf{UniqueEOPL}$ too. Finally, Gärtner et al. noted that the ARRIVAL problem lies in $\mathsf{EOPL}$, and in fact their EndOfPotentialLine instance always contains exactly one line, and so the problem also lies in $\mathsf{UniqueEOPL}$.

We remark that none of these are promise-problems. Each of them can be formulated so that they unconditionally have a unique solution. Hence, these problems seem to be easier than the problems captured by $\mathsf{UniqueEOPL}$, since problems that are complete for $\mathsf{UniqueEOPL}$ only have a unique solution conditioned on the promise that there are no violations.

A UEOPL-complete problem.

In addition to our containment results, we also give a $\mathsf{UniqueEOPL}$-completeness result. Specifically, we show that One-Permutation Discrete Contraction (OPDC) is complete for $\mathsf{UniqueEOPL}$.

OPDC is a problem that is inspired by both Contraction and USO. Intuitively, it is a discrete version of Contraction. The inputs to the problem are (a concise representation of) a discrete grid of points $P$ covering the space $^{d}$, and a set of direction functions $\mathcal{D}=D_{i=1\dots d}$, where each function $D_{i}$ has the form $D_{i}:P\rightarrow\{\mathsf{up},\mathsf{down},\mathsf{zero}\}$. To discretize a map $f:^{d}\rightarrow^{d}$ we simply define $D_{i}$ so that

$D_{i}(p)=\mathsf{up}$ whenever $f(p)_{i}>p_{i}$,

$D_{i}(p)=\mathsf{zero}$ whenever $f(p)_{i}=p_{i}$, and

$D_{i}(p)=\mathsf{down}$ whenever $f(p)_{i}<p_{i}$.

So the direction function for dimension $i$ simply points in the direction that $f$ moves in dimension $i$. To solve the problem, we seek a point $p\in P$ such that $D_{i}(p)=\mathsf{zero}$ for all $i$, which corresponds to a fixpoint of $f$.

We remark that, although the problem was formulated as a discretization of Contraction, it is also closely related to the USO problem. Specifically, if we take the set of points $P$ to be the $\{0,1\}^{n}$ hypercube, then the direction functions actually specify an orientation of the cube. Moreover, the condition that every slice should have have unique fixpoint exactly corresponds to the USO property that every face should have a unique sink. However, since we only insist on this property for $i$-slices, OPDC can be viewed as a variant of USO in which only some of the faces have unique sinks.

OPDC lies in $\mathsf{UniqueEOPL}$ under promise-preserving reductions.

OPDC actually plays a central role in the paper. We reduce Piecewise-Linear Contraction, USO, and P-LCP to it, and we then reduce OPDC to UniqueEOPL, as shown in Figure 1. The reduction from OPDC to UniqueEOPL is by far the most difficult step.

In the case where the promise is satisfied, meaning that the OPDC instance has a unique fixpoint, the reduction defines a single line that starts at the point $p\in P$ with $p_{i}=0$ for all $i$, and ends at the unique fixpoint. This line walks around the grid, following the direction functions given by $\mathcal{D}$ in a specific manner that ensures that it will find the fixpoint, while also decreasing a potential function at each step. We need to very carefully define the vertices of this line, to ensure that the line is unique, and for this we crucially rely on the fact that every $i$-slice also has a unique fixpoint.

This does not get us all the way to UniqueEOPL though, because the line we describe above lacks a predecessor circuit. In UniqueEOPL, each vertex has a predecessor, a successor and a potential, but the line we construct only gives successors and potentials to each vertex. To resolve this, we apply the pebbling game reversibility argument introduced by Bitansky et al , and later improved by Hubáček and Yogev . Using this technique allows us to produce a predecessor circuit, as long as there is exactly one line in the instance.

Our reduction also handles violations in the OPDC instance. The key challenge here is that the pebbling game argument assumes that there is exactly one line, and so far it has only been applied to promise-problems. We show that the argument can be extended to work with non-promise problems that may have multiple lines. This can cause the argument to break, specifically when multiple lines are detected, but we are able to show that these can be mapped back to violations in the OPDC instance.

OPDC is $\mathsf{UniqueEOPL}$-complete under promise-preserving reductions, even when the set of points $P$ is a hypercube.

We show that OPDC is $\mathsf{UniqueEOPL}$-hard by giving a polynomial-time promise-preserving reduction from UniqueEOPL to OPDC. This means that OPDC is $\mathsf{UniqueEOPL}$-complete, and the variant of OPDC in which it is promised that there are no violations is $\mathsf{PromiseUEOPL}$-complete.

Our reduction produces an OPDC instances where the set of points $P$ is the boolean hypercube $\{0,1\}^{n}$. In the case where the UniqueEOPL instance has no violations, meaning that it contains a single line, the reduction embeds this line into the hypercube. To do this, it splits the line in half. The second half is embedded into a particular sub-cube, while the first half is embedded into all other sub-cube. This process is recursive, so each half of the line is again split in half, and further embedded into sub-cubes. The reduction ensures that the only fixpoint of the instance corresponds to the end of the line. If the UniqueEOPL instance does have violations, then this embedding may fail. However, in any instance where the embedding fails, we are able to produce a violation for the original UniqueEOPL instance.

We remark that this hardness reduction makes significant progress towards showing a hardness result for Contraction and USO. As we have mentioned, OPDC is a discrete variant of Contraction, and when the set of points is a hypercube, the problem is also very similar to USO. The key difference is that OPDC insists that only $i$-slices should have a unique fixpoint, whereas Contraction and USO insist that all slices should have unique fixpoints. To show a hardness result for either of those two problems, one would need to produce an OPDC instance with that property.

New algorithms.

We also show that these results can be extended to the case where the contraction map is given by a general arithmetic circuit. In this case, we provide polynomial-time algorithm that either finds an approximate fixpoint, or produces a short certificate that the function is not contracting.

Finally, as noted in , one of our reductions from P-LCP to EndOfPotentialLine allows a technique of Aldous to be applied, which in turn gives the fastest known randomized algorithm for P-LCP.

2 Related work

Recent work by Hubáček and Yogev proved lower bounds for $\mathsf{CLS}$. They introduced a problem known as EndOfMeteredLine which they showed was in $\mathsf{CLS}$, and for which they proved a query complexity lower bound of $\Omega(2^{n/2}/\sqrt{n})$ and hardness under the assumption that there were one-way permutations and indistinguishability obfuscators for problems in $\mathsf{P_{/poly}}$. Another recent result showed that the search version of the Colorful Carathéodory Theorem is in $\mathsf{PPAD}\cap\mathsf{PLS}$, and left open whether the problem is also in $\mathsf{CLS}$ .

P-LCP.

Papadimitriou showed that P-LCP, the problem of solving the LCP or returning a violation of the P-matrix property, is in $\mathsf{PPAD}$ using Lemke’s algorithm. The relationship between Lemke’s algorithm and $\mathsf{PPAD}$ has been studied by Adler and Verma . Later, Daskalakis and Papadimitrou showed that P-LCP is in $\mathsf{CLS}$ , using the potential reduction method in . Many algorithms for P-LCP have been studied, e.g., . However, no polynomial-time algorithms are known for P-LCP, or for the promise version where one can assume that the input matrix is a P-matrix.

The best known algorithms for P-LCP are based on a reduction to Unique Sink Orientations (USOs) of cubes . For an P-matrix LCP of size $n$, the USO algorithms of apply, and give a deterministic algorithm that runs in time $O(1.61^{n})$ and a randomized algorithm with expected running time $O(1.43^{n})$. The application of Aldous’ algorithm to the UniqueEOPL instance that we produce from a P-matrix LCP takes expected time $2^{n/2}\cdot\operatorname{poly}(n)=O(1.4143^{n})$ in the worst case.

Unique Sink Orientations.

In this paper we study USOs of cubes, a problem that was first studied by Stickney and Watson in the context of P-matrix LCPs. A USO arising from a P-matrix may be cyclic. Motivating by Linear Programming, acylic, AUSOs have also been studied, both for cubes and general polytopes . Recently Gärtner and Thomas studied the computational complexity of recognizing USOs and AUSOs . They found that the problem is $\mathsf{coNP}$-complete for USOs and $\mathsf{PSPACE}$-complete for AUSOs. A series of papers provide upper and lower bounds for specific algorithms for solving (A)USOs, including . An AUSOs on a $n$-dimensional cube can be solved in subexponential time, by the RANDOM-FACET algorithm, which is essentially tight for this algorithm . An almost quadratic lower bound on the number of vertex evaluations needed to solve a general USO is known ; unlike for AUSOs, the best running times known for general USOs, as for P-matrix LCPs, are exponential. To be best of our knowledge, we are first to study the general problem of solving a USO from a complexity-theoretic point of view.

Contraction.

Infinite games.

3 Future directions

A clear direction for future work is to show that further problems are $\mathsf{UniqueEOPL}$-complete. We have several conjectures.

We think that, among our three motivating problems, USO is the most likely to be $\mathsf{UniqueEOPL}$-complete. Our hardness proof for OPDC already goes some way towards proving this, since we showed that OPDC was hard even when the set of points is a hypercube. The key difference between OPDC on a hypercube and USO is that OPDC only requires that the faces corresponding to $i$-slices should have unique sinks, while USO requires that all faces should have unique sinks.

Our OPDC hardness result also goes some way towards showing that Piecewise-Linear Contraction is hard, however there are more barriers to overcome here. In addition to the $i$-slice vs. all slice issue, we would also need to convert the discrete OPDC problem to the continuous contraction problem. Converting discrete problems to continuous fixpoint problems has been well-studied in the context of $\mathsf{PPAD}$-hardness reductions , but here the additional challenge is to carry out such a reduction while maintaining the contraction property.

Aside from hardness, we also think that the relationship between Contraction and USO should be explored further. Our formulation of the OPDC problem exposes significant similarities between the two problems, which until this point have not been recognised. Can we reduce USO to Contraction in polynomial time?

Of all of our conjectures, this will be the most difficult to prove. Since P-LCP reduces to USO, the hardness of USO should be resolved before we attempt to show that P-LCP is hard. One possible avenue towards showing the hardness of P-LCP might be to reduce from Piecewise-Linear Contraction. Our $\mathsf{UniqueEOPL}$ containment proof for Piecewise-Linear Contraction makes explicit use of the fact that the problem can be formulated as an LCP, although in that case the resulting matrix is not a P-matrix. Can we modify the reduction to produce a P-matrix?

$\mathsf{UniqueEOPL}\subset\mathsf{EOPL}=\mathsf{CLS}$.

The question of $\mathsf{EOPL}$ vs $\mathsf{CLS}$ is unresolved, and we actually think it could go either way. One could show that $\mathsf{EOPL}=\mathsf{CLS}$ by placing either of the two known $\mathsf{CLS}$-complete Contraction variants into $\mathsf{EOPL}$ . If the two classes are actually distinct, then it is interesting to ask which of the problems in $\mathsf{CLS}$ are also in $\mathsf{EOPL}$.

On the other hand, we believe that $\mathsf{UniqueEOPL}$ is a strict subset of $\mathsf{EOPL}$. The evidence for this is that the extra violation in UniqueEOPL that does not appear in EndOfPotentialLine changes the problem significantly. This new violation will introduce many new solutions whenever there are multiple lines in the instance, and so it is unlikely, in our view, that one could reduce EndOfPotentialLine to UniqueEOPL. Of course, there is no hope to unconditionally prove that $\mathsf{UniqueEOPL}\subset\mathsf{EOPL}$, but we can ask for further evidence to support the idea. For example, can oracle separations shed any light on the issue?

Finally, we remark that $\mathsf{UniqueEOPL}$ is the closest complexity class to $\mathsf{FP}$, among all the standard sub-classes of $\mathsf{TFNP}$. However, we still think that further subdivisions of $\mathsf{UniqueEOPL}$ will be needed. Specifically, we do not believe that simple stochastic games, or any of the problems that can be reduced to them, are $\mathsf{UniqueEOPL}$-complete, since all of these problems have unique solutions unconditionally. Further research will be needed to classify these problems.

Unique End of Potential Line

In this section we define two new complexity classes called $\mathsf{EOPL}$ and $\mathsf{UniqueEOPL}$. These two classes are defined by merging the definitions of $\mathsf{PPAD}$ and $\mathsf{PLS}$, so we will begin by recapping those classes.

The complexity class $\mathsf{PPAD}$ contains every problem that can be reduced to EndOfLine .

Given Boolean circuits $S,P:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $P(0^{n})=0^{n}\neq S(0^{n})$, find one of the following:

A point $x\in\left\{0,1\right\}^{n}$ such that $P(S(x))\neq x$.

A point $x\in\left\{0,1\right\}^{n}$ such that $x\neq 0^{n}$ and $S(P(x))\neq x$.

Intuitively, the problem defines an exponentially large graph where all vertices vhave in-degree and out-degree at most one. Each bit-string in $\left\{0,1\right\}^{n}$ defines a vertex, while the functions $S$ and $P$ define successor and predecessor functions for each vertex. A directed edge exists from vertex $x$ and $y$ if and only if $S(x)=y$ and $P(y)=x$. Any vertex $x$ for which $P(S(x))\neq x$ has no outgoing edge, while every vertex $y$ with $S(P(x))\neq x$ has no incoming edge.

The condition that $P(0^{n})=0^{n}\neq S(0^{n})$ specifies that the vertex $0^{n}$ has no incoming edge, and so it is the start of a line. To solve the problem, we must find either a solution of type (E1), which is a vertex $x$ that is the end of a line, or a solution of type (E2), which is a vertex $x$ other than $0^{n}$ that is the start of a line. Since we know that the graph has at least one source, there must at least exist a solution of type (E1), and so the problem is in $\mathsf{TFNP}$.

The complexity class $\mathsf{PLS}$ contains every problem that can be reduced to the SinkOfDag While this is not the standard definition of PLS, it has been observed that the standard $\mathsf{PLS}$-complete problem can easily be recast as a SinkOfDag instance .

Given a Boolean circuit $S:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $S(0^{n})\neq 0^{n}$, and a circuit $V:\left\{0,1\right\}^{n}\to\left\{0,1,\dotsc,2^{m}-1\right\}$ find:

A vertex $x\in\left\{0,1\right\}^{n}$ such that $S(x)\neq x$ and either $S(S(x))=x$ or $V(S(x))\leq V(x)$.

Once again, the problem specifies an exponentially large graph on the vertex set $\left\{0,1\right\}^{n}$, but this time the only guarantee is that each vertex has out-degree one. The circuit $S$ gives a successor function. In this problem, some bit-strings do not correspond to vertices in the graph. Specifically, if we have $S(x)=x$ for some bit-string $x\in\left\{0,1\right\}^{n}$, then $x$ does not encode a vertex.

The second circuit $V$ gives a potential to each vertex from the set $\left\{0,1,\dotsc,2^{m}-1\right\}$. An edge exists in the graph if and only if the potential increases along that edge. Specifically, there is an edge from $x$ to $y$ if and only if $S(x)=y$ and $V(x)<V(y)$. This restriction means that the graph must be a DAG.

To solve the problem, we must find a sink of the DAG, ie., a vertex that has no outgoing edge. Since we require that $S(0^{n})\neq 0^{n}$, we know that the DAG has at least one vertex, and therefore it must also have at least one sink. This places the problem in TFNP.

We define a new problem called EndOfPotentialLine, which merges the two definitions of EndOfLine and SinkOfDag into a single problem.

Given Boolean circuits $S,P:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $P(0^{n})=0^{n}\neq S(0^{n})$ and a Boolean circuit $V:\left\{0,1\right\}^{n}\to\left\{0,1,\dotsc,2^{m}-1\right\}$ such that $V(0^{n})=0$ find one of the following:

A point $x\in\left\{0,1\right\}^{n}$ such that $S(P(x))\neq x\neq 0^{n}$ or $P(S(x))\neq x$.

A point $x\in\left\{0,1\right\}^{n}$ such that $x\neq S(x)$, $P(S(x))=x$, and $V(S(x))-V(x)\leq 0$.

This problem defines an exponentially large graph where each vertex has in-degree and out-degree at most one (as in EndOfLine) that is also a DAG (as in SinkOfDag). An edge exists from $x$ to $y$ if and only if $S(x)=y$, $P(y)=x$, and $V(x)<V(y)$. As in SinkOfDag, only some bit-string encode vertices, and we adopt the same idea that if $S(x)=x$ for some bit-string $x$, then $x$ does not encode a vertex.

So we have a single instance that is simultaneously an instance of EndOfLine and an instance of SinkOfDag. To solve the problem, it suffices to solve either of these problems. Solutions of type (R1) consist of vertices $x$ that are either the end of a line, or the start of a line (excluding the case where $x=0^{n}$). Solutions of type (R2) consist of any point $x$ where the potential does not strictly increase on the edge between $x$ and $S(x)$.

The complexity class 𝖤𝖮𝖯𝖫𝖤𝖮𝖯𝖫\mathsf{EOPL}.

We define the complexity class $\mathsf{EOPL}$ to consist of all problems that can be reduced in polynomial time to EndOfPotentialLine. By definition the problem lies in $\mathsf{PPAD}\cap\mathsf{PLS}$, since one can simply ignore solutions of type (R2) to obtain an EndOfLine instance, and ignore solutions of type (R1) to obtain a SinkOfDag instance.

In fact we are able to show the stronger result that $\mathsf{EOPL}\subseteq\mathsf{CLS}$. To do this, we reduce EndOfPotentialLine to the problem EndOfMeteredLine, which was defined by Hubáček and Yogev, who also showed that the problem lies in $\mathsf{CLS}$ . The main difference between the two problems is that EndOfMeteredLine requires that the potential increases by exactly one along each edge. The reduction from EndOfMeteredLine to EndOfPotentialLine is straightforward. The other direction is more involved, and requires us to insert new vertices into the instance. Specifically, if there is an edge between a vertex $x$ and a vertex $y$, but $V(y)\neq V(x)+1$, then we need to insert a new chain of vertices of length $V(y)-V(x)-1$ between $x$ and $y$, so that we can ensure that the potential always increases by exactly one along each edge. The full details are given in Appendix A, where the following theorem is proved.

EndOfMeteredLine and EndOfPotentialLine are polynomial-time equivalent.

As we have mentioned, Hubáček and Yogev have shown that EndOfMeteredLine lies in $\mathsf{CLS}$ , so we get the following corollary.

Problems with unique solutions.

The problems that we study in this paper all share a specific set of properties that cause them to produce an interesting subclass of EndOfPotentialLine instances. Each of the problems that we study have a promise, and if the promise is satisfied the problem has a unique solution.

For example, in the Contraction problem, we are given a function $f:^{d}\rightarrow^{d}$ that is promised to be contracting, meaning that $d(f(x),f(y))\leq c\cdot f(x,y)$ for some positive constant $c<1$ and some distance metric $d$. We cannot efficiently check whether $f$ is actually contracting, but if it is, then Banach’s fixpoint theorem states that $f$ has a unique fixpoint . If $f$ is not contracting, then there will exist violations that can be witnessed by short certificates. For Contraction, a violation is any pair of points $x,y$ such that $d(f(x),f(y))>c\cdot f(x,y)$.

We can use violations to formulate the problem as a non-promise problem that lies in TFNP. Specifically, if we ask for either a fixpoint or a violation of contraction, then the contraction problem is total, because if there is no fixpoint, then the contrapositive of Banach’s theorem implies that there must exist a violation of contraction.

Unique End of Potential Line.

When we place this type of problem in $\mathsf{EOPL}$, we obtain an instance with extra properties. Specifically, if the original problem has no violations, meaning that the promise is satisfied, then the EndOfPotentialLine instance will contain a single line that starts at $0^{n}$, and ends at the unique solution of the original problem. This means that, if we ever find two distinct lines in our EndOfPotentialLine instance, then we immediately know that original instance fails to satisfy the promise.

We define the following problem, which is intended to capture these properties.

Given Boolean circuits $S,P:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $P(0^{n})=0^{n}\neq S(0^{n})$ and a Boolean circuit $V:\left\{0,1\right\}^{n}\to\left\{0,1,\dotsc,2^{m}-1\right\}$ such that $V(0^{n})=0$ find one of the following:

A point $x\in\left\{0,1\right\}^{n}$ such that $P(S(x))\neq x$.

A point $x\in\left\{0,1\right\}^{n}$ such that $x\neq S(x)$, $P(S(x))=x$, and $V(S(x))-V(x)\leq 0$.

A point $x\in\left\{0,1\right\}^{n}$ such that $S(P(x))\neq x\neq 0^{n}$.

Two points $x,y\in\left\{0,1\right\}^{n}$, such that $x\neq y$, $x\neq S(x)$, $y\neq S(y)$, and either $V(x)=V(y)$ or $V(x)<V(y)<S(x)$.

We split the solutions into two types: proper solutions and violations. Solutions of type (U1) encode the end of any line, which are the proper solutions to the problem. There are three types of violation solution. Violations of type (UV1) are vertices at which the potential fails to strictly increase. Violations of type (UV2) ask for the start of any line, other than the vertex $0^{n}$. Clearly, if there are two sources in the graph, then there are two lines.

Violations of type (UV3) give another witness that the instance contains more than one line. This is encoded by a pair of vertices $x$ and $y$, with either $V(x)=V(y)$, or with the property that the potential of $y$ lies between the potential of $x$ and $S(x)$. Since we require the potential to strictly increase along every edge of a line, this means that $y$ cannot lie on the same line as $x$, since all vertices before $x$ in the line have potential strictly less than $V(x)$, while all vertices after $S(x)$ have potential strictly greater than $V(S(x))$.

We remark that (UV2) by itself already captures the property “there is a unique line”, since if a second line cannot start, then it cannot exist. So why do we insist on the extra type of violation given by (UV3)? Violations of type (UV3) allow us to solve the problem immediately if we ever detect the existence of multiple lines. Note that this is not the case if we only have solutions of type (UV2), since we may find two vertices on two different lines, but both of them may be exponentially many steps away from the start of their respective lines.

By adding (UV3) solutions, we make the problem easier than EndOfPotentialLine (note that without UV3, the problem is actually the same as EndOfPotentialLine). This means that problems that can be reduced to UniqueEOPL have the very special property that, if at any point you detect the existence of multiple lines, either through the start of a second line, or through a violation in (UV3), then you immediately get a violation in the original problem without any extra effort. All of the problems that we study in this paper share this property.

The complexity class 𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫\mathsf{UniqueEOPL}.

We define the complexity class $\mathsf{UniqueEOPL}$ to be the class of problems that can be reduced in polynomial time to UniqueEOPL. We note that $\mathsf{UniqueEOPL}\subseteq\mathsf{EOPL}$ is trivial, since the problem remains total even if we disallow solutions of type UV3.

For each of our problems, it is also interesting to consider the complexity of the promise variant, in which it is guaranteed via a promise that no violations exist. We define PromiseUniqueEOPL to be the promise version of UniqueEOPL in which $0^{n}$ is the only start of a line (and hence there are no solutions that are type (UV2) or (UV3)). We define the complexity class $\mathsf{PromiseUEOPL}$ to be the class of promise problems that can be reduced in polynomial time to PromiseUniqueEOPL.

Promise-preserving reductions.

The problem UniqueEOPL has the interesting property that, if it is promised that there are no violation solutions, then there must be a unique solution. All of the problems that we study in this paper share this property, and indeed when when we reduce them to UniqueEOPL, the resulting instance will have a unique line whenever the original problem has no violation solutions.

We formalise this by defining the concept of a promise-preserving reduction. This is a reduction between two problems A and B, both of which have proper solutions and violation solutions. The reduction is promise-preserving if, when it is promised that A has no violations, then the resulting instance of B also has no violations. Hence, if we reduce a problem to UniqueEOPL via a chain of promise-preserving reductions, and we know that there are no violations in the original problem, then there is a unique line ending at the unique proper solution in the UniqueEOPL instance.

Note that this is more restrictive than a general reduction. We could in principle produce a reduction that took an instance of A, where it is promised that there are no violations, and produce an instance of B that sometimes contains violations. By using promise-preserving reductions, we are showing that our problems have the natural properties that one would expect for a problem in $\mathsf{UniqueEOPL}$. Specifically, that the promise version has a unique solution, and that this can be found by following the unique line in the UniqueEOPL instance.

One added bonus is that, if we show that a problem is in $\mathsf{UniqueEOPL}$ via a chain of promise-preserving reductions, then we automatically get that the promise version of that problem, where it is promised that there are no violations, lies in $\mathsf{PromiseUEOPL}$. Moreover, if we show that a problem is $\mathsf{UniqueEOPL}$-complete via a promise-preserving reduction, then this also implies that the promise version of that problem is $\mathsf{PromiseUEOPL}$-complete.

One-Permutation Discrete Contraction

The One-Permutation Discrete Contraction (OPDC) problem will play a crucial role in our results. We will show that the problem lies in $\mathsf{UniqueEOPL}$, and we will then reduce both PL-Contraction and Grid-USO to OPDC, thereby showing that those problems also lie in $\mathsf{UniqueEOPL}$. We will also show that UniqueEOPL can be reduced to OPDC, making this problem the first example of a non-trivial $\mathsf{UniqueEOPL}$-complete problem.

The OPDC can be seen as a discrete variant of the continuous contraction problem. Recall that a contraction map is a function $f:^{n}\rightarrow^{d}$ that is contracting under a metric $d$, i.e., $d(f(x),f(y))\leq c\cdot f(x,y)$ for all $x,y\in^{d}$ and some constant $c$ satisfying $0<c<1$.

We will discretize the space by overlaying a grid of points on the $^{d}$ cube. Let $[k]$ denote the set $\{0,1,\dots,k\}$. Given a tuple of grid widths $(k_{1},k_{2},\dots,k_{d})$, we define the set

We will refer to $P(k_{1},k_{2},\dots,k_{d})$ simply as $P$ when the grid widths are clear from the context. Note that each point $p\in P$ is a tuple $(p_{1},p_{2},\dots,p_{d})$, where $p_{i}$ is an integer between and $k_{i}$, and this point maps onto the point $(p_{1}/k_{1},p_{2}/k_{2},\dots,p_{d}/k_{d})\in^{d}$.

Instead of a single function $f$, in the discrete version of the problem we will use a family of direction functions over the grid $P$. For each dimension $i\leq d$, we have function $D_{i}:P\rightarrow\{\mathsf{up},\mathsf{down},\mathsf{zero}\}$. Intuitively, the natural reduction from a contraction map $f$ to a family of direction functions would, for each point $p\in P$ and each dimension $i\leq d$ set:

$D_{i}(p)=\mathsf{up}$ whenever $f(p)_{i}>p_{i}$,

$D_{i}(p)=\mathsf{down}$ whenever $f(p)_{i}<p_{i}$, and

$D_{i}(p)=\mathsf{zero}$ whenever $f(p)_{i}=p_{i}$.

In other words, the function $D_{i}$ simply outputs whether $f(p)$ moves up, down, or not at all in dimension $i$. So a point $p\in P$ with $D_{i}(p)=\mathsf{zero}$ for all $i$ would correspond to the fixpoint of $f$. Note, however, that the grid may not actually contain the fixpoint of $f$, and so there may be no point $p$ satisfying $D_{i}(p)=\mathsf{zero}$ for all $i$.

A two-dimensional example.

To illustrate this definition, consider the two-dimensional instance given in Figure 3, which we will use as a running example. It shows two direction functions: the figure on the left shows a direction function for the up-down dimension, which we will call dimension $1$ and illustrate using the color blue. The figure on the right shows a direction function for the left-right dimension, which we will call dimension $2$ and illustrate using the color red. Each square in the figures represents a point in the discretized space, and the value of the direction function is shown inside the box. Note that there is exactly one point $p$ where $D_{1}(p)=D_{2}(p)=\mathsf{zero}$, which is the fixpoint that we seek.

Slices.

We will frequently refer to subsets of $P$ in which some of the dimensions have been fixed. A slice will be represented as a tuple $(s_{1},s_{2},\dots,s_{d})$, where each $s_{i}$ is either

a number in $$, which indicates that dimension$i$should be fixed to$s_{i}$, or

the special symbol $\mathtt{*}$, which indicates that dimension $i$ is free to vary.

We define $\operatorname{\mathsf{Slice}}_{d}=\left(\cup\left\{\mathtt{*}\right\}\right)^{d}$ to be the set of all possible slices in dimension $d$. Given a slice $s\in\operatorname{\mathsf{Slice}}_{d}$, we define $P_{s}\subseteq P$ to be the set of points in that slice, ie., $P_{s}$ contains every point $p\in P$ such that $p_{i}=s_{i}$ whenever $s_{i}\neq\mathtt{*}$. We’ll say that a slice $s^{\prime}\in\operatorname{\mathsf{Slice}}_{d}$ is a sub-slice of a slice $s\in\operatorname{\mathsf{Slice}}_{d}$ if $s_{j}\neq\mathtt{*}\implies s^{\prime}_{j}=s_{j}$ for all $j\in[d]$.

An $i$-slice is a slice $s$ for which $s_{j}=\mathtt{*}$ for all $j\leq i$, and $s_{j}\neq\mathtt{*}$ for all $j>i$. In other words, all dimensions up to and including dimension $i$ are allowed to vary, while all other dimensions are fixed.

In our two-dimensional example, there are three types of $i$-slices. There is one $2$-slice: the slice $(\mathtt{*},\mathtt{*})$ that contains every point. For each $x$, there is a $1$-slice $(\mathtt{*},x)$, which restricts the left/right dimension to the value $n$. For each pair $x,y$ there is a -slice $(y,x)$, which contains only the exact point corresponding to $x$ and $y$.

Discrete contraction maps.

We can now define a one-permutation discrete contraction map. We say that a point $p\in P_{s}$ in some slice $s$ is a fixpoint of $s$ if $D_{i}(p)=\mathsf{zero}$ for all dimensions $i$ where $s_{i}=\mathtt{*}$. The following definition captures the promise version of the problem, and we will later give a non-promise version by formulating appropriate violations.

Let $P$ be a grid of points over $^{d}$ and let $\mathcal{D}=(D_{i})_{i=1,\dots,d}$ be a family of direction functions over $P$. We say that $\mathcal{D}$ and $P$ form a one-permutation discrete contraction map if, for every $i$-slice $s$, the following conditions hold.

Let $s^{\prime}\in\operatorname{\mathsf{Slice}}_{d}$ be a sub-slice of $s$ where some coordinate $i$ for which $s_{i}=\mathtt{*}$ has been fixed to a value, and all other coordinates are unchanged. If $q$ is the unique fixpoint of $s$, and $p$ is the unique fixpoint of $s^{\prime}$, then

if $p_{i}<q_{i}$, then $D_{i}(p)=\mathsf{up}$, and

if $p_{i}>q_{i}$, then $D_{i}(p)=\mathsf{down}$.

The first condition specifies that each $i$-slice must have a unique fixed point. Since the slice $(\mathtt{*},\mathtt{*},\dots,\mathtt{*})$ is an $i$-slice, this implies that the full problem also has a unique fixpoint.

The second condition is a more technical condition. It tells us that if we have found the unique fixpoint $p$ of the $(i+1)$-slice $s^{\prime}$, and if this point is not the unique fixpoint of the $i$-slice $s$, then the direction function $D_{i}(p)$ tells us which way to walk to find the unique fixpoint of $s$. This is a crucial property that we will use in our reduction from OPDC to UniqueEOPL, and in our algorithms for contraction maps.

In our two-dimensional example, the first condition requires that every slice $(\mathtt{*},x)$ has a unique fixpoint, and this corresponds to saying that for every fixed slice of the left/right dimension, there is a unique blue point that is zero. The second condition requires that, if we are at some blue zero, then the red direction function at that point tells us the direction of the overall fixpoint. It can be seen that our example satisfies both of these requirements.

Note that both properties only consider $i$-slices. In the continuous contraction map problem with an $L_{p}$ norm distance metric, every slice has a unique fixpoint, and so one may expect a discrete version of contraction to share this property. The problem is that the second property is very difficult to prove. Indeed, when we reduce PL-Contraction to OPDC in Section 4.2, we must carefully choose the grid size to ensure that both the first and second properties hold. In fact, our choice of grid size for dimension $i$ will depend on the grid size of dimension $i+1$, which is why our definition only considers $i$-slices.

The name One-Permutation Discrete Contraction was chosen to emphasize this fact. The $i$-slices correspond to restricting dimensions in order, starting with dimension $d$. Since the order of the dimensions is arbitrary, we could have chosen any permutation of the dimensions, but we must choose one of these permutations to define the problem.

The OPDC problem.

The OPDC problem is as follows: given a discrete contraction map $\mathcal{D}=(D_{i}(p))_{i=1,\dots,d}$, find the unique point $p$ such that $D_{i}(p)=\mathsf{zero}$ for all $i$. Note that we cannot efficiently verify whether $\mathcal{D}$ is actually a one-permutation discrete contraction map.

So, the OPDC problem is a promise problem, and we will formulate a total variant of it that uses a set of violations to cover the cases where $\mathcal{D}$ fails to be a discrete contraction map.

Given a tuple $(k_{1},k_{2},\dots,k_{d})$ and circuits $(D_{i}(p))_{i=1,\dots,d}$, where each circuit $D_{i}:P(k_{1},k_{2},\dots,k_{d})\rightarrow\{\mathsf{up},\mathsf{down},\mathsf{zero}\}$, find one of the following

A point $p\in P$ such that $D_{i}(p)=\mathsf{zero}$ for all $i$.

An $i$-slice $s$ and two points $p,q\in P_{s}$ with $p\neq q$ such that $D_{j}(p)=D_{j}(q)=\mathsf{zero}$ for all $j\leq i$.

An $i$-slice $s$ and two points $p,q\in P_{s}$ such that

$D_{j}(p)=D_{j}(q)=\mathsf{zero}$ for all $j<i$,

$D_{i}(p)=\mathsf{down}$ and $D_{i}(q)=\mathsf{up}$.

An $i$-slice $s$ and a point $p\in P_{s}$ such that

$D_{j}(p)=D_{j}(q)=\mathsf{zero}$ for all $j<i$, and either

$p_{i}=0$ and $D_{i}(p)=\mathsf{down}$, or

$p_{i}=k_{i}$ and $D_{i}(p)=\mathsf{up}$.

Solution type (O1) encodes a fixpoint, which is the proper solution of the discrete contraction map, while solution types (OV1) through (OV3) encode violations of the discrete contraction map property.

Solution type (OV1) witnesses a violation of the first property of a discrete contraction map, namely that each $i$-slice should have a unique fixpoint. A solution of type (OV1) gives two different points $p$ and $q$ in the same $i$-slice that are both fixpoints of that slice.

Solutions of type (OV2) witness violations of the first and second properties of a discrete contraction map. In these solutions we have two points $p$ and $q$ that are both fixpoints of their respective $(i-1)$-slices and are directly adjacent in an $i$-slice $s$. If there is a fixpoint $r$ of the slice $s$, then this witnesses a violation of the second property of a discrete contraction map, which states that $D_{i}(p)$ and $D_{i}(q)$ should both point towards $r$, and clearly one of them does not. On the other hand, if slice $s$ has no fixpoint, then $p$ and $q$ also witness this fact, since the fixpoint should be in-between $p$ and $q$, which is not possible.

Solutions of type (OV3) consist of a point $p$ that is a fixpoint of its $(i-1)$-slice but $D_{i}(p)$ points outside the boundary of the grid. These are clear violations of the second property, since $D_{i}(p)$ should point towards the fixpoint of the $i$-slice containing $p$, but that fixpoint cannot be outside the grid.

It is perhaps not immediately obvious that OPDC is a total problem. Ultimately we will prove this fact in the next section by providing a promise-preserving reducing from OPDC to UniqueEOPL. This will give us a proof of totality, and will also prove that, if the discrete contraction map has no violations, then it does indeed have a unique solution.

1 One-Permutation Discrete Contraction is in 𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫\mathsf{UniqueEOPL}

In this section, we will show that One-Permutation Discrete Contraction lies in $\mathsf{UniqueEOPL}$ under promise-preserving reductions.

Our reduction will make use of an intermediate problem that we call unique forward EOPL, which is a version of UniqueEOPL in which we only have a successor circuit $S$, meaning that no predecessor circuit $P$ is given.

Given a Boolean circuits $S:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $S(0^{n})\neq 0^{n}$ and a Boolean circuit $V:\left\{0,1\right\}^{n}\to\left\{0,1,\dotsc,2^{m}-1\right\}$ such that $V(0^{n})=0$ find one of the following:

A point $x\in\left\{0,1\right\}^{n}$ such that $S(x)\neq x$ and either $S(S(x))=S(x)$ or $V(S(x))\leq V(x)$.

Two points $x,y\in\left\{0,1\right\}^{n}$, such that $x\neq y$, $x\neq S(x)$, $y\neq S(y)$, and either $V(x)=V(y)$ or $V(x)<V(y)<V(S(x))$.

Without the predecessor circuit, this problem bears more resemblance to SinkOfDag than to EndOfPotentialLine. As in SinkOfDag, a bit-string $x$ encodes a vertex if and only if $S(x)\neq x$, and an edge exists between vertices $x$ and $y$ if and only if $S(x)=y$ and $V(x)<V(y)$. The proper solution type (UF1) asks us to find a vertex that is a sink of the DAG, just as before.

The difference lies in the violation solution type (UFV1), which is the same as violation type (UV3) of UniqueEOPL. It asks for two vertices $x$ and $y$ that either have the same potential, or for which the potential of $y$ lies strictly between the potential of $x$ and the potential of $S(x)$. Note that this restriction severely constrains a SinkOfDag instance: if there are no violation solutions, then the DAG must consist of a single line that starts at $0^{n}$, and ends at the unique solution of type (UF1). So in this sense, the problem really does capture instances of UniqueEOPL that lack a predecessor circuit.

The UniqueForwardEOPL problem will play a crucial role in our reduction. We will reduce OPDC to it, and we will then reduce it to UniqueEOPL.

An illustration of the reduction.

Before we discuss the formal definition of the construction, we first give some intuition by describing the reduction for the two-dimensional example shown in Figure 3.

The reduction uses the notion of a surface. On the left side in Figure 4, we have overlaid the surfaces of the two direction functions from Figure 3. The surface of a direction function $D_{i}$ is exactly the set of points $p\in P$ such that $D_{i}(p)=\mathsf{zero}$. The fixpoint $p$ that we seek has $D_{i}(p)=\mathsf{zero}$ for all dimensions $i$, and so it lies at the intersection of these surfaces.

To reach the overall fixpoint, we walk along a path starting from the bottom-left corner, which is shown on the right-hand side of Figure 4. The path begins by walking upwards until it finds the blue surface. Once it has found the blue surface, it then there are two possibilities: either we have found the overall fixpoint, in which case the line ends, or we have not found the overall fixpoint, and the red direction function tells us that the direction of the overall fixpoint is to the right.

If we have not found the overall fixpoint, then we move one step to the right, go back to the bottom of the diagram, and start walking upwards again. We keep repeating this until we find the overall fixpoint. This procedure gives us the line shown on the right-hand side of Figure 4.

The potential.

How do we define a potential for this line? Observe that the dimension-two coordinates of the points on the line are weakly monotone, meaning that the line never moves to the left. Furthermore, for any dimension-two slice (meaning any slice in which the left/right coordinate is fixed), the dimension-one coordinate is monotonically increasing. So, if $p=(p_{1},p_{2})$ denotes any point on the line, if $k$ denotes the maximum coordinate in either dimension, then the function

is a function that monotonically increases along the line, which we can use as a potential function.

Uniqueness.

To provide a promise-preserving reduction to UFEOPL, we must argue that the line is unique whenever the OPDC instance has no violations. Here we must carefully define what exactly a vertex on the line actually is, to ensure that no other line can exist. Specifically, we must be careful that only points that are to the left of the fixpoint are actually on the line, and that no “false” line exists to the right of the fixpoint.

Here we rely on the following fact: if the line visits a point with coordinate $x$ in dimension $2$, then it must have visited the point $p$ on the blue surface in the slice defined by $x-1$. Moreover, for that point $p$ we must have $D_{2}(p)=\mathsf{up}$, which means that it is to the left of the overall fixpoint.

Using this fact, each vertex on our line will be a pair $(p,q)$, where $p$ is the current point that we are visiting, and $q$ is either

the symbol $\mathtt{-}$, indicating that we are still in the first column of points, and we have never visited a point on the blue surface, or

a point $q$ that is on the blue surface, that satisfies $q_{2}=p_{2}-1$ and $D_{2}(q)=\mathsf{up}$.

Hence the point $q$ is always the last point that we visited on the blue surface, which provides a witness that we have not yet walked past the overall fixpoint.

When we finish walking up a column of points, and find the point on the blue surface, we overwrite $q$ with the new point that we have found. This step is the reason why only a successor circuit can be given for the line, since the value that is overwritten cannot easily be computed by a predecessor circuit.

Violations.

Our two-dimensional OPDC example does not contain any violations, but our reduction can still handle all possible violations in the OPDC instance. At a high level, there are two possible ways in which the reduction can go wrong if there are violations.

It is possible, that as we walk upwards in some column, we do not find a fixpoint, and our line will get stuck. This creates an end of line solution of type (UF1), which must be mapped back to an OPDC violation. In our two-dimensional example, this case corresponds to a column of points in which there is no point on the blue surface. However, if there is no point on the blue surface, then we will either

find two adjacent points $p$ and $q$ in that column with $D_{1}(p)=\mathsf{up}$ and $D_{2}(p)=\mathsf{down}$, which is a solution of type (OV2), or

find a point $p$ at the top of the column with $D_{1}(p)=\mathsf{up}$, or a point $q$ at the bottom of the column with $D_{1}(q)=\mathsf{down}$. Both of these are solutions of type (OV3).

There is also the similar case where we walk all the way to the right without finding an overall fixpoint, in which case we will find a point $p$ on the right-hand boundary that satisfies $D_{1}(p)=\mathsf{zero}$ and $D_{2}(p)=\mathsf{up}$, which is a solution of type (OV3).

The other possibility is that there may be more than one point on the blue surface in some of the columns. This will inevitably lead to multiple lines, since if $q$ and $q^{\prime}$ are both points on the blue surface in some column, and $p$ is some point in the column to the right of $p$ and $q$, then $(p,q)$ and $(p,q^{\prime})$ will both be valid vertices on two different lines.

These can show up as violations of type (UFV1), which we map back to solutions of type (OV1). Specifically, the points $p$ and $q$, which are given as part of the two vertices, are both fixpoints of the same slice, which is exactly what (OV1) asks for.

We can argue that our reduction is promise-preserving. This is because violation solutions in the UFEOPL instance are never mapped back to proper solutions of the OPDC instance. This means that, if we promise that the OPDC instance has no violations, then the resulting UFEOPL instance must also contain no violations.

The full reduction.

Our reduction from OPDC to UniqueForwardEOPL generalizes the approach given above to $d$ dimensions. We say that a point $p\in P$ is on the $i$-surface if $D_{j}(p)=\mathsf{zero}$ for all $j\leq i$. In our two-dimensional example we followed a line of points on the one-surface, in order to find a point on the two-surface. In between any two points on the one-surface, we followed a line of points on the zero-surface (every point is trivially on the zero-surface).

Our line will visit a sequence of points on the $(d-1)$-surface in order to find the point on the $d$-surface, which is the fixpoint. Between any two points on the $(d-1)$-surface the line visits a sequence of points on the $(d-2)$-surface, between any two points on the $(d-2)$-surface the line visits a sequence of points on the $(d-3)$-surface, and so on.

The line will follow the same pattern that we laid out in two dimensions. Every time we find a point on the $i$-surface, we remember it, increment our position in dimension $i$ by $1$, and reset our coordinates back to for all dimensions $j<i$. Hence, a vertex will be a tuple $(p_{0},p_{1},\dots,p_{d})$, where each $p_{i}$ is either

the symbol $\mathtt{-}$, indicating that we have not yet encountered a point on the $i$-surface, or

the most recent point on the $i$-surface that we have visited.

This is a generalization of the witnessing scheme that we saw in two-dimensions.

The potential is likewise generalized so that the potential of a point $p$ is proportional to $\sum_{i=1}^{d}k^{i}p_{i}$, where again $k$ is some constant that is larger than the grid size. This means that progress in dimension $i$ dominates progress in dimension $j$ whenever $j<i$, which allows the potential to monotonically increase along the line.

We are also able to deal with all possible violations, using the ideas that we have described in two-dimensional case. Full details of this construction are given in Appendix B.1, where the following lemma is proved.

There is a polynomial-time promise-preserving reduction from OPDC to UniqueForwardEOPL.

From UniqueForwardEOPL to UniqueForwardEOPL+1.

The next step of the reduction is to slightly modify the UniqueForwardEOPL instance, so that the potential increases by exactly one in each step. Specifically we define the following problem

Given a Boolean circuits $S:\left\{0,1\right\}^{n}\to\left\{0,1\right\}^{n}$ such that $S(0^{n})\neq 0^{n}$ and a Boolean circuit $V:\left\{0,1\right\}^{n}\to\left\{0,1,\dotsc,2^{m}-1\right\}$ such that $V(0^{n})=0$ find one of the following:

A point $x\in\left\{0,1\right\}^{n}$ such that $S(x)\neq x$ and either $S(S(x))=S(x)$ or $V(S(x))\neq V(x)+1$.

Two points $x,y\in\left\{0,1\right\}^{n}$, such that $x\neq y$, $x\neq S(x)$, $y\neq S(y)$, and $V(x)=V(y)$.

There are two differences between this problem and UniqueForwardEOPL. Firstly, an edge exists between $x$ and $y$ if and only if $S(x)=y$, and $V(y)=V(x)+1$, and this is reflected in the modified definition of solution type (UFP1). Secondly, solution type (UFPV1) has been modified to only cover the case where we have two vertices $x$ and $y$ that have the same potential. The case where $V(x)<V(y)<V(S(x))$ is not covered, since in this setting this would imply $V(S(x))>V(x)+1$, which already gives us a solution of type (UFP1).

It is not difficult to reduce UniqueForwardEOPL to UniqueForwardEOPL+1, using the same techniques that we used in the reduction from EndOfPotentialLine to EndOfMeteredLine in Theorem 10. This gives us the following lemma, which is proved in Appendix B.2.

There is a polynomial-time promise-preserving reduction from UniqueForwardEOPL to UniqueForwardEOPL+1.

UniqueForwardEOPL+1 to UniqueEOPL.

The final step of the proof is to reduce UniqueForwardEOPL to UniqueEOPL. For this, we are able to build upon existing work. The following problem was introduced by Bitansky et al .

The input to the problem consists of a starting vertex $x_{s}\in\{0,1\}^{n}$, a target integer $T\leq 2^{n}$, and two boolean circuits $S:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$, $W:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$. It is promised that, for every vertex $x\in\{0,1\}^{n}$, and every integer $i\leq T$, we have $W(x,i)=1$ if and only if $x=S^{i-1}(x_{s})$. The goal is to find the vertex $x_{f}\in\{0,1\}^{n}$ such that $W(x_{f},T)=1$.

SinkOfVerifiableLine is intuitively very similar to UniqueForwardEOPL. In this problem, a single line is encoded, where as usual the vertices are encoded as bit-strings, and the circuit $S$ gives the successor of each vertex. The difference in this problem is that the circuit $W$ gives a way of verifying how far along the line a given vertex is. Specifically, $W(x,i)=1$ if and only if $x$ is the $i$th vertex on the line. Note that this is inherently a promise problem, since if $W(x,i)=1$ for some $i$, we have no way of knowing whether $x$ is actually $i$ steps along the line, without walking all of those steps ourselves.

It was shown by Hubáček and Yogev that SinkOfVerifiableLine can be reduced in polynomial time to EndOfMeteredLine, and hence also to EndOfPotentialLine (via Theorem 10). Moreover, the resulting EndOfPotentialLine instance has a unique line, so this reduction also reduces SinkOfVerifiableLine to UniqueEOPL. It is easy to reduce the promise version of UniqueForwardEOPL+1 to SinkOfVerifiableLine, since we can implement the circuit $W$ so that $W(x,i)=1$ if and only if $V(x)=i$.

However, the existing work only deals with the promise problem. Our contribution is to deal with violations. We show that, if one creates a SinkOfVerifiableLine instance from a UniqueForwardEOPL+1 instance, in the way described above, and applies the reduction of Hubáček and Yogev to produce a UniqueEOPL instance, then any violation can be mapped back to a solution in the original UniqueForwardEOPL+1 instance. Hence, we show the following lemma, whose full proof appears in Appendix B.3.

There is a polynomial-time promise-preserving reduction from UniqueForwardEOPL to $\mathsf{UniqueEOPL}$.

This completes the chain of promise-preserving reductions from OPDC to UniqueEOPL. Hence, we have shown the following theorem.

OPDC is in $\mathsf{UniqueEOPL}$ under polynomial-time promise-preserving reductions.

2 One-Permutation Discrete Contraction is 𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫𝖴𝗇𝗂𝗊𝗎𝖾𝖤𝖮𝖯𝖫\mathsf{UniqueEOPL}-hard

In this section we will show that One-Permutation Discrete Contraction is $\mathsf{UniqueEOPL}$-complete, by giving a hardness result. Specifically, we give a reduction from UniqueEOPL to OPDC.

The first step of the reduction is to slightly alter the UniqueEOPL instance. Specifically, we would like to ensure the following two properties.

Every edge increases the potential by exactly one. That is, $V(S(x))=V(x)+1$ for every vertex $x$.

The line has length exactly $2^{n}$ for some integer $n$. More specifically, we ensure that if $x$ is the end of any line then we have $V(x)=2^{n}-1$. The start of the line given in the problem has potential , this ensures that the length of that line is exactly $2^{n}$, although other lines may be shorter.

We have already developed a technique for ensuring the first property in the reduction from EOPL to EOML in Theorem 10, which can be reused here. Specifically, we introduce a chain of dummy vertices between any pair of vertices $x$ and $y$ with $S(x)=y$ and $V(y)>V(x)+1$. The second property can be ensured by choosing $n$ so that $2^{n}$ is larger than the longest possible line in the instance. Then, at every vertex $x$ that is the end of a line, we introduce a chain of dummy vertices