Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
What happens if we define ${\bf PPAD}$ 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 for small circuits turned out to be important, so I wonder what happens to rectricted versions of ${\bf PPAD}$.
$\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.
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.
