0
$\begingroup$

Let M be a non deterministic turing machine.

Suppose M is a TM that runs in T(n) time.

Given an instance of x in {0,1}^n, and the question M(x) accepts?

We can

1) convert M into an oblivious TM that runs in O( T \log T) time. 2) convert the oblivious TM into a circuit SAT instance with O( T \log T ) gates. 3) Convert the circuit SAT into a 3CNF with O (T \log T) vars and O (T \log T) clauses.

Question: is there a way to make this tighter? In particular, can I get a SAT instance of vars/clauses O(n), rather than O( T(n) \log T(n) ) ?

Or is this essentially impossible, as I am forced to have a variable for each non-deterministic step the TM takes, (thus lower bounded to T(n)).

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ It is impossible because it would contradict the nondeterministic time hierarchy theorem. en.wikipedia.org/wiki/… $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 7, 2011 at 2:43
  • 3
    $\begingroup$ note: there is a meta-discussion about the recent questions in complexity including this one here. $\endgroup$
    – Kaveh
    Commented Oct 7, 2011 at 4:11
  • $\begingroup$ My previous comment is wrong, because the time complexity of the reduction can be any polynomial depending on the language. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 7, 2011 at 10:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .