2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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