All Questions
3 questions
3
votes
1
answer
101
views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
- 33
2
votes
0
answers
275
views
Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
- 221
2
votes
1
answer
122
views
Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
- 221