# Does ${\bf CFLPAD}={\bf PPAD}$?

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

• 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 supports Monica Dec 29 '18 at 8:30
• 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 supports Monica Dec 29 '18 at 8:36
• I tried to explain what I had in mind. – domotorp Dec 29 '18 at 20:30