New answers tagged

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-...
user avatar
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) = ...
user avatar
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 ...
user avatar
  • 22.6k

Top 50 recent answers are included