New answers tagged circuits
3
votes
Shannon's result that some Boolean functions require exponential circuits
The best known lower bounds for explicit functions are $\Omega(n)$. The only superpolynomial lower bounds are in restricted models of circuits, such as monotone circuits and bounded-depth circuits.
NP-...
0
votes
How does fan-out change circuit complexity?
Let $Ω ⊆ B2$ be a complete basis. For a positive integer $s$, let $C_{Ω,s}(f)$ denote the circuit complexity of f, if only fan-out at most $s$ is allowed for each gate.
For all $s ≥ 2$: $C_{Ω,s}(f) = ...
0
votes
Accepted
prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$
If $|C| < 2^{n/100}$ then $C \not\in \text{CorrectSATSolver}$ since otherwise we would have $\text{SAT} \in \text{Size}(2^{n/100})$.
Assume then that $|C| \ge 2^{n/100}$. Evaluating $C$ for a fixed ...
Top 50 recent answers are included
Related Tags
circuits × 269complexity-theory × 141
logic × 26
boolean-algebra × 24
digital-circuits × 18
lower-bounds × 14
complexity-classes × 13
algorithms × 11
turing-machines × 10
reference-request × 10
quantum-computing × 10
time-complexity × 9
computability × 9
reductions × 8
satisfiability × 8
polynomial-time × 8
computer-architecture × 7
space-complexity × 7
computation-models × 7
graphs × 6
np-complete × 6
arithmetic × 6
sequential-circuit × 5
terminology × 4
sorting × 4