<p>$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.)</p>

<p>The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a polynomially long line of $\ac$-computable edges. By a further extension of the idea, one could simulate edges computable in poly time with a PPAD oracle, that is, PPAD is closed under Turing reducibility; this argument is given in <a href="http://www.math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/">Buss and Johnson</a>.</p>

<p>There are many equivalent definition of PPAD in the literature that differ in various details, hence let me fix one here for definiteness. An NP search problem $S$ is in PPAD if there is a polynomial $p(n)$, and polynomial-time functions $f(x,u)$, $g(x,u)$, and $h(x,u)$ with the following properties. For each input $x$ of length $n$, $f$ and $g$ represent a directed graph $G_x=(V_x,E_x)$ without self-loops where $V_x=\{0,1\}^{p(n)}$, and every node has in-degree and out-degree at most $1$. The representation is such that if $(u,v)\in E_x$, then $f(x,u)=v$ and $g(x,v)=u$; if $u$ has out-degree $0$, $f(x,u)=u$; and if $u$ has in-degree $0$, $g(x,u)=u$.</p>

<p>The node $0^{p(n)}\in V_x$ is a source (i.e., it has in-degree $0$ and out-degree $1$). If $u\in V_x$ is any source or sink (in-degree $1$, out-degree $0$) other than $0^{p(n)}$, then $h(x,u)$ is a solution to $S(x)$.</p>

<p>We can define $\ac\mathrm{PAD}$ similarly, except we require $f,g,h$ to be in $\mathrm{FAC}^0$.</p>

<p>I will ignore $h$ in the construction for simplicity. (It is not hard to show that one can take it to be a projection, hence $\ac$-computable.)</p>

<p>So, consider a PPAD problem $S$ defined by $f$ and $g$, and fix Turing machines computing $f$ and $g$ in time $q(n)$. For any $x$, we define a directed graph $G'_x=(V'_x,E'_x)$ whose vertices are sequences of the following form:</p>

<ul>
<li><p>$(0,u,c_1,\dots,c_k)$, where $u\in V_x$, $0\le k\le q(n)$, and $c_1,\dots,c_k$ are the first $k$ configurations in the computation of $f(x,u)$.</p></li>
<li><p>$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)$, where $u,v\in V_x$, $0\le k\le q(n)$, $f(x,u)=v$, $c_1,\dots,c_{q(n)}$ is the full computation of $f(x,u)$, and $d_1,\dots,d_k$ are the first $k$ steps in the computation of $g(x,v)$.</p></li>
<li><p>$(1,v,d_1,\dots,d_k)$, where $0^{p(n)}\ne v\in V_x$, $0\le k\le q(n)$, and $d_1,\dots,d_k$ are the first $k$ configurations in the computation of $g(x,v)$.</p></li>
<li><p>$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$, where $u,v\in V_x$, $v\ne0^{p(n)}$, $0\le k\le q(n)$, $g(x,v)=u$, $d_1,\dots,d_{q(n)}$ is the computation of $g(x,v)$, and $c_1,\dots,c_k$ are the first $k$ steps in the computation of $f(x,u)$.</p></li>
</ul>

<p>$E'_x$ consists of the edges in $V'_x\times V'_x$ of the following kinds:</p>

<ul>
<li><p>$(0,u,c_1,\dots,c_k)\to(0,u,c_1,\dots,c_{k+1})$</p></li>
<li><p>$(0,u,c_1,\dots,c_{q(n)})\to(0,u,c_1,\dots,c_{q(n)},v)$</p></li>
<li><p>$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_k)\to(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{k+1})$</p></li>
<li><p>$(0,u,c_1,\dots,c_{q(n)},v,d_1,\dots,d_{q(n)})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{q(n)})$ if $f(u)=v$ and $g(v)=u$ (i.e., either $(u,v)\in E_x$, or $u=v$ is an isolated vertex)</p></li>
<li><p>$(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_{k+1})\to(1,v,d_1,\dots,d_{q(n)},u,c_1,\dots,c_k)$</p></li>
<li><p>$(1,v,d_1,\dots,d_{q(n)},u)\to(1,v,d_1,\dots,d_{q(n)})$</p></li>
<li><p>$(1,v,d_1,\dots,d_{k+1})\to(1,v,d_1,\dots,d_k)$</p></li>
<li><p>$(1,u)\to(0,u)$</p></li>
</ul>

<p>Formally, let $r(n)$ be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with $\ac$-functions); we actually put $V'_x=\{0,1\}^{r(n)}$, and we let all vertices except the above-mentioned sequences to be isolated.</p>

<p>It is easy to see that the functions $f'$, $g'$ representing $G'_x$ are $\ac$-computable: in particular, we can test in $\ac$ whether $c_1,\dots,c_k$ is a valid partial computation of $f(x,u)$, we can compute $c_{k+1}$ from $c_k$, and we can extract the value of $f(x,u)$ from $c_{q(n)}$.</p>

