8

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

domotorp
  • 13,931
  • 37
  • 93
  • 4
    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 Dec 29 '18 at 08:30
  • 3
    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 Dec 29 '18 at 08:36
  • 2
    I tried to explain what I had in mind. – domotorp Dec 29 '18 at 20:30

0 Answers0