3 ms·
Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself
by jmount 2y ago
Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself has to be written out by a simple Turing machine (I thought there was one but it isn't on the tip of my tong).
- bo1024 2y agoYeah, the word is "uniform", e.g. a uniform family of circuits is one where there is a Turing machine where, for each n, it outputs the circuit for inputs of size n.