New answers tagged circuits
3
Let $H_{f(n)}$ be the set of all pairs $(M,x)$ such that $M$ halts on $x$ within $f(|x|)$ steps. We encode the pairs in such a way that $|(M,x)| = |x| + C_M$, where $C_M$ is a constant that depends only on $M$. Suppose that $H_{f(n)}$ has circuits of size $g(n)$ (note that it's a slightly different $n$).
Let $h(n) \leq \kappa 2^n/n$, for an appropriate $\...
Top 50 recent answers are included