Something I came up with. Positing here for critiques, and to figure out potential errors.

There is a method to transform polynomial time non-deterministic turing machines into boolean expressions such that the expression is satisfiable if and only if the machine accepts an input $x$.

This method was used by Cook and Levin to prove the NP-completeness of the boolean satisfiability problem.

The idea is to create a table, each row of which is a state in the machine, the first row being the initial state. Consequent rows are the next states, according to the transition function of the machine.

If a machine takes c$n^k$ time to accept an input x, then the table is of size $cn^k\times cn^k$.

The boolean expression constructed from this table of computation is of size $dn^{2k}$ ($d$ being a constant).

The paper can be found at http://courses.cs.tau.ac.il/cc/12a/pdf/CookLevin.pdf

But the method itself would also work for polynomial time deterministic turing machines, as they are indistinguishable from non-deterministic polynomial time turing machines, except for the guessing stage. We can simply omit it, or we can even consider the input $x$ as the guess, and move on to the checking stage.

There is a one-to-one correspondence between the turing machine on input $x$, and the boolean expression constructed out of it using the method above. Also, the expression is satisfiable iff the machine accepts the input $x$. Since the machine always accepts or rejects in polynomial time, say, $O(n^r)$, satisfiability checks on boolean expressions constructed out of this turing machine on different inputs have to take time $O(n^{2r})$ (we can simply run the turing machine on an input, decide if it accepts, or rejects, and then find the boolean expression, and label it as satisfiable or otherwise).

Now, we know via the Time Hierarchy Theorem that there are some problems decidable in $n^{k+1}$ time, but not in $n^k$ time ($k\in \mathbb{N}$). Say, $T_{k+1}$ is a turing machine which decides in $n^{k+1}$ time, but not in $n^k$ time. Therefore, the set of boolean expressions constructed from $T_{k+1}$ can be checked for satisfiability in $n^{2(k+1)}$ time, but not in $n^{2k}$ time.

Hence, we find that $\forall k\in \mathbb{N}$, there exist boolean expressions whose satisfiability cannot be checked in $O(n^{2k})$ time.

This implies that the boolean satisfiability problem cannot have a polynomial time algorithm. Hence P$\neq$ NP.


1 Answer 1


Your approach boils down to 1. we can create SAT instances corresponding to a Turing machine 2. by the time hierarchy there exists for each $k \in \mathbb{N}$ a problem only solvable in at least $O(n^k)$ operations representable by a Turing machine $M$ 3. thus there exists a SAT problem that cannot be solved in $O(n^k)$ for each $k \in \mathbb{N}$ as each such $M$ has a sat formula of at least size $dn^{2k}$.

The intrinsic problem here is with input blow up. To show this, suppose we have a polynomial time SAT algorithm -- in fact, let's suppose we have a linear one, e.g. $O(n)$. Using your proof should contradict the possibility of this.

Now let's take your conclusion, "there exists boolean expressions whose satisfiability cannot be checked in $O(n^{2k})$." Let's make this concrete. If you have a language decidable with a lower bound of acceptance in $O(n^3)$, then the SAT formula will have size $dn^6$. Thus the input to our SAT solver will have increased from $n$ to $n^6$! That's not a fair comparison. To be fair, call our input to the SAT solver $m$. We know that $m$ will have size $n^6$. Thus now any big-oh notation used to describe to the algorithm will be in terms of $m$. Now, the number of operations (what we mean when we say big-oh) would still be $O(m)$ even though it handles data of size $O(n^6)$. This works for any input, even one like $dn^{2k}$: taking $|m| = dn^{2k}$, we still do only $O(m)$ operations.

Thus your proof doesn't contradict a linear time SAT solver. That's because it didn't take into account the input blow up (in fact you base your proof on it -- there's no way to fix it without fundamentally changing the idea of the proof).

  • $\begingroup$ There's a one-to-one correspondence between the turing machine on input $x$, and the boolean expression constructed from it. Hence, we can have a polynomial algorithm to convert such an expression into its turing machine, and the input. One way to check satisfiability is finding the turing machine this way, and seeing it it accepts. Another is through your SAT solver. But if your SAT solver takes less time than the above method, then there'll be a contradiction because of Time Hierarchy Theorem. $\endgroup$ Mar 30, 2017 at 18:27
  • $\begingroup$ Again, consider the input, by converting, or "reducing" one problem to another you need to consider what the original input was. The reduction takes something with input of size $n$ and produces something with input size $dn^{2k}$. Meaning the SAT solver above is linear in $m$ but NOT $n$. (part 1) $\endgroup$
    – J C
    Mar 30, 2017 at 18:50
  • $\begingroup$ This was caused by the reduction, e.g. your phrasing/converting of the problem (or the one provided by Cook) and doesn't mean that the SAT solver can't still be linear. You're now solving it (the problem that is $O(n^k)$) in a way that's slower, but that's because you've increased the size of the input to the linear SAT solver by multiplying it by a polynomial. Thus we aren't contradicting the Time Hierarchy Theorem. (part 2) $\endgroup$
    – J C
    Mar 30, 2017 at 18:50
  • 1
    $\begingroup$ As a side note, based on your other NP question it seems like you would be interested in the study of how reductions work. There's a lot of tricky details like this one that reductions are meant to acknowledge and make you wary of. $\endgroup$
    – J C
    Mar 30, 2017 at 19:03
  • 1
    $\begingroup$ I get what you're saying. The input to the turing machine is of size $n$. But the size of the boolean expression is $n^{2k}$, so the size of input in the SAT solver is $n^{2k}$. This becomes the "n" of the input of the solver. So, the solver is not dealing with input the size of $n^{2k}$ but of size $n$. $\endgroup$ Mar 31, 2017 at 4:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .