2
$\begingroup$

Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is an expressiveness question, but I have not seen such a construction before.

Update: There are competitions to construct the smallest TM that halts iff Goldbach is false. The current record is 27 states. Basically the TM puts successively larger even numbers in unary on the tape and checks if there is a cut dividing the unary even number into two primes. This is the spirit that I intended; my question is not about existential, nonconstructive arguments or provability from ZFC.

$\endgroup$
2
  • 2
    $\begingroup$ Yes. Consider the following two Turing machines on some alphabet $\Sigma$: (i) The initial state coincides with the final state, so the machine halts immediately (ii) The initial state $q_0$ differs from the final state, and the transition function $f$ is such that $f(q_0, x) = \langle q_0, x, \mbox{stay} \rangle$ for every $x \in \Sigma \cup \{ \varepsilon \}$. Either (i) or (ii) satisfy your condition. $\endgroup$
    – Steven
    Oct 31, 2020 at 13:30
  • 2
    $\begingroup$ What I think @Steven is trying to tell you is that you want to ask your question a bit more carefuly. You could try: Construct a specific Turing machine $M$ and prove that $M$ halts iff $\mathrm{P} = \mathrm{NP}$. $\endgroup$ Oct 31, 2020 at 14:48

3 Answers 3

3
$\begingroup$

You are asking whether there is a concrete TM for which we know that its halting is equivalent to $\mathrm{P} = \mathrm{NP}$. An alternative phrasing is whether we know $\mathrm{P} = \mathrm{NP}$ to be equivalent to specific $\Sigma_1$-statement. The answer is no.

We know that $\mathrm{P} = \mathrm{NP}$ is equivalent to "There exists a polynomial-time algorithm that solves SAT." So we might hope to obtain our hypothetical TM by searching through all possible polytime algorithms and halt if we find one that solves SAT. The problem is that we can not decide whether a given polytime algorithm solves SAT or not.

So to see the actual complexity of $\mathrm{P} = \mathrm{NP}$ we should phrase it as:

"There exists ($\exists$) a polytime algorithm $A$ such that for all ($\forall$) propositional formulas $\phi$ the algorithm $A$ correctly determines whether or not $\phi$ is satisfiable".

Hence, $\mathrm{P} = \mathrm{NP}$ is $\Sigma_2$, and we can easily built a TM that will definitely run forever, and output finitely many $1$'s iff $\mathrm{P} = \mathrm{NP}$. Maybe someone will prove $\mathrm{P} = \mathrm{NP}$ to be equivalent to a concrete $\Sigma_1$ or $\Pi_1$ question before it is resolved. but to date no such result is known.

$\endgroup$
8
  • $\begingroup$ The quantifier argument is nonsense. But no machine can decide whether a given machine solves SAT; that’s Rice’s theorem. Are there clever ways to avoid this? The question does not require searching for TMs. $\endgroup$
    – Zirui Wang
    Jul 27, 2021 at 15:16
  • $\begingroup$ The quantifier stuff is essential to understand this issue. As I mentioned, P=NP is not known to be equivalent to any concrete statement of complexity less than $\Sigma_2$; hence if there is a clever way around this, noone has found it. $\endgroup$
    – Arno
    Jul 27, 2021 at 15:21
  • $\begingroup$ Rice’s theorem says there is no TM that decides 1) a given TM runs in polynomial time, 2) a TM solves SAT. But it doesn’t say that there is no TM that decides both, because the intersection could be empty. So this is not Rice’s theorem. Why do you think it can’t be done? By the way, Rice’s theorem says no TM can divide the set of all TMs into two nontrivial partitions by accepting one set and rejecting the other. $\endgroup$
    – Zirui Wang
    Jul 27, 2021 at 15:40
  • $\begingroup$ We don't need to worry about the time-complexity, we can enforce that using clocks. If we knew that $P \neq NP$, then we of course could decide whether a polytime algorithm solves SAT. But lacking this knowledge, the same argument as for Rice' goes through. $\endgroup$
    – Arno
    Jul 27, 2021 at 15:45
  • $\begingroup$ There exists a number $x$ such that for all natural number $y$, $x < y$. This is a $\Sigma_2$ statement, but it can be easily decided to be true. Quantifier arguments are meaningless. You don’t have to search for $x$ and then $y$. $\endgroup$
    – Zirui Wang
    Jul 27, 2021 at 15:53
