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?


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.

  • $\begingroup$ 'circuits of size 1 can compute the following language:....' why? $\endgroup$ – 1.. May 23 '19 at 7:16
  • $\begingroup$ That's a nice question for you. $\endgroup$ – Yuval Filmus May 23 '19 at 7:21
  • $\begingroup$ Dont get it that looks undecidable. $\endgroup$ – 1.. May 23 '19 at 7:22
  • 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$ – dkaeae May 23 '19 at 7:22
  • $\begingroup$ @dkaee Is there reference for this (it is new to me)? $\endgroup$ – 1.. May 23 '19 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.