# 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? Commented Dec 29, 2018 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. Commented Dec 29, 2018 at 8:36
• I tried to explain what I had in mind. Commented Dec 29, 2018 at 20:30