What could $P = NP$ imply about arbitrary Turing machines?

Question

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

• Diophantine equations and P vs. NP (can an undecidable problem be in NP? and more), inputs to arbitrary Turing machines and P vs. NP and more, irreducible problems (not a proof idea by itself), NP vs. coNP ("proof by definition", not involving undecidability or TMs). One can come up with endless versions of problems involving arbitrary Turing machines or diophantine equations. I was about to make a question about yet another naive proof attempt.

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.

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.