My question:

  • What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists (e.g. based on the literature, most popular research directions). Take a single arbitrary program/computation. What could we learn about it if $P \not= NP$ or $P = NP$? I'll give more context to my question below.

Undecidability and P vs. NP

1) This answer explains:

"Global" complexity results such as "The halting problem is undecidable" and "Truth is undefinable", and even "The reals are uncountable" have local analogues whose proofs can be automatically extracted from the global argument but which also permit a simplicity result.

2) Many bounded versions of undecidable problems are NP problems. For example, bounded Post correspondence problem.

3) If $P = NP$, it can make undecidability largely irrelevant in practice. Because it can give us an effective algorithm for checking all possible proofs of reasonable length. Here's a quote by Gödel: (a source, wikipedia)

If there really were a machine with $φ(n) ∼ k⋅n$ (or even $∼ k⋅n2$), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem.

4) From time to time people come up with naive proof ideas which try to use undecidability or arbitrary Turing machines to prove $P \not= NP$:

I think 1-4 means that we can talk about P vs. NP in the context of undecidability and arbitrary computations. I'm not saying that undecidability resolves P vs. NP, just that we can talk about one thing in connection to the other. For example, we can say:

  • "$P = NP$ could imply that any finite part of an infinite computation has..." (has what? some invariant? some distribution? some other pattern?)
  • "$P = NP$ could imply that all/most programs which don't halt fast enough can be recognized by something like..." (like what?)

But how can we finish those sentences, based on the most popular research directions? This is my question. It can be a little broad, but I think it's justified, because more specific versions of this question can keep popping up indefinitely. It would be useful to have a general answer.

Subjective thoughts

I hope my question is objective and justified enough. However, here I want to describe some subjective thoughts which fuel my interest. You don't have to understand this part of the post to answer my question.

When you analyze a complex phenomenon in physics, you can break it down until you eventually get to "the most specific reason" which makes it true/false. For example, if you study perpetual motion engines, you can get to very specific reasons of why they are impossible. Math can be extremely different from physics. However, I think that approximately the same idea is true in math (that's just my personal philosophical position). If something is true/false, then there exists "the most specific reason" which makes it true/false.

P vs. NP problem can be viewed as talking about arbitrary Turing machines. And this problem seems very strange to me, because compared to other mathematical problems, I can't even imagine breaking it down into any possible specific facts [about arbitrary TMs]. So, I want to know what are the potential "most specific facts" [about arbitrary TMs] implied by $P = NP$. I really have absolutely no idea, no mental model of what $P = NP$ could tell us about arbitrary computations. Because arbitrary computations are supposed to be, well, "arbitrary". What exploitable patterns could exist in those computations? I may be missing some trivial possibilities.

  • 1
    $\begingroup$ The crux of your argument seems to be whether it is required to test all (or most) possible subsets of programs to find the right "combination" for $C$. A crucial flaw in many naive $P\neq NP$ proof attempts is that "I cannot possibly see how to do this except for trying all combinations" is not a proof of impossibility, and also not even close to it. However, I don't see what decidability has to do with this, can you explain this more clearly? Perhaps this question about applying an undecidable problem to P vs NP is relevant. $\endgroup$
    – Discrete lizard
    Commented Jul 26, 2023 at 12:35
  • $\begingroup$ @Discretelizard, I'm just asking a general question, not proposing any solid proof. If we have a generally unsolvable problem, then at what point, for what reasons, an effective algorithm for analyzing [bounded versions of] the problem could pop up? I.e. if $P vs. NP$ is resolved, what do mathematicians expect to learn about arbitrary Turing machines and arbitrary computations which would allow (or prohibit) an effective algorithm? I assume a non-subjective answer to this question exists, based on e.g. the literature. Maybe a partial and incomplete, but objective answer. $\endgroup$ Commented Jul 27, 2023 at 10:01
  • $\begingroup$ I just want to know how implications of $P = NP$ connect to arbitrary [undecidable] computations: e.g. "$P = NP$ would imply that any finite part of an infinite computation has... (has what? some invariant? some distribution? some other pattern?)" or "all/most programs which don't halt fast enough can be recognized by something like... (like what?)". Take just a single arbitrary program/computation. What do we learn about it if $P = NP$? Your linked answer is 100% relevant, just a little bit too abstract, not explaining what set $S$ could possibly represent. $\endgroup$ Commented Jul 27, 2023 at 10:02
  • 1
    $\begingroup$ If I understood your question correctly, it is about whether the undecidability of some problems involving Turing machines would lead to a proof of $P\neq NP$. Based on the way you phrased it, I presume you have a concrete reason to believe this might be the case. I couldn't find such a reason in your question, so it would be nice if you could clarify that. Most of the questions your raise in the comments are connected but rather broad. Please try to focus on one question at a time. $\endgroup$
    – Discrete lizard
    Commented Jul 27, 2023 at 11:14
  • $\begingroup$ As for the linked answer, it would be nice if I had a concrete algorithm to solve RH10, but I don't. It has be abstract. I have no idea what $S$ could represent or even whether such an algorithm as described exists. It is not a direct refutation, but rather an argument that a claim made without argument needs one. $\endgroup$
    – Discrete lizard
    Commented Jul 27, 2023 at 11:30

1 Answer 1


There is good evidence that what you are asking about does not occur.

Specifically, there are computable $A,B$ such that $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\not=\mathsf{NP}^B$ (this is the Baker-Gill-Solovay theorem, although there's a typo in Theorem 4.1 of the linked document, namely "$\subseteq$" should be "$=$"). The standard (and entirely correct) takeaway from this result is that no "relativizing" argument can resolve the $\mathsf{P}/\mathsf{NP}$ question, and a particular case of this is that it arguably prevents the sort of phenomenon you're asking about.

Every significant undecidability result I'm aware of highly implementation-independent: for example, the $m$-degree of the halting problem doesn't change if in its definition we replace "Turing machine" by "Turing machine with oracle $X$" for any computable $X$, or make similar tweaks. BGS-type results tell us that if we hope to see complexity-theoretic facts "reflected" somehow in computability-theoretic facts, their computability-theoretic reflections will often need to be "implementation-fragile" in a way that computability-theoretic results generally aren't.

  • $\begingroup$ Is there a typo in Theorem 4.1 that you linked to? $\endgroup$ Commented Jul 28, 2023 at 18:51
  • $\begingroup$ @AndrejBauer looks like it. But I think the text is still decent as an explanation. $\endgroup$ Commented Jul 28, 2023 at 18:52
  • $\begingroup$ @NoahSchweber, is it still possible to answer what ${P}={NP}$ could imply for arbitrary Turing machines without oracles? (You can make an ${NP}$ problem about arbitrary TMs, so I guess there should be some implications. But I can be wrong. I can be content with a negative answer.) "There does (not) exist a polynomial algorithm for ${NP}$ problems" is a high-level claim, because it doesn't specify in any way what could (dis)allow the existence of such algorithm. Is it possible to break down this high-level claim into more specific [conjectured] claims about arbitrary TMs/computations? $\endgroup$ Commented Jul 28, 2023 at 22:42
  • $\begingroup$ Sorry for a silly analogy, but right now the ${P/NP}$ question sounds to me like "could an apple become the president of USA?". Like, I understand the question on the level of abstract definitions (I know what an "apple" and "the president of USA" are, I understand that in theory there could be an abstract sequence of events leading to this absurd outcome), but I can't really imagine any specific facts which could make the "yes" answer true. Same for ${P = NP}$, I have no mental model of what it could mean in terms of specific facts [about arbitrary TMs]. $\endgroup$ Commented Jul 28, 2023 at 22:58

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.