The Classes PPA-$k$: Existence from Arguments Modulo $k$

Introduction

The complexity class TFNP is the class of all search problems such that every instance has a least one solution and any solution can be checked in polynomial time. It has attracted a lot of interest, because, in some sense, it lies between P and NP. Moreover, TFNP contains many natural problems for which no polynomial-time algorithm is known, such as Factoring (given a integer, find a prime factor) or Nash (given a bimatrix game, find a Nash equilibrium). However, no problem in TFNP can be NP-hard, unless NP $=$ co-NP . Furthermore, it is believed that no TFNP-complete problem exists . Thus, the challenge is to find some way to provide evidence that these TFNP problems are indeed hard.

Papadimitriou proposed the following idea: define subclasses of TFNP and classify the natural problems of interest with respect to these classes. Proving that many natural problems are complete for such a class, shows that they are “equally” hard. Then, investigating how these classes relate to each other, yields a relative classification of all these problems. In other words, it provides a unified framework that gives a better understanding of how these problems relate to each other. TFNP subclasses are based on various non-constructive existence results. Some of these classes and their corresponding existence principle are:

PPAD : given a directed graph and an unbalanced vertex (i.e., out-degree $\neq$ in-degree), there must exist another unbalanced vertex.

PPA : given an undirected graph and vertex with odd degree, there must exist another vertex with odd degree (Handshaking Lemma).

PPP : given a function mapping a finite set to a smaller set, there must exist a collision (Pigeonhole Principle).

Other TFNP subclasses are PPADS, PLS , CLS , PTFNP , EOPL and UEOPL . It is known that $\textup{PPAD}\subseteq\textup{PPADS}\subseteq\textup{PPP}$, $\textup{PPAD}\subseteq\textup{PPA}$ and $\textup{UEOPL}\subseteq\textup{EOPL}\subseteq\textup{CLS}\subseteq\textup{PPAD}\cap\textup{PLS}$. Very recently it was shown that in fact $\textup{CLS}=\textup{PPAD}\cap\textup{PLS}$ . Any separation between TFNP subclasses would imply P $\neq$ NP, but various oracle separations exist (see Section 2 for more details).

TFNP subclasses have been very successful in capturing the complexity of natural problems. The most famous result is that the problem Nash is PPAD-complete , but various other natural problems have also been shown PPAD-complete . Many local optimisation problems have been proved PLS-complete . Recently, the first natural complete problems were found for PPA and PPP . The famous Factoring problem has been partially related to PPA and PPP .

The natural problem recently shown PPA-complete is a problem in fair division, called the $2$-Necklace-Splitting problem . For $k\geq 2$, the premise of the $k$-Necklace-Splitting problem is as follows. Imagine that $k$ thieves have stolen a necklace that has beads of different colours. Since the thieves are unsure of the value of the different beads, they want to divide the necklace into $k$ parts such that each part contains the same number of beads of each colour. However, the string of the necklace is made of precious metal, so the thieves don’t want to use too many cuts. Alon’s famous result says that this can always be achieved with a limited number of cuts.

The corresponding computational problem can be described as follows. We are given an open necklace (i.e., a segment) with $n$ beads of $c$ different colours, i.e., there are $a_{i}$ beads of colour $i$ and $\sum_{i=1}^{c}a_{i}=n$. Furthermore, assume that for each $i$, $a_{i}$ is divisible by $k$ (the number of thieves). The goal is to cut the necklace in (at most) $c(k-1)$ places and allocate the pieces to the $k$ thieves, such that every thief gets exactly $a_{i}/k$ beads of colour $i$, for each colour $i$. By Alon’s result , a solution always exists, and thus the problem lies in TFNP.

The complexity of this problem has been an open problem for almost 30 years . While the 2-thieves version is now resolved, the complexity of the problem with $k$ thieves ($k\geq 3$) remains open. The main motivation of the present paper is to investigate the classes PPA-$k$, which are believed to be the most likely candidates to capture the complexity of $k$-Necklace-Splitting. Indeed, in the conclusion of the paper where they prove that $2$-Necklace-Splitting is PPA-complete, Filos-Ratsikas and Goldberg [18, arXiv version] mention:

“What is the computational complexity of $k$-thief Necklace-splitting, for $k$ not a power of 2? As discussed in , the proof that it is a total search problem, does not seem to boil down to the PPA principle. Right now, we do not even know if it belongs to PTFNP .

Interestingly, Papadimitriou in (implicitly) also defined a number of computational complexity classes related to PPA, namely PPA-$p$, for a parameter $p\geq 2$. […] Given the discussion above, it could possibly be the case that the principle associated with Necklace-Splitting for $k$-thieves is the PPA-$k$ principle instead.”

PPA-p𝑝p.

The TFNP subclasses PPA-$p$ were defined by Papadimitriou almost 30 years ago in his seminal paper . Recall that the existence of a solution to a PPA problem is guaranteed by a parity argument, i.e., an argument modulo $2$. The classes PPA-$p$ are a generalisation of this. For every prime $p$, the existence of a solution to a PPA-$p$ problem is guaranteed by an argument modulo $p$. In particular, \textup{PPA-2}=\textup{PPA}. Surprisingly, these classes have received very little attention. As far as we know, they have only been studied in the following:

Papadimitriou defined the classes PPA-$p$ and proved that a problem called Chevalley-mod-$p$ lies in PPA-$p$ and a problem called Cubic-Subgraph lies in PPA-$3$.

In an online thread on Stack Exchange , Jeřábek provided two other equivalent ways to define PPA-$3$. The problems and proofs can be generalised to any prime $p$.

