From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity 𝑇(𝑛) in time 𝑇(𝑛)log𝑇(𝑛).

Is there is an analogue for circuits? Since circuits can only accept a fixed input size it would only be able to simulate circuits that can be encoded as that input size; so, considering such a set of circuits (or a set of circuits that makes more sense) can the circuit efficiently simulate these?

ex: you can simulate polynomial time Turing machines with polynomial size circuits, can you simulate polynomial size circuits with polynomial size circuits (something like this)?

  • 1
    $\begingroup$ This is not really enough for an answer, but you would need to encode the circuit, and the input to make up the input to the "master" circuit, but that's fine. With that you can take the "cheating" route and build every possible circuit using the input as input, and the circuit description to turn things on and off, then or the outputs of each circuit together. This is very large of course, however I don't think you can avoid that, there's a lot of circuits of a given size, and you need to embed all of them in the "master" circuit. $\endgroup$ Nov 24 '20 at 13:58
  • $\begingroup$ @LukeMathieson when you embed a number of circuits with different outputs into the master circuit is there a lower bound imposed on the size of that master circuit by the number of circuits embedded in it? $\endgroup$
    – DeeDee
    Nov 24 '20 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.