You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?


1 Answer 1


In a trivial sense, no, because circuits have a fixed input size. To compute the same function as a Turing machine, you need an infinite family of circuits, one for each input size. So a single circuit can't even "simulate" one Turing machine.

So let's restrict ourselves then to inputs just of size $n$, then the question is just are there two Turing machines that compute the same output for every input of size $n$? Well sure, no problem.

Moving back to the family of circuits, fix an infinite family, one circuit for each possible size. Are there two Turing machines that compute the same function for every input size as this circuit family? Again, sure, any two Turing machines with the same language can be paired up with the same family of circuits.

The polynomial bounds even behave nicely (even if they're different polynomials).

Note that this doesn't necessarily hold together once you actually start to think about how to get the family of circuits, and imposing uniformity conditions, but given the question, you're not up to that bit yet.

  • $\begingroup$ apologies, let me rephrase -- restricted to inputs of size n, can a circuit simulate two Turing machines that differ on at least one output given same input of size n? and if both TMs are PTIME can the circuit do this in PSZIE? what about as the number of Turing machines grows to 2-4-16... exponentially but remain PTIME is there still a PSIZE circuit that can take care of them? Thanks! $\endgroup$
    – DeeDee
    Nov 24, 2020 at 15:32

Your Answer

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

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