Questions tagged [uniformity]
The uniformity tag has no usage guidance.
9
questions
4
votes
1answer
164 views
Is length uniform AC0 computable?
Consider the following problem:
Input: A binary string $w$.
Output: $|w|$ as a binary number.
Is it possible to compute this
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$
(or equivalently in $\...
2
votes
0answers
189 views
Circuit complexity lower bounds and uniformity
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.
For example, the word problem for ...
13
votes
1answer
258 views
Do we have any nontrivial uniform circuits?
Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$.
On the other hand, it might be that ...
7
votes
2answers
263 views
Size hierachy for uniform circuits
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 ...
11
votes
2answers
324 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. ...
0
votes
1answer
343 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 ...
5
votes
1answer
197 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$ ...
31
votes
3answers
2k 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 $AC^0/...
27
votes
3answers
1k 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 {$0^{f(...
