7
$\begingroup$

In the Arora-Barak book, in the Cook-Levin reduction, the resulting SAT formula is of size $T(n)\log(T(n))$, where $T(n)$ is the running time of the given Turing machine.

Is there a method to get a $O(T(n))$ length SAT formula?

The original TM is made oblivious (a TM is oblivious if the position of the head at the $i$th step depends only on the length of the input string). This step brings the $O(\log(n))$ factor. Once we have an oblivious TM that takes time $T'(n)$, the SAT formula is of length $O(T'(n))$.

Can we somehow bypass the step of making the TM oblivious?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ The first thing to observe is that it's not known if it's possible to get a $O(1)$ length SAT formula. $\endgroup$ – user6973 Mar 22 '12 at 5:58
  • $\begingroup$ The length of the formula must depend on the running time of the machine simulated. Otherwise, you can use the reduction to solve any $\mathbb{NP}$ problem in $NTIME(n^{k})$ , for some k, which would violate the nondeterministic time hierarchy. I believe this would prohibit the formula from having constant length, but it doesn't exclude a linear dependency. $\endgroup$ – chazisop Mar 22 '12 at 14:00
  • $\begingroup$ No. $\:$ The reduction would require an amount of time that depends on the running time of the machine simulated, without the length of the formula depending on the running time of the machine simulated. $\;\;$ $\endgroup$ – user6973 Mar 22 '12 at 20:14
6
$\begingroup$

The obliviousness of the Turing machine is very crucial for Cook-Levin construction to run in time $t(n) \log t(n)$. If the Turing machine is not-oblivious (that is the head position at $i^{th}$ step of computation is not a function of input length ) then, on different inputs, the head position at $i^{th}$ step can be at various positions. But then writing a constant size formula which depends only on the two cells adjacent to head position and head position itself, to ensure correctness of transition from one configuration to the next, cannot be written without knowing the input(As Kaveh pointed out, it is easy to get a $t(n)^2$ formula without the TM being oblivious). But whereas if the Turing machine is oblivious, we can know the position of head at step $i$ on a input of length $n$. Hence can write this formula for correctness between two adjacent configurations. So I guess you should be asking for a better simulation of oblivious Turing machines which beats $O(m \log m)$. It is already asked here : Oblivious Turing Machine emulation lowerbound.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "the obliviousness of the Turing machine is very crucial for the proof of Cook-Levin theorem" is not correct, it is easy to write a size $t^2(n)$ formula for a non-oblivious TM with run-time $t(n)$. $\endgroup$ – Kaveh Mar 22 '12 at 11:34
  • $\begingroup$ @Kaveh : Yes, but this would increase the time taken for the reduction beyond $T(n) \log T(n)$. I should have written a constant size formula. Thanks for pointing out. $\endgroup$ – Sajin Koroth Mar 22 '12 at 12:51
  • $\begingroup$ @Kaveh : As you said, I was wrong, the proof of Cook-Levin theorem does not crucially depend on the fact on T.M. being oblivious. $\endgroup$ – Sajin Koroth Mar 22 '12 at 12:59

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.