Proof plan for P ≠ NP

Question

Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.

For each natural number $k$, we will have a formula $\phi$ of length $n$ that does the following: $\phi$ is satisfiable iff the assignment encodes a run of $M$ on $\phi$ of length $n^k$ that ends in the reject state.

Suppose SAT can be computed in time $n^k$, and let $\phi$ be the formula associated with $k$. If $\phi$ is satisfiable, then the satisfying assignment encodes a run of $M$ on $\phi$ ending in the reject state. If $\phi$ is not satisfiable, then by our assumption there is a run of $M$ on $\phi$ of length $n^k$ ending in the reject state. An encoding of this path satisfies $\phi$. Contradiction. Therefore, SAT cannot be computed in time $n^k$.

Any opinions? I'm curious if anyone has an immediate reason why this wouldn't work. (I'm quite aware that it would be difficult.)

Answer 1

Before I explain what went wrong, notice the following red flag:

Let $T(n)$ be some arbitrary function representing some run-time. What would not work from this "proof" if we replace $n^k$ by $T(n)$? From what I see, pretty much nothing. Does that mean that $SAT$ is not solveable in any run-time? of course not!

---

Now to the actual problem: Each $\Phi_k$ depends on $n$, so let us call it instead $\Phi_k^n$. Notice, that the size of $\Phi_k^n$ would not be $n$, since it takes a lot of "space" to represent this formula. In fact, its size woul most likely be way bigger than $n^k$. When you run $M$ on $\Phi_k^n$, the runtime would take $O(|\Phi_k^n|^k)\approx O((n^k)^k)$ and not $O(n^k)$, since the runtime depends on the size of the input $\Phi_k^n$. This completely nullifies your argument that this is a contradiction.

---

As a side note, if you do actually manage to encode $\Phi_k^n$ in some magical way with size $O(n)$, then congratulations! Your argument holds and $P\neq NP$. But clearly its not easy to encode it like that... good luck :)