In his thesis , Johnson defined the classes $\text{PMOD}^{k}$ for any $k\geq 2$, which were intended to capture the complexity of counting arguments modulo $k$. He proved various oracle separation results involving his classes and other TFNP classes. While the PPA-$p$ classes are not mentioned by Johnson, using Jeřábek’s results it is easy to show that \textup{\text{PMOD}^{p}}=\textup{PPA-p} for any prime $p$. In Section 6, we characterise $\text{PMOD}^{k}$ in terms of the classes PPA-$p$ when $k$ is not prime. In particular, we show that $\text{PMOD}^{k}$ only partially captures existence arguments modulo $k$.

Our contribution.

Finally, in Section 6 we investigate the classes $\text{PMOD}^{k}$ defined by Johnson and provide a full characterisation in terms of the classes PPA-$k$. In particular, we show that \textup{\text{PMOD}^{k}}=\textup{PPA-k} if $k$ is a prime power. However, when $k$ is not a prime power, we provide evidence that $\text{PMOD}^{k}$ does not capture the full strength of existence arguments modulo $k$, unlike PPA-$k$. This characterisation of $\text{PMOD}^{k}$ in terms of PPA-$k$ leads to some oracle separation results involving PPA-$k$ and other TFNP classes (using Johnson’s oracle separation results).

We note that a significant fraction of our results were also obtained by Göös, Kamath, Sotiraki and Zampetakis in concurrent and independent work . In their work, they have also provided the first “natural” complete problem for the classes PPA-$p$ (a variant of Chevalley-mod-$p$), namely the first complete problem that does not involve circuits or other computational devices in its description. The present work, and in particular the equivalent characterisations of the classes PPA-$k$, have been pivotal in subsequent work showing that the $k$-Necklace-Splitting problem lies in PPA-$k$ under Turing reductions. However, the question of whether $k$-Necklace-Splitting is also PPA-$k$-hard remains open.

Preliminaries

Let $\{0,1\}^{*}$ denote the set of all finite length bit-strings and for $w\in\{0,1\}^{*}$ let $|w|$ be its length. A computational search problem is given by a binary relation $R\subseteq\{0,1\}^{*}\times\{0,1\}^{*}$. The problem is: given an instance $I\in\{0,1\}^{*}$, find an $s\in\{0,1\}^{*}$ such that $(I,s)\in R$, or return that no such $s$ exists. The search problem $R$ is in FNP (Functions in NP), if $R$ is polynomial-time computable (i.e., $(I,s)\in R$ can be decided in polynomial time in $|I|+|s|$) and there exists some polynomial $p$ such that $(I,s)\in R\implies|s|\leq p(|I|)$. Thus, FNP is the search problem version of NP (and FNP-complete problems are equivalent to NP-complete problems under Turing reductions).

The class TFNP (Total Functions in NP ) contains all FNP search problems $R$ that are total: for every $I\in\{0,1\}^{*}$ there exists $s\in\{0,1\}^{*}$ such that $(I,s)\in R$. With a slight abuse of notation, we can say that P lies in TFNP. Indeed, if a decision problem is solvable in polynomial time, then both the “yes” and “no” answers can be verified in polynomial time. In this sense, TFNP lies between P and NP.

Note that TFNP problems are not promise problems, i.e., we are not allowed to restrict the instance space $\{0,1\}^{*}$. This means that for any instance in $\{0,1\}^{*}$, there must always exist at least one solution. Nevertheless, TFNP can indirectly capture various settings where the instance space is restricted. For example, if a problem $R$ in FNP is total only on a subset $L$ of the instances and $L\in P$, then we can transform it into an equivalent TFNP problem by adding $(I,0)$ to $R$ for all instances $I\notin L$.

Reductions.

Let $R$ and $S$ be total search problems in TFNP. We say that $R$ (many-one) reduces to $S$, denoted $R\leq S$, if there exist polynomial-time computable functions $f,g$ such that

Note that if $S$ is polynomial-time solvable, then so is $R$. We say that two problems $R$ and $S$ are (polynomial-time) equivalent, if $R\leq S$ and $S\leq R$.

There is also a more general type of reduction. A Turing reduction from $R$ to $S$ is a polynomial-time oracle Turing machine that solves problem $R$ with the help of queries to an oracle for $S$. Note that a Turing reduction that only makes a single oracle query immediately yields a many-one reduction.

Encoding of Sets.

PPA.

The class PPA (Polynomial Parity Argument) is defined as the set of all TFNP problems that many-one reduce to the problem Leaf : given an undirected graph with maximum degree 2 and a leaf (i.e., a vertex of degree 1), find another leaf. The important thing to note is that the graph is not given explicitly (in which case the problem would be very easy), but it is provided implicitly through a succinct representation.

The vertex set is $\{0,1\}^{n}$ and the undirected graph is represented by a Boolean circuit $C:\{0,1\}^{n}\to\textsf{Set}_{\leq 2}(\{0,1\}^{n})$. By this we mean that for any $x\in\{0,1\}^{n}$, we interpret $C(x)$ as the set of potential neighbours of $x$, where we syntactically enforce that $x\notin C(x)$. We say that there is an edge between $x$ and $y$ if $x\in C(y)$ and $y\in C(x)$. Thus, every vertex has at most two neighbours. Note that the size of the graph can be exponential with respect to its description size.

The full formal definition of the problem Leaf is: given a Boolean circuit $C:\{0,1\}^{n}\to\textsf{Set}_{\leq 2}(\{0,1\}^{n})$ representing an undirected graph on the vertex set $\{0,1\}^{n}$ such that $|C(0^{n})|=1$ (i.e., $0^{n}$ is a leaf), find

