There is the size hierarchy theorem for non-uniform circuits. Do we have any size hierarchy theorem for any kind of uniform circuits ? (By uniform here, I mean DLOGTIME uniform. But I don't know ...
A course's teaching assistant has managed to write a program that (deterministically) generates difficult exam questions. Now, she'd like to write a program that generates the corresponding answers. ...
I have two questions (1)Circuit lower bound for coNP TAUT is a set of formulae such that any formula in TAUT is satisfied for all boolean assignments. UnSAT is the complement problem of SAT. It is ...
I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ ...
I thought I would share this question as it might be interesting for other users here. Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like ...
I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language ...