1
$\begingroup$

The answer to your question is formally "yes". This is because one possible Turing machine that halts iff P=NP is either (i) a Turning machine that always halts or (ii) a Turing machine that never halts (regardless of its input).

However, the following argument might be closer in spirit to what you are asking: Assume that $P=NP$ is not independent from the axioms you are (implicitly) using. Since proofs are enumerable you could build a Turing machine $T$ that iterates over all "candidate proofs" that P=NP. When a candidate proof $\pi$ is considered, $T$ checks whether $\pi$ is an anctual proof. If it is, $T$ halts immediately. If it isn't, $T$ continues with the next candidate proof. It follows that $T$ halts iff $P=NP$.

$\endgroup$
3
  • $\begingroup$ A Turing machine is a Turing machine. It does not rely on any axioms whatsoever, it just executes its steps and halts after some finite number $t$ steps, or never. It will always do exactly this, independent of what you (implicitly) assume. So I don't see why you mention axioms in your answer. $\endgroup$
    – orlp
    Oct 31, 2020 at 17:38
  • $\begingroup$ @orlp That is not needed for the Turing machine T to run but if P=NP is an independent statement then T will never find a proof for it. I don't know how to deal with this case, so I excluded it by only considering worlds where P=NP is not independent. Actually, I would appreciate any comment about this issue... $\endgroup$
    – Steven
    Oct 31, 2020 at 18:02
  • 8
    $\begingroup$ The second paragraph is misleading, it teaches people to confuse truth and provability. $\endgroup$ Oct 31, 2020 at 22:54
-1
$\begingroup$

1 The problem is somewhat more complicated in spirit to Goldbach and similar problems (FLT, ZFC): You certainly can invent a TM that solves instances of 3-SAT (in exp time) as you can check instances of Goldbach.

2 You want to know however whether there is a faster TM and which is the fastest one. Since there are faster and faster machines (eg by recoding) none of which are subexponential though, this does not constitute proof of N=NP, neither does it yield a lower bound on time complexity.

3 Hence, what you can do is

(a) fix an encoding of 3-SAT formulae.

(b) test for satisfiability (in exp time)

(c) run "all" TMs (ie all algorithms, all proofs) against larger and larger instances of 3-SAT. these

  • (i) will provide wrong answers: discard
  • (ii) will provide correct answers: check time behaviour for larger and larger instances
  • (iii) will not halt sometimes, the (in)famous halting problem: keep in list and simulate further (will eventually drop out by exceeding any time bound).

From (ii) you obtain upper bounds on the timing behaviour. Discard any machines with $T(d) > n\cdot |d|^n$, $d$ the description of the 3-SAT instance, n a growing parameter.

Ingeniously mix TMs, 3-SAT instances, time bound parameter values $n$ ... Eventually you have no machine left for a given fixed $n$, with $n\to\infty$ discarding P=NP, or else some TM (require $n > |TM|$ or so) is the solution for all say $|d| \leq n^{n^n}$, P$\doteq$NP. You are famous!

(Well, almost: you will have a machine that correctly decides 3-Sat in poly time for some (not so) small instances, $|d| \leq n^{n^n}$ ... and $|TM|$ far smaller - it is then up to you to mathematically prove the correctness (and speed) for any $|d|$. But you have an algorithm to begin with.)

Same problem here as with Goldbach: Showing P=NP is OK (like a counterexample to Goldbach), disproving it requires "infinite time" - you actually never disprove. You have an $P\neq NP$-checker (for a finite, but arbitrary large, set of instances!) as you have a Goldbach-checker (which is what you are asking for in your question).

$\endgroup$

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.