All Questions
5 questions
1
vote
1
answer
109
views
What is uniformity in Boolean circuits exactly?
I have two questions on Kaveh's answer to Definition of uniform boolean circuit :
Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
- 320
0
votes
1
answer
76
views
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
- 55
3
votes
1
answer
188
views
Is it known that $AC^1 \subseteq L$?
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
- 7,248
2
votes
1
answer
514
views
Space complexity of boolean circuit evaluation
I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size.
Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.
Now, assuming the fan in of ...
- 193
1
vote
1
answer
370
views
Show that problem is PSPACE-complete - path in directed graph
I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
- 379