Let's say we have some function that can be computed by a minimal circuit of size $m$ (using some metric, say, the number of gates). Other than this minimal circuit, there will be many other circuits computing the same function. Is anything known about how the number of circuits computing the function grows as you increase the allowable size? Does this depend greatly on the function?

Also, I would be interested in any relationship between the size/runtime of smallest programs computing function and the number of circuits computing it.


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.