The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and "possible next" functions, each with an exponentially sized domain. And the task is to find an input that satisfies $P(Q(x)) \neq Q(P(x)) \neq x$.

But I raise the question: How can these circuits be represented on a Turing machine?

To answer this question, I think two things must be proven.

  1. Arithmetic circuits have a polynomial time and space translation to a Turing machine language
  2. Polynomial depth circuits can compute any choice of $P$ and $Q$

My question is mostly about $1$, but I don't really see how $2$ can be true either. Do we need these to translate this problem to a Turing machine context?


1 Answer 1


A circuit is not represented "on" a Turing machine, rather a representation of the circuit is provided as input. It is straightforward to represent a circuit as a bit-string. For instance, you can list each gate of the circuit, and which gates' outputs are connected to which gates' inputs.

I can't make sense of the things that you suggest must be proven. I suspect there is some misunderstanding or faulty premise.

  • $\begingroup$ I think my second suggestion is faulty. My first one is asking for an algorithm for what you describe as "straightforward [method] to represent a circuit as a bit-string." (and how to evaluate such a bit-string as though it was a circuit) $\endgroup$
    – Loic Stoic
    Mar 17, 2023 at 9:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.