Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

10
votes
1answer
155 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 ...
5
votes
2answers
206 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 ...
10
votes
2answers
287 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
244 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
150 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
1k 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
867 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 ...