$x\neq 0^{n}$ such that $|C(x)|=1$ (another leaf)

or $x,y$ such that $x\in C(y)$ but $y\notin C(x)$ (an inconsistent edge)

Type 2 Problems and Oracle Separations.

We work in the standard Turing machine model, but TFNP subclasses have also been studied in the black-box model. In this model, one considers the type 2 versions of the problems, namely, the circuits in the input are replaced by black-boxes. In that case, it is possible to prove unconditional separations between type 2 TFNP subclasses (in the standard model this would imply P $\neq$ NP). The interesting point here is that separations between type 2 classes yield separations of the corresponding classes in the standard model with respect to any generic oracle (see for more details on this). This technique has been used to prove various oracle separations between TFNP subclasses . In Section 6 we provide some oracle separations involving PPA-$k$ and other TFNP subclasses.

On the other hand, any reduction that works in the type 2 setting, also works in the standard setting. Indeed, it suffices to replace the calls to the black boxes by the corresponding circuits that compute them. In this paper, our reductions are stated in the standard model, but they also work in the type 2 setting, because they don’t examine the inner workings of the circuits.

Definition of the Classes

For any prime $p$, Papadimitriou defined the class PPA-$p$ as the set of all TFNP problems that many-one reduce to the following problem, that we call Bipartite-mod-$p$: We are given an undirected bipartite graph (implicitly represented by a circuit) and a vertex with degree $\neq 0\mod p$ (which we call the trivial solution). The goal is to find another such vertex. This problem lies in TFNP: if all other vertices had degree $=0\mod p$, then the sum of the degrees of all vertices on each side would have a different value modulo $p$, which is impossible.

The problem remains well-defined and total if $p$ is not a prime, and so we will instead define it for any $k\geq 2$. Let us now provide a formal definition of the problem. A vertex of the bipartite graph is represented as a bit-string in $\{0,1\}\times\{0,1\}^{n}$, where the first bit indicates whether the vertex lies on the “left” or “right” side of the bipartite graph. The graph will be represented by a Boolean circuit that outputs a set of potential neighbours, just as we did for Leaf. Instead of at most two neighbours, here we allow at most $k$ neighbours (see Remark 1 for why this is enough). Note that we can syntactically enforce that the graph is bipartite, i.e., that a vertex $0x$ can only have neighbours of the type $1y$ and vice versa.

Let $k\geq 2$. The problem Bipartite-mod-$k$ is defined as: given a Boolean circuit $C:\{0,1\}\times\{0,1\}^{n}\to\textsf{Set}_{\leq k}(\{0,1\}\times\{0,1\}^{n})$ representing a bipartite graph on the vertex set $(\{0\}\times\{0,1\}^{n},\{1\}\times\{0,1\}^{n})$ with $|C(00^{n})|\in\{1,\dots,k-1\}$, find

$x\neq 00^{n}$ such that $|C(x)|\notin\{0,k\}$

or $x,y$ such that $y\in C(x)$ but $x\notin C(y)$.

Here the trivial solution is the vertex $00^{n}$. The first type of solution corresponds to a vertex with degree $\neq 0\mod k$. The second type of solution corresponds to an edge that is not well-defined. We can always ensure that all edges are well-defined by doing some pre-processing. Indeed, in polynomial time we can construct a circuit $C^{\prime}$ such that all solutions are of the first type and yield a solution for $C$. On input $0x$ the circuit $C^{\prime}$ first computes $C(0x)=\{1y_{1},\dots,1y_{m}\}$ and then for each $i$ removes $1y_{i}$ from this set, if $0x\notin C(1y_{i})$.

Note that in this problem statement we require that all degrees lie in $\{0,1,\dots,k\}$. This is easily seen to be equivalent to the more general formulation where vertices can have more than $k$ neighbours. Indeed, any vertex that has more than $k$ edges can be split into multiple copies such that all the copies have or $k$ edges, except for one copy which is allowed to have any number of edges in $\{0,1,\dots,k\}$. A solution of the original instance is then easily recovered from a solution of this modified instance. Note that since the set of neighbours is given as the output of a circuit, it will have length bounded by some polynomial in the input size and so this argument can indeed be applied.

For any $k\geq 2$, the class PPA-$k$ is defined as the set of all TFNP problems that many-one reduce to Bipartite-mod-$k$.

Recall that PPA can be defined using the canonical complete problem Leaf : given an undirected graph where every vertex has degree at most 2, and a leaf (i.e., degree $=1$), find another leaf. This immediately yields PPA-$2$ $\subseteq$ PPA, since Bipartite-mod-$2$ is just a special case of Leaf where the graph is bipartite.

Given an instance of Leaf with graph $G=(\{0,1\}^{n},E)$ we construct an instance of Bipartite-mod-$2$ on the vertex set $\{0,1\}\times\{0,1\}^{2n}$ as follows. For any $u\in\{0,1\}^{n}$ we have a vertex $x_{u}:=0u0^{n}$ on the left side of the bipartite graph. For any edge $\{u,v\}\in E$ ($u,v$ ordered lexicographically) we have a vertex $y_{uv}:=1uv$ on the right side of the bipartite graph and we create the edges $\{x_{u},y_{uv}\}$ and $\{x_{v},y_{uv}\}$. All other vertices in $\{0,1\}\times\{0,1\}^{2n}$ are isolated. In polynomial time we can construct a circuit that computes the neighbours of any vertex. Furthermore, $w\in\{0,1\}^{n}$ is a leaf, if and only if $x_{w}$ has degree 1. Finally, all vertices on the right-hand side have degree 0 or 2. ∎

