1
$\begingroup$

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.)

Improve this question
$\endgroup$
7
  • $\begingroup$ Please use MathJax to improve the formatting of your post. $\endgroup$
    – Nathaniel
    Commented May 18, 2021 at 20:44
  • $\begingroup$ How do you encode $\phi$ in length $n$? $\endgroup$
    – Yuval Filmus
    Commented May 18, 2021 at 20:59
  • $\begingroup$ Does your argument refute the time hierarchy theorem, by any chance? $\endgroup$
    – Yuval Filmus
    Commented May 18, 2021 at 20:59
  • $\begingroup$ You are claiming to have a solution for a well-known, difficult open problem. This is an extraordinary claim requiring extraordinary evidence. You have not provided such so there is not much to talk about. Even if you had, this would not be a good post for SE; it is not our goal here to make broad advances to science in a single post. See here for a related discussion. $\endgroup$
    – Raphael
    Commented May 18, 2021 at 21:41
  • $\begingroup$ What's more, proof-checking questions are also not well-suited for this platform. What's a specific question you have about your proof outline? $\endgroup$
    – Raphael
    Commented May 18, 2021 at 21:42

1 Answer 1

Reset to default
2
$\begingroup$

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 :)

Improve this answer
$\endgroup$
8
  • $\begingroup$ I haven't figured out how to properly format my responses yet, my apologies. First of all, this is not a proof, it's not remotely close to being a proof, it's just an idea. When I say that the length of phi_k is n, I mean that the length of the representation of phi_k is n. $\endgroup$
    – Brian
    Commented May 18, 2021 at 21:35
  • $\begingroup$ Yes, the problem is that you cant have the length of the representation of $\Phi_k^n$ to be $n$, but also to contain the expression of $M(\phi)=false$ for $\phi$ of length $n$, since that expression is most likely to take up at least $n^k$. $\endgroup$
    – nir shahar
    Commented May 18, 2021 at 22:02
  • $\begingroup$ The length of phi_k by definition is n. I'm using n to represent the length of the input. The variable n doesn't represent anything else. The idea is to represent this particular path of M in a short way. It would have to be something new. I don't know how to do it, I'm just tossing around the idea. $\endgroup$
    – Brian
    Commented May 19, 2021 at 23:10
  • $\begingroup$ if $\Phi_k^n$ is of length $n$ then it represents a computation of $M$ on some extremely short input, something that is way smaller than $n$. $\endgroup$
    – nir shahar
    Commented May 20, 2021 at 6:54
  • $\begingroup$ We would need a new way to represent computations of M (not all computations, just some special ones). If the formula is of length n and M is bounded by n^k, then the length of the computation would be n^k in the worst case. I agree, a formula of length n can't handle something of size n^k. We couldn't just list the transitions or have a computation tableau. We would need an entirely new method. The number 2^10^10^80 has more digits than there are particles in the universe, but we can represent it in a concise way. We would have to do something similar for M. $\endgroup$
    – Brian
    Commented May 20, 2021 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.