All Questions
2 questions
2
votes
1
answer
82
views
Checking membership in DFA with fixed length using AC1 circuit?
I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
- 29
4
votes
2
answers
2k
views
Definition of uniform boolean circuit
Definition
A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log
space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/...
- 61