<p>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 : <a href="https://cstheory.stackexchange.com/q/10645/8345">Oblivious Turing Machine emulation lowerbound</a>. </p>

CC BY-SA 3.0
2012-03-22T11:34:33.530Z
"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)$.
Kaveh
CC BY-SA 3.0
2012-03-22T12:51:51.153Z
@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.
Sajin Koroth
CC BY-SA 3.0
2012-03-22T12:59:16.480Z
@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.
Sajin Koroth
CC BY-SA 3.0
2012-03-22T07:52:21.757Z
2012-03-22T12:55:58.140Z
2017-04-13T12:32:28.077Z
Sajin Koroth
<p>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.</p>

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

<p>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&#39;(n)$, the SAT formula is of length $O(T&#39;(n))$.</p>

<p>Can we somehow bypass the step of making the TM oblivious?</p>

CC BY-SA 3.0
2012-03-22T14:00:11.260Z
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.
chazisop
<cc.complexity-theory><sat><reductions>
More efficient Cook-Levin reduction
Arpita Korwar
# More efficient Cook-Levin reduction

(Asked by: username_0 on 2012-03-22)

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?

**Tags:** cc.complexity-theory, sat, reductions
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-03-22. Score: 6

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](https://cstheory.stackexchange.com/q/10645/8345).

> **Comments:**
> **username_3**: "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)$.  
> **username_2**: @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.  
> **username_2**: @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.  

---