<p>The sinks in $G'_x$ are nodes of the form $(0,u,c_1,\dots,c_{q(n)},u,d_1,\dots,d_{q(n)})$ where $u$ is a sink in $G_x$. Likewise, sources are $(1,v,d_1,\dots,d_{q(n)},v,c_1,\dots,c_{q(n)})$ where $v$ is a source in $G_x$, except that in the special case $v=0^{p(n)}$, we have pruned the line early and the corresponding source in $G'_x$ is just $(0,0^{p(n)})$. We can assume the encoding of sequences is done in such a way that $(0,0^{p(n)})=0^{r(n)}$.</p>

<p>Thus, $f'$ and $g'$ define an $\ac\mathrm{PAD}$ problem $S'$, and we can extract a solution to $S(x)$ from a solution to $S'(x)$ by an $\ac$-function $h'$ which outputs the second component of a sequence.</p>

CC BY-SA 3.0
2014-10-17T19:34:51.590Z
2014-10-17T19:34:51.590Z
Emil Jeřábek
<p>What happens if we define <a href="http://en.wikipedia.org/wiki/PPAD_(complexity)">${\bf PPAD}$</a> such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? </p>

<p>Recently giving faster algorithms for <a href="http://en.wikipedia.org/wiki/Circuit_satisfiability_problem">Circuit satisfiability</a> for small circuits <a href="http://arxiv.org/abs/1401.2444">turned out</a> to be important, so I wonder what happens to rectricted versions of ${\bf PPAD}$.</p>

CC BY-SA 3.0
2014-10-16T08:41:38.443Z
Buss and Johnson, "Propositional proofs and reductions between NP search problems", prove that PPAD is closed under Turing reductions, and I'm pretty sure a minor modification of the argument gives the equivalence of PPAD with its (uniform) AC^0 version.
Emil Jeřábek
CC BY-SA 3.0
2014-10-16T16:11:56.630Z
@Emil: Thank you for the suggestion, unfortunately the notions in this paper are beyond me. I would be grateful if someone could tell me its implications. Also, let me link to its preprint here: http://www.math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/NPSearch.pdf
domotorp
<cc.complexity-theory><circuit-complexity><logspace><ppad><ac0>
Does ${\bf AC^0PAD} = {\bf PPAD}$?
domotorp
# Does ${\bf AC^0PAD} = {\bf PPAD}$?

(Asked by: username_0 on 2014-10-15)