In the definition of the PPA-$k$-complete problem Bipartite-mod-$k$ (Definition 1) the degree of the trivial solution $00^{n}$ can be any number in $\{1,\dots,k-1\}$. In this section we define more refined classes where the degree of the trivial solution is fixed. In Section 5, these classes will be very useful to describe how the PPA-$k$ classes relate to each other. These definitions are inspired by the corresponding “counting principles” studied in Beame et al. that were also defined in a refined form in order to describe how they relate to each other. We believe that these refined classes will also be useful to capture the complexity of natural problems. Note that for $k=2$, the degree of the trivial solution will always be $1$ and thus the question does not even appear in the study of PPA.

Note that this problem remains in TFNP, since the condition can be checked efficiently.

Let $R_{0}$ and $R_{1}$ be two TFNP problems. Then the problem $R_{0}\operatorname*{\&}R_{1}$ is defined as: given an instance $I_{0}$ of $R_{0}$, an instance $I_{1}$ of $R_{1}$ and a bit $b\in\{0,1\}$, find a solution to $I_{b}$.

We extend the $\operatorname*{\&}$ operation to TFNP subclasses in the natural way. Let $C_{0}$ and $C_{1}$ be TFNP subclasses with complete problems $R_{0}$ and $R_{1}$ respectively. Then $C_{0}\operatorname*{\&}C_{1}$ is the class of all TFNP problems that many-one reduce to $R_{0}\operatorname*{\&}R_{1}$. Note that the choice of complete problems does not matter. Intuitively, this class contains all problems that can be solved in polynomial time by a Turing machine with a single oracle query to either $C_{0}$ or $C_{1}$.

