1
$\begingroup$

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(n)\subseteq DTIME(O(f(n)))$?

$\endgroup$

1 Answer 1

1
$\begingroup$

I'm not 100% sure on this, but I believe that the best known bound on this comes from the construction used for the best known bound on creating oblivious Turing machines. See this Gödel's Lost Letter blog post on the relationship between circuit size and oblivious Turing machines, and in particular the "Open Problems" section.

Given an arbitrary deterministic Turing machine that runs in time $T(n)$, it is known how to construct an oblivious deterministic Turing machine that accepts the same language in time $O(T(n) \log T(n))$. I believe that this implies $\operatorname{NTIME}(t) \subseteq \operatorname{DTIME}(t^{2d} \log t)$, where $d$ is the CIRCUIT-SAT exponent from the question (the 2 coming from the fact that you wrote $(nm)^d$ instead of $(n + m)^d$). However, I have not verified the details myself.

$\endgroup$

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.