What happens if we define [${\bf PPAD}$](http://en.wikipedia.org/wiki/PPAD_(complexity)) such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem?

Recently giving faster algorithms for [Circuit satisfiability](http://en.wikipedia.org/wiki/Circuit_satisfiability_problem) for small circuits [turned out](http://arxiv.org/abs/1401.2444) to be important, so I wonder what happens to rectricted versions of ${\bf PPAD}$.

**Tags:** cc.complexity-theory, circuit-complexity, logspace, ppad, ac0
> **Comments:**
> **username_1**: Buss and Johnson, "Propositional proofs and reductions between NP search problems", prove that PPAD is closed under Turing reductions, and I'm pretty sure a minor modification of the argument gives the equivalence of PPAD with its (uniform) AC^0 version.  
> **username_0**: @Emil: Thank you for the suggestion, unfortunately the notions in this paper are beyond me. I would be grateful if someone could tell me its implications. Also, let me link to its preprint here: http://www.math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/NPSearch.pdf  

---

## 1 answers

### Answer by username_1 on 2014-10-17. Score: 10 | Accepted answer

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.)

The basic idea is quite simple: $\ac$ can do one step of a Turing machine computation, hence we can simulate one polynomial-time computable edge by a polynomially long line of $\ac$-computable edges. By a further extension of the idea, one could simulate edges computable in poly time with a PPAD oracle, that is, PPAD is closed under Turing reducibility; this argument is given in [Buss and Johnson](http://www.math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/).

There are many equivalent definition of PPAD in the literature that differ in various details, hence let me fix one here for definiteness. An NP search problem $S$ is in PPAD if there is a polynomial $p(n)$, and polynomial-time functions $f(x,u)$, $g(x,u)$, and $h(x,u)$ with the following properties. For each input $x$ of length $n$, $f$ and $g$ represent a directed graph $G\_x=(V\_x,E\_x)$ without self-loops where $V\_x=\{0,1\}^{p(n)}$, and every node has in-degree and out-degree at most $1$. The representation is such that if $(u,v)\in E\_x$, then $f(x,u)=v$ and $g(x,v)=u$; if $u$ has out-degree $0$, $f(x,u)=u$; and if $u$ has in-degree $0$, $g(x,u)=u$.

The node $0^{p(n)}\in V\_x$ is a source (i.e., it has in-degree $0$ and out-degree $1$). If $u\in V\_x$ is any source or sink (in-degree $1$, out-degree $0$) other than $0^{p(n)}$, then $h(x,u)$ is a solution to $S(x)$.

We can define $\ac\mathrm{PAD}$ similarly, except we require $f,g,h$ to be in $\mathrm{FAC}^0$.

I will ignore $h$ in the construction for simplicity. (It is not hard to show that one can take it to be a projection, hence $\ac$-computable.)

So, consider a PPAD problem $S$ defined by $f$ and $g$, and fix Turing machines computing $f$ and $g$ in time $q(n)$. For any $x$, we define a directed graph $G'\_x=(V'\_x,E'\_x)$ whose vertices are sequences of the following form:

* $(0,u,c\_1,\dots,c\_k)$, where $u\in V\_x$, $0\le k\le q(n)$, and $c\_1,\dots,c\_k$ are the first $k$ configurations in the computation of $f(x,u)$.
* $(0,u,c\_1,\dots,c\_{q(n)},v,d\_1,\dots,d\_k)$, where $u,v\in V\_x$, $0\le k\le q(n)$, $f(x,u)=v$, $c\_1,\dots,c\_{q(n)}$ is the full computation of $f(x,u)$, and $d\_1,\dots,d\_k$ are the first $k$ steps in the computation of $g(x,v)$.
* $(1,v,d\_1,\dots,d\_k)$, where $0^{p(n)}\ne v\in V\_x$, $0\le k\le q(n)$, and $d\_1,\dots,d\_k$ are the first $k$ configurations in the computation of $g(x,v)$.
* $(1,v,d\_1,\dots,d\_{q(n)},u,c\_1,\dots,c\_k)$, where $u,v\in V\_x$, $v\ne0^{p(n)}$, $0\le k\le q(n)$, $g(x,v)=u$, $d\_1,\dots,d\_{q(n)}$ is the computation of $g(x,v)$, and $c\_1,\dots,c\_k$ are the first $k$ steps in the computation of $f(x,u)$.

$E'\_x$ consists of the edges in $V'\_x\times V'\_x$ of the following kinds:

* $(0,u,c\_1,\dots,c\_k)\to(0,u,c\_1,\dots,c\_{k+1})$
* $(0,u,c\_1,\dots,c\_{q(n)})\to(0,u,c\_1,\dots,c\_{q(n)},v)$
* $(0,u,c\_1,\dots,c\_{q(n)},v,d\_1,\dots,d\_k)\to(0,u,c\_1,\dots,c\_{q(n)},v,d\_1,\dots,d\_{k+1})$
* $(0,u,c\_1,\dots,c\_{q(n)},v,d\_1,\dots,d\_{q(n)})\to(1,v,d\_1,\dots,d\_{q(n)},u,c\_1,\dots,c\_{q(n)})$ if $f(u)=v$ and $g(v)=u$ (i.e., either $(u,v)\in E\_x$, or $u=v$ is an isolated vertex)
* $(1,v,d\_1,\dots,d\_{q(n)},u,c\_1,\dots,c\_{k+1})\to(1,v,d\_1,\dots,d\_{q(n)},u,c\_1,\dots,c\_k)$
* $(1,v,d\_1,\dots,d\_{q(n)},u)\to(1,v,d\_1,\dots,d\_{q(n)})$
* $(1,v,d\_1,\dots,d\_{k+1})\to(1,v,d\_1,\dots,d\_k)$
* $(1,u)\to(0,u)$

Formally, let $r(n)$ be a polynomial bounding the lengths of binary representations of all the sequences above (such that we can extend or shorten sequences, and extract their elements with $\ac$-functions); we actually put $V'\_x=\{0,1\}^{r(n)}$, and we let all vertices except the above-mentioned sequences to be isolated.

It is easy to see that the functions $f'$, $g'$ representing $G'\_x$ are $\ac$-computable: in particular, we can test in $\ac$ whether $c\_1,\dots,c\_k$ is a valid partial computation of $f(x,u)$, we can compute $c\_{k+1}$ from $c\_k$, and we can extract the value of $f(x,u)$ from $c\_{q(n)}$.

The sinks in $G'\_x$ are nodes of the form $(0,u,c\_1,\dots,c\_{q(n)},u,d\_1,\dots,d\_{q(n)})$ where $u$ is a sink in $G\_x$. Likewise, sources are $(1,v,d\_1,\dots,d\_{q(n)},v,c\_1,\dots,c\_{q(n)})$ where $v$ is a source in $G\_x$, except that in the special case $v=0^{p(n)}$, we have pruned the line early and the corresponding source in $G'\_x$ is just $(0,0^{p(n)})$. We can assume the encoding of sequences is done in such a way that $(0,0^{p(n)})=0^{r(n)}$.

Thus, $f'$ and $g'$ define an $\ac\mathrm{PAD}$ problem $S'$, and we can extract a solution to $S(x)$ from a solution to $S'(x)$ by an $\ac$-function $h'$ which outputs the second component of a sequence.


---

