All Questions
6 questions
2
votes
1
answer
71
views
What are the gap functions in the AC hierarchy?
Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth−d AC0 circuit needs a size Θ(2n1d−1). But PARITY is in NC1 and PARITY is also the negation of ...
2
votes
1
answer
458
views
Why each function may be computed with circuit with 2^n gates?
Why each function may be computed with circuit with 2^n gates ?
I am trying to understand this thing, but I can't. In particular why function constant 1 requires 2n gates. For me, it should be ...
2
votes
1
answer
80
views
MOD2017(x1,…,xk) computable by bounded depth polynomial size circuit in basis {¬,MAJ}?
Now, I have the following conjecture.
MOD2017(x1,…,xk) is computable by a bounded depth polynomial size circuit in the basis {¬,MAJ}.
However, I am at a loss at ...
2
votes
1
answer
341
views
What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates
In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
2
votes
0
answers
40
views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
1
vote
0
answers
102
views
How many bits we can negate using two/three NOT gates?
How many bits we can negate using two/three NOT gates ?
I am newbie at this subject so I ask for help. It is about circuits.
Edit
After reading link given in comments by @D.W I think that I can ...