Programs to circuit conversion

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?

1 Answer

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.

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