Together with Lemma 1, Lemma 2 yields, e.g., PPA-$6$ $=$ PPA-$6[\#2]$ $\operatorname*{\&}$ PPA-$6[\#3]$.

Equivalent Definitions

In this section we show that PPA-$k$ can be defined by using other problems instead of Bipartite-mod-$k$. The totality of these problems is again based on arguments modulo $k$. By showing that these problems are indeed PPA-$k$-complete, we provide additional support for the claim that PPA-$k$ captures the complexity of “polynomial arguments modulo $k$”. While these problems are not “natural” and thus not interesting in their own right, they provide equivalent ways of defining PPA-$k$, which can be very useful when working with these classes. In particular, we make extensive use of these equivalences in this work.

The TFNP problems we consider are the following:

Imbalance-mod-$k$ : given a directed graph and a vertex that is unbalanced-mod-$k$, i.e., out-degree $-$ in-degree $\neq 0\mod k$, find another such vertex.

Hypergraph-mod-$k$ : given a hypergraph and a vertex that has degree $\neq 0\mod k$, find another such vertex or a hyperedge that has size $\neq k$.

Partition-mod-$k$ : given a set of size $\neq 0\mod k$ and a partition into subsets, find a subset that has size $\neq k$.

Imbalance-mod-$k$, Hypergraph-mod-$k$, Partition-mod-$k$ are PPA-$k$-complete.

The problem Imbalance-mod-$k$ is a generalisation of the PPAD-complete problem Imbalance : given a directed graph and a vertex that is unbalanced (i.e., out-degree $-$ in-degree $\neq 0$), find another unbalanced vertex. It is known that in Imbalance we can assume without loss of generality that the given vertex has imbalance exactly $1$. As a result, Imbalance trivially reduces to Imbalance-mod-$k$, and thus Theorem 1 also yieldsThis observation was also made by Jeřábek for the classes PPA-$p$ ($p$ prime).:

For all $k\geq 2$, we have PPAD $\subseteq$ PPA-$k$.

Furthermore, if we use the convention that $a=b\mod 0$ if and only if $a=b$, then Imbalance-mod- actually corresponds to Imbalance. Thus, in a certain sense we could define \textup{PPA-0}=\textup{PPAD}. On the other hand, Imbalance-mod-$1$ is a trivial problem.

Let $k\geq 2$. The problem Imbalance-mod-$k$ is defined as: given Boolean circuits $S,P:\{0,1\}^{n}\to\textsf{Set}_{\leq k}(\{0,1\}^{n})$ representing a directed graph on the vertex set $\{0,1\}^{n}$ with $|S(0^{n})|-|P(0^{n})|\notin\{-k,0,k\}$, find

$x\neq 0^{n}$ such that $|S(x)|-|P(x)|\notin\{-k,0,k\}$

or $x,y$ such that $y\in S(x)$ but $x\notin P(y)$, or $y\in P(x)$ but $x\notin S(y)$.

Hypergraph.

A hypergraph on the vertex set $\{0,1\}^{n}$ is represented as follows. For every vertex $x\in\{0,1\}^{n}$, a circuit $C:\{0,1\}^{n}\to\textsf{Set}_{\leq k}(\textsf{Set}_{\leq k}(\{0,1\}^{n}))$ outputs the set $C(x)$ of all hyperedges containing $x$, where each hyperedge is a set of vertices in $\{0,1\}^{n}$. As usual, we only need to consider the case where every vertex is contained in at most $k$ hyperedges and every hyperedge has size at most $k$. A hyperedge $\{x_{1},\dots,x_{m}\}$ exists in the hypergraph, if all the vertices involved indeed agree that it is present, i.e., if $\{x_{1},\dots,x_{m}\}\in C(x_{i})$ for all $i\in\{1,\dots,m\}$.

Let $k\geq 2$. The problem Hypergraph-mod-$k$ is defined as: given a Boolean circuit $C:\{0,1\}^{n}\to\textsf{Set}_{\leq k}(\textsf{Set}_{\leq k}(\{0,1\}^{n}))$ representing a hypergraph on the vertex set $\{0,1\}^{n}$ with $|C(0^{n})|\notin\{0,k\}$, find

$x\neq 0^{n}$ such that $|C(x)|\notin\{0,k\}$

or $x$ such that $C(x)$ contains a hyperedge of size $\neq k$

or $x,y$ such that $C(x)$ and $C(y)$ are not consistent with one another.

Note that for $k=2$ this problem essentially corresponds to the PPA-complete problem Leaf and its (equivalent) generalisation Odd : given an undirected graph and a vertex with odd degree, find another one.

Partition.

A partition of $\{0,1\}^{n}$ is represented by a Boolean circuit $C:\{0,1\}^{n}\to\{0,1\}^{n}$ as follows: $x\in\{0,1\}^{n}$ lies in the subset given by the orbit of $x$ with respect to $C$, i.e., $\{C^{i}(x):i\geq 0\}$, where $C^{i}(x)=C(C(\dots C(x))\dots)$ ($i$ times). The problem we define below is based on the simple observation that a base set of size $\neq 0\mod k$ cannot be partitioned into sets of size $k$. The base set consists of all elements in $\{0,1\}^{n}$ except for $m$ elements that have been removed, for some $m<2^{n}$ such that $2^{n}-m\neq 0\mod k$. Here it is convenient to identify $\{0,1\}^{n}$ with $\{0,1,\dots,2^{n}-1\}$ in the natural way. Thus, we can think of the base set as simply being $\{m,m+1,\dots,2^{n}-1\}$.

Let $k\geq 2$. The problem Partition-mod-$k$ is defined as: given $m<2^{n}$ with $2^{n}-m\neq 0\mod k$ and a Boolean circuit $C:\{0,1\}^{n}\to\{0,1\}^{n}$, such that $C(x)=x$ for all $x<m$, find

or $x\in\{0,1\}^{n}$ such that $C^{k}(x)\neq x$

The condition “$C(x)=x$ for all $x<m$” corresponds to excluding elements that do not lie in the base set and it can be enforced syntactically. The first solution type corresponds to finding a set in the partition such that its size divides $k$ (but is $\neq k$), while the second solution type corresponds to finding a set such that its size does not divide $k$. Note that a solution is guaranteed to exist since $2^{n}-m\neq 0\mod k$.

The definition of this problem can be modified in various ways without changing its complexity. For instance, the first solution type can be changed to simply ask for $x\geq m$ such that $C^{d}(x)=x$ for some $d<k$. We have defined the problem in a slightly more complicated way to make the connection with the $\textup{MOD}^{k}$ problems more immediate (see Section 6). Yet another equivalent way of defining the problem would be to consider a Boolean circuit $C:\{0,1\}^{n}\to\textsf{Set}_{\leq k}(\{0,1\}^{n})$ where $C(x)\subseteq\{0,1\}^{n}$ is interpreted as the set containing $x$ in the partition. A solution would then be any $x\geq m$ with $|C(x)|<k$ or any $x,y$ witnessing an inconsistency in the partition given by $C$.

2 Proof of Theorem 1

Mitosis gadgets.

Let $k\geq 2$. We now show how to construct a small bipartite graph such that exactly one vertex on each side has degree $1$ and all other vertices have degree $k$ (or ). This “gadget” can then be used to increase the degree of two vertices (one on each side of the bipartite graph) without adding any solutions, i.e., vertices with degree $\neq 0\mod k$.

The gadget is a bipartite graph with $k+1$ vertices on each side: $a_{1},\dots,a_{k+1}$ and $b_{1},\dots,b_{k+1}$. It contains all the edges $\{a_{i},b_{j}\}$ for $i,j\leq k$, except the edge $\{a_{k},b_{k}\}$. It also contains the edges $\{a_{k},b_{k+1}\}$ and $\{a_{k+1},b_{k}\}$. Thus, all vertices have degree $k$, except for $a_{k+1}$ and $b_{k+1}$ which have degree $1$.

We call this the “Mitosis” gadget, because it allows us to duplicate edges that already exist. Let $u$ and $v$ be two vertices in a bipartite graph, one on each side. Furthermore, consider the case where there is an edge $\{u,v\}$. We would like to increase the degree of $u$ and $v$ by $1$, but without introducing any new solutions, in particular without introducing any vertex with degree $\neq 0\mod k$. Using the Mitosis gadget, we can just add new vertices $a_{1},\dots,a_{k}$ and $b_{1},\dots,b_{k}$, and identify $a_{k+1}$ with $u$ and $b_{k+1}$ with $v$. Adding the corresponding vertices of the gadget yields a bipartite graph where the degree of $u$ and $v$ has increased by $1$, but no new solutions have been introduced. Note that this gadget can, in particular, be used to turn a bipartite graph with multi-edges into one without them, without changing the degree of existing vertices and without adding any new solutions.

Relationship Between the Classes

In this section, we present some results that provide deeper insights into how the classes relate to each other. For any $k\geq 2$, $\operatorname{\mathsf{PF}}(k)$ denotes the set of all prime factors of $k$. The main conceptual result is that PPA-$k$ is entirely determined by the set of prime factors of $k$:

For any $k\geq 2$ we have PPA-$k$ $=$ $\operatorname*{\&}\limits_{p\in\operatorname{\mathsf{PF}}(k)}$ PPA-$p$.

This equation can be understood as saying the following:

Given a single query to an oracle for PPA-$k$, we can solve any problem in PPA-$p$ for any $p\in\operatorname{\mathsf{PF}}(k)$

Given a single query to an oracle that solves any PPA-$p$ problem for any $p\in\operatorname{\mathsf{PF}}(k)$, we can solve any problem in PPA-$k$.

For $k_{1},k_{2}\geq 2$, if $\operatorname{\mathsf{PF}}(k_{1})\subseteq\operatorname{\mathsf{PF}}(k_{2})$, then PPA-$k_{1}$ $\subseteq$ PPA-$k_{2}$.

For all $k_{1},k_{2}\geq 2$, PPA-$k_{1}k_{2}$ $=$ PPA-$k_{1}$ $\operatorname*{\&}$ PPA-$k_{2}$.

For all $k\geq 2$ and all $r\geq 1$ we have PPA-$k^{r}$ $=$ PPA-$k$.

The proof of Theorem 3 can be found in the next section. Before we move on to that, let us briefly show that Theorem 2 follows from Theorem 3.

All containment results follow from Theorem 4 below, except

Inspired by the definition of the PPA-complete problem Lonely , Buss and Johnson defined TFNP problems called $\textup{MOD}^{p}$ to represent arguments modulo some prime $p$. Their main motivation was to use these problems to show separations (in the type 2 setting) between Turing reductions with $m$ oracle queries and Turing reductions with $m+1$ oracle queries. In his thesis , Johnson generalised the definition of $\textup{MOD}^{k}$ to any $k\geq 2$ and defined corresponding classes $\text{PMOD}^{k}$. He also proved some separations between these classes and other TFNP classes in the type 2 setting (which yield oracle separations in the standard setting). It seems that Johnson was not aware of Papadimitriou’s PPA-$p$ classes.

In this section, we study the classes $\text{PMOD}^{k}$ and prove a characterisation in terms of the classes PPA-$p$. In particular, we show that $\text{PMOD}^{k}$ does not capture the full strength of arguments modulo $k$, when $k$ is not a prime power. This characterisation also allows us to use Johnson’s separations to obtain some oracle separations involving PPA-$k$ and other TFNP classes.

Informally, the problem $\textup{MOD}^{k}$ can be defined as follows. We are given a partition of $\{0,1\}^{n}$ into subsets and the goal is to find one of these subsets that has size $\neq k$. If $k$ is not a power of $2$, then such a subset must exist. If $k$ is a power of $2$, then we instead consider $\{0,1\}^{n}\setminus\{0^{n}\}$ and the problem remains total.

Let $k\geq 2$. The problem $\textup{MOD}^{k}$ is defined as: given a Boolean circuit $C$ with $n$ inputs and outputs,

or $x\in\{0,1\}^{n}$ such that $C^{k}(x)\neq x$

If $k$ is a power of $2$: Let additionally $C(0^{n})=0^{n}$ and find

or $x\in\{0,1\}^{n}$ such that $C^{k}(x)\neq x$

For any $k\geq 2$, the class $\text{PMOD}^{k}$ is defined as the set of all TFNP problems that many-one reduce to $\textup{MOD}^{k}$.

Johnson proves a lemma [25, Lemma 7.4.5] that gives some idea of how the $\text{PMOD}^{k}$ classes relate to each other. It can be stated as follows: if $k=p_{1}p_{2}\dots p_{r}$, where the $p_{i}$ are distinct primes, then \textup{\text{PMOD}^{k}}=\cap_{i}\textup{\text{PMOD}^{p_{i}}}. He proves this if all $p_{i}\neq 2$ and claims that the proof also works if some $p_{i}=2$. However, if some $p_{i}=2$ then the proof does not work. This is easy to see, since our results below prove that \textup{\text{PMOD}^{6}}=\textup{\text{PMOD}^{3}} which is not equal to \textup{\text{PMOD}^{2}}\cap\textup{\text{PMOD}^{3}}, unless \textup{\text{PMOD}^{2}}\subseteq\textup{\text{PMOD}^{3}}. However, Johnson proves that \textup{\text{PMOD}^{2}}\not\subseteq\textup{\text{PMOD}^{3}} in the type 2 setting.

The following result provides a full characterisation of $\text{PMOD}^{k}$ in terms of the classes PPA-$p$.

If $k$ is not a power of $2$, then \textup{\text{PMOD}^{k}}=\textup{PPA-\widetilde{k}[\#1]}=\cap_{p\in\operatorname{\mathsf{PF}}(\widetilde{k})}\textup{PPA-p} where $\widetilde{k}$ is the largest odd divisor of $k$.

If $k$ is a power of $2$, then \textup{\text{PMOD}^{k}}=\textup{PPA-2}.

The proof of Theorem 5 is given below in Section 6.1.

for all primes $p$ and $r\geq 1$, \textup{\text{PMOD}^{p^{r}}}=\textup{PPA-p^{r}}=\textup{PPA-p}

for all $k\geq 2$, \textup{\text{PMOD}^{2k}}=\textup{\text{PMOD}^{k}}

for all odd $k\geq 3$, \textup{\text{PMOD}^{k}}=\textup{PPA-k[\#1]}=\cap_{p\in\operatorname{\mathsf{PF}}(k)}\textup{PPA-p}

If $k$ is a prime power, then $\text{PMOD}^{k}$ is the same as PPA-$k$. However, for other values of $k$, we argue that $\text{PMOD}^{k}$ fails to capture the full strength of arguments modulo $k$. For example, \textup{\text{PMOD}^{15}}=\textup{PPA-15[\#1]}=\textup{PPA-3}\cap\textup{PPA-5}, whereas \textup{PPA-15}=\textup{PPA-3}\operatorname*{\&}\textup{PPA-5}. This means that PPA-$15$ can solve any problem that lies in PPA-$3$ or PPA-$5$, while $\text{PMOD}^{15}$ can only solve problems that lie both in PPA-$3$ and PPA-$5$. In particular, if \textup{\text{PMOD}^{15}}=\textup{PPA-15}, then it would follow that \textup{PPA-3}=\textup{PPA-5}, which is not believed to hold (see oracle separations below). Even worse perhaps, is the fact that \textup{\text{PMOD}^{2k}}=\textup{\text{PMOD}^{k}} for any $k\geq 2$. In particular, this means that \textup{\text{PMOD}^{6}}=\textup{\text{PMOD}^{3}}, which indicates that $\text{PMOD}^{6}$ does not really capture arguments modulo $6$.

Nevertheless, Johnson’s oracle separation results (obtained from the corresponding type 2 separations as in ) also yield corresponding results for the PPA-$k$ classes (using Theorem 5). We briefly mention a few of the results obtained this way. See Johnson [25, Chapter 8] for additional results. Relative to any generic oracle (see ):

\textup{PPA-p}\not\subseteq\textup{PPA-q} for any distinct primes $p,q$

\textup{PPA-k}\not\subseteq\textup{PPP}, \textup{PPA-k}\not\subseteq\textup{PLS}, \textup{PPA-k}\not\subseteq\textup{PPADS} for any $k\geq 2$

\textup{PPP}\not\subseteq\textup{PPA-p}, \textup{PLS}\not\subseteq\textup{PPA-p} for any prime $p$

For $k=2$, $\textup{MOD}^{2}$ corresponds to the PPA-complete problem Lonely , and thus \textup{\text{PMOD}^{2}}=\textup{PPA}=\textup{PPA-2}. Let $r\geq 2$. Consider an instance $(C,m)$ of Partition-mod-$2^{r}[\#(2^{r}-1)]$ on the set $\{0,1\}^{n}$. Without loss of generality, assume $n\geq r$. Then $2^{n}=0\mod 2^{r}$ and thus $m=2^{n}-(2^{n}-m)=-(2^{r}-1)\mod 2^{r}=1\mod 2^{r}$. This means that we can (efficiently) partition $\{0,1,\dots,m-1\}$ into subsets of size $2^{r}$, leaving only $0=0^{n}$ out. Thus, we have reduced Partition-mod-$2^{r}[\#(2^{r}-1)]$ to $\textup{MOD}^{2^{r}}$. Since \textup{PPA-2^{r}[\#(2^{r}-1)]}=\textup{PPA-2} (Theorem 3), we obtain \textup{PPA-2}\subseteq\textup{\text{PMOD}^{2^{r}}}. On the other hand we also have \textup{\text{PMOD}^{2^{r}}}\subseteq\textup{PPA-2^{r}}=\textup{PPA-2} by Corollary 2.

Consider some $k\geq 3$ that is not a power of $2$. First, let us show that \textup{\text{PMOD}^{2k}}=\textup{\text{PMOD}^{k}}. $\textup{MOD}^{2k}$ reduces to $\textup{MOD}^{k}$ by splitting every subset into two subsets of size $k$ (or less, if the subset has size $<2k$). Conversely, consider an instance of $\textup{MOD}^{k}$ on the set $\{0,1\}^{n}$. Make a copy of the instance, thus obtaining an instance on the set $\{0,1\}^{n+1}$. For every subset of the original instance, take the union with its copy. If the subset had size $k$, the new subset has size $2k$. Thus, we have reduced to $\textup{MOD}^{2k}$.

Let $k\geq 3$ be coprime with $2$. We will show \textup{\text{PMOD}^{k}}=\textup{PPA-k[\#1]}. Consider an instance of $\textup{MOD}^{k}$ on the set $\{0,1\}^{n}$. Since $k$ and $2$ are coprime, there exists $i\in\{0,\dots,k-1\}$ such that $2^{n+i}=1\mod k$ (e.g., by using Euler’s theorem). Thus, we take $2^{i}$ copies of the instance and obtain an instance on the set $\{0,1\}^{n+i}$, which is an instance of Partition-mod-$k[\#1]$ (with $m=0$), since $2^{n+i}=1\mod k$. Conversely, consider an instance $(C,m)$ of Partition-mod-$k[\#1]$ on the set $\{0,1\}^{n}$. As before, there exists $i\in\{0,\dots,k-1\}$ such that $2^{n+i}=1\mod k$. We construct an instance $C^{\prime}$ of $\textup{MOD}^{k}$ on $\{0,1\}^{n+i}$ as follows. The element $x\in\{0,1\}^{n}$ of the original instance corresponds to the element $1^{i}x\in\{0,1\}^{n}$ of the new instance. If $x\geq m$, set $C^{\prime}(1^{i}x)=1^{i}C(x)$. The number of elements that have not yet been assigned to a subset is $m+(2^{i}-1)2^{n}=(m-2^{n})+2^{n+i}=0\mod k$. Thus, we can efficiently partition them into subsets of size $k$ without introducing any solution. We have obtained an instance of $\textup{MOD}^{k}$.

Many-one vs Turing Reductions

For any prime $p\geq 2$, PPA-$p$ is closed under Turing reductions.

In particular, PPA-$p^{r}$ = PPA-$p$ is also closed under Turing reductions. The proof of Theorem 6 can be found in Section 7.1. Furthermore, we also obtain:

If $k$ is not a prime power, then it is not known whether PPA-$k$ is closed under Turing reductions. Using our results from Section 6, we can actually provide an oracle separation between PPA-$k$ and the Turing-closure of PPA-$k$, i.e., an oracle under which PPA-$k$ is not closed under Turing reductions. Let $R_{1},\dots,R_{k}$ be TFNP problems. Following Johnson we define $\bigotimes_{j=1}^{k}R_{j}$ as the problem: given instances $(I_{1},\dots,I_{k})$, where $I_{j}$ is an instance of $R_{j}$, solve $I_{j}$ for all $j$. As we did with the $\operatorname*{\&}$ operation, with a slight abuse of notation, we can also use the operation $\otimes$ with the PPA-$k$ classes. In [25, Theorem 7.6.1], Johnson proved that for $m\geq 2$ and distinct primes $p_{1},\dots,p_{m}$, $\bigotimes_{i=1}^{m}$ $\textup{MOD}^{p_{i}}$ does not many-one reduce to $\operatorname*{\&}_{i=1}^{m}$ $\textup{MOD}^{p_{i}}$ in the type 2 setting. Together with our Theorems 2 and 5 this yields:

Let $k\geq 2$ not a power of a prime. Relative to any generic oracle, it holds that \bigotimes_{p\in\operatorname{\mathsf{PF}}(k)}\textup{PPA-p}\not\subseteq\textup{PPA-k}. In particular, relative to any generic oracle, PPA-$k$ is not closed under Turing reductions.

S=\bigotimes_{p\in\operatorname{\mathsf{PF}}(k)}\textup{PPA-p} corresponds to solving PPA-$p$ for all prime factors $p$ of $k$ simultaneously. In particular, this can be done by using $|\operatorname{\mathsf{PF}}(k)|$ queries to PPA-$k$, i.e., a Turing reduction to PPA-$k$. Thus, $S$ lies in the Turing closure of PPA-$k$, but not in PPA-$k$ (relative to any generic oracle).

We essentially apply the same technique that was used by Buss and Johnson to show that PPA, PPAD, PPADS and PLS are closed under Turing reductions.

Let $\Pi$ be a problem that Turing-reduces to some problem in PPA-$p$. This means that there exists a Turing machine $M$ with access to a PPA-$p$-oracle that solves $\Pi$ in polynomial time. Since Imbalance-mod-$p$ is PPA-$p$-complete (Theorem 1), we assume that the oracle provides solutions to Imbalance-mod-$p$ instances. Our goal is to show that all the oracle queries can be combined into a single one. Indeed, a Turing reduction that always uses a single oracle query immediately yields a many-one reduction. Thus, by the definition of PPA-$p$, this would yield \Pi\in\textup{PPA-p}.

We begin by showing that any Imbalance-mod-$p$-instance can be efficiently transformed into an instance that has a particular form, namely: the starting node has imbalance $+1$ (in-degree and out-degree $1$), and any solution has imbalance $-1$ (in-degree $1$ and out-degree ). This can be achieved by the following steps:

Ensure that all vertices have in- and out-degree at most $p$ (by splitting vertices into multiple copies).

Ensure that any unbalanced vertex has in- or out-degree (by creating a copy that will take all the edges that yield the imbalance).

Since $p$ is prime, we can ensure that the starting vertex has imbalance $+1$.

Ensure that all vertices that have imbalance $\neq 0\mod p$, actually have imbalance $+1$ or $-1$ (by splitting every such vertex into $p$ vertices, each getting at most one edge).

Transform every solution that has imbalance $+1$ into $p-1$ solutions with imbalance $-1$ instead (by pointing to $p-1$ new vertices).

It remains to show that this graph $G$ can be constructed in polynomial time from $I$, i.e., we can efficiently construct circuits that compute the edges incident on any given node. This is easy to see, because any node contains enough information to simulate a run of $M$ up to the point that is needed to determine the neighbours in $G$. We omit the full details, since the formal arguments are analogous to the ones in the corresponding proofs in .

Acknowledgements

I would like to thank Aris Filos-Ratsikas and Paul Goldberg for helpful discussions, as well as an anonymous reviewer for suggestions that helped improve the presentation of the paper. This work was supported by an EPSRC doctoral studentship (Reference 1892947).

References

Appendix A Technical Lemmas for Theorem 4

The proof ideas from are used to construct some of these reductions.

The circuit $C^{\prime}$ determines the image of $a\in S$ by first computing $x_{1},\dots,x_{s}$ and $\alpha_{1},\dots,\alpha_{s}$ as described above, and determining the smallest index $i$ as explained above. Let $a_{i}=a\cap O(x_{i})$. The circuit outputs

Let $k_{1},k_{2}\geq 2$. If all prime factors of $k_{2}$ also divide $k_{1}$, then \textup{PPA-k_{1}[\#1]}\subseteq\textup{PPA-k_{2}[\#1]}.

Similarly to our proof of Lemma 5, we adapt the proof of the corresponding statement for the counting formulas from Beame et al. [2, Lemma 2.5] in order to obtain a polynomial-time reduction.

The final step is to set $m^{\prime}=2^{nr}-(2^{n}-m)^{r}$ and construct an efficient bijection between $\{m^{\prime},\dots,2^{nr}-1\}$ and $\{m,\dots,2^{n}-1\}^{r}$, which is easy to do. ∎