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-...
- 268k
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) = ...
- 1
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 ...
- 22.6k
Top 50 recent answers are included