<p>What happens if we define <a href="http://en.wikipedia.org/wiki/PPAD_(complexity)" rel="nofollow noreferrer"><span class="math-container">${\bf PPAD}$</span></a> such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem? </p>

<p>I asked a similar <a href="https://cstheory.stackexchange.com/questions/27074/does-bf-ac0pad-bf-ppad">question</a> four years ago, but I expect the answer to be different.</p>

<p>To give a concrete example, consider End-Of-The-Line in a grid (known to be PPAD-complete); here a digraph <span class="math-container">$G_n$</span> on <span class="math-container">$2^n\times 2^n$</span>, with arcs going only between some neighboring grid-points, is encoded by a machine, such that <span class="math-container">$(0,0)$</span> has no in-neighbor and only one out-neighbor, and our goal is to find another vertex of odd degree. We make a CFLPAD problem from it as follows. Fix a PDA. On any input <span class="math-container">$(x,y)$</span> of length <span class="math-container">$n$</span>, the PDA should return the in- and out-neighbors of the grid-vertex <span class="math-container">$(x,y)$</span> of <span class="math-container">$G_n$</span>. So how hard is it to find another odd vertex (with the PDA and <span class="math-container">$n$</span> as input)?</p>

CC BY-SA 4.0
2018-12-29T08:30:15.917Z
CFL is not even closed under complement, hence minute details of the formalization matter. Can you spell out exactly what language is given by the PDA?
Emil Jeřábek
CC BY-SA 4.0
2018-12-29T08:36:58.040Z
Also, do you mean that every CFLPAD problem is given by a fixed (constant-size) PDA corresponding to the problem, or is the PDA a part of the input? This will make a huge difference.
Emil Jeřábek
CC BY-SA 4.0
2018-12-29T20:30:34.650Z
I tried to explain what I had in mind.
domotorp
<cc.complexity-theory><circuit-complexity><regular-language><context-free><ppad>
Does ${\bf CFLPAD}={\bf PPAD}$?
domotorp
# Does ${\bf CFLPAD}={\bf PPAD}$?

(Asked by: username_0 on 2018-12-28)

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 (non-)deterministic finite/push-down automaton encodes the problem?

I asked a similar [question](https://cstheory.stackexchange.com/questions/27074/does-bf-ac0pad-bf-ppad) four years ago, but I expect the answer to be different.

To give a concrete example, consider End-Of-The-Line in a grid (known to be PPAD-complete); here a digraph $G\_n$ on $2^n\times 2^n$, with arcs going only between some neighboring grid-points, is encoded by a machine, such that $(0,0)$ has no in-neighbor and only one out-neighbor, and our goal is to find another vertex of odd degree. We make a CFLPAD problem from it as follows. Fix a PDA. On any input $(x,y)$ of length $n$, the PDA should return the in- and out-neighbors of the grid-vertex $(x,y)$ of $G\_n$. So how hard is it to find another odd vertex (with the PDA and $n$ as input)?

**Tags:** cc.complexity-theory, circuit-complexity, regular-language, context-free, ppad
> **Comments:**
> **username_1**: CFL is not even closed under complement, hence minute details of the formalization matter. Can you spell out exactly what language is given by the PDA?  
> **username_1**: Also, do you mean that every CFLPAD problem is given by a fixed (constant-size) PDA corresponding to the problem, or is the PDA a part of the input? This will make a huge difference.  
> **username_0**: I tried to explain what I had in mind.  

---

## 0 answers

