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)?

  • 3
    $\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$ – Emil Jeřábek Dec 29 '18 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$ – Emil Jeřábek Dec 29 '18 at 8:36
  • 2
    $\begingroup$ I tried to explain what I had in mind. $\endgroup$ – domotorp Dec 29 '18 at 20:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.