What happens if we define ${\bf PPAD}$ 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 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)?

  • 4
    $\begingroup$ 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? $\endgroup$ Commented Dec 29, 2018 at 8:30
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Dec 29, 2018 at 8:36
  • 2
    $\begingroup$ I tried to explain what I had in mind. $\endgroup$
    – domotorp
    Commented Dec 29, 2018 at 20:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.