All Questions
Tagged with bounded-depth advice-and-nonuniformity
1 question
9
votes
0
answers
173
views
Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?
D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"On Uniformity Within $\mathsf{NC^1}$" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
($\mathsf{FO}$ ...
- 21.8k