The uniformity tag has no wiki summary.
8
votes
2answers
152 views
The Examiner's Problem (uniform generation of SAT decision instances/answers)
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. ...
-1
votes
1answer
208 views
Proof Complexity and Circuit Lower bound for coNP
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 ...
4
votes
1answer
116 views
Other types of uniformity for circuits (incl. by small modifications)
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$ ...
26
votes
3answers
868 views
Is $AC^0/poly \cap NP$ contained in $P$?
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 ...
24
votes
3answers
661 views
Is there a candidate for a natural problem in $P/poly - P$?
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 ...
