Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates?
How about when we go from circuits to programs?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
The Cook–Levin theorem shows how to construct a circuit of size $f(n)^{O(1)}$. I'm not sure what's the best exponent.
The opposite direction is impossible, since circuits of size 1 can compute the following language: $$ \{ w : \text{the $|w|$th Turing machine halts on the empty input} \}. $$ More generally, circuits of size 1 can compute any language in which the answer depends only on the length of the input.
answered May 23, 2019 at 7:15
-
$\begingroup$ 'circuits of size 1 can compute the following language:....' why? $\endgroup$– TurboMay 23, 2019 at 7:16
-
-
-
1$\begingroup$ @Brout It's a map from length to a non-computable predicate. That's the most standard example for non-uniformity allowing for strictly more than r.e. languages. $\endgroup$– dkaeaeMay 23, 2019 at 7:22
-
$\begingroup$ @dkaee Is there reference for this (it is new to me)? $\endgroup$– TurboMay 23, 2019 at 7:32