Complexity first:

The “P vs. NP” issue revolves around that “N”, which means “nondeterministic.” If it were possible to invoke, employ, and use nondeterministic methods, then all of the intractable problems of “P” could be crushed in a stroke. This is interesting mathematically, but terrifying from a practical point of view. Because all of your private information – your bank accounts, credit cards, messages, emails, web sites you visit, etc. – lives and dies on the intractable problem of cracking encryption, a “P” form of intractable. If there is a way of realizing NP problem solving, then all of your privacy is erased in a stroke.

There may be a way. It is called “Quantum Computing” (QC). QC is based upon the idea of exploiting quantum in-determinacy to realize an operational form of that N(on-deterministic)P computing. Frankly, unless you’re some really over-the-top savant in both physics and mathematics, you’ll have a better chance of explaining how ordinary semiconductors work to your cat than ever making sense of how QC is supposed to work. Understanding how electrons are shuffled from the shell of one atom to another, thus opening or blocking the flow of other electrons, is Dick and Jane level material compared to making sense of how a quantum bubble of indeterminacy is supposed to be opened at will and exploited to simultaneously solve all sides of a puzzle at once. That quantum bubble will “collapse” the instant it is observed, and in so doing force a “solution” to come out the other end. But for a general purpose computer, it would then have to be opened again (which ought to be impossible; just saying) so that another computation can be performed. Because if it can’t do multiple computations, it doesn’t even qualify as a carnival sideshow stunt. (Like the old Daffy Duck cartoon, “the only problem is, I can only do it once.”)

If these problems are solved, the effect will be civilization changing. Nothing on the internet, nothing connected to the internet, nothing even occasionally connected to the internet, will be even remotely secure. But everything is connected to the internet, and it all depends on security: our businesses, our infrastructure, our government, our personal phones, our personal computers, our personal lives. We would be looking at a return to hard-wired landlines for our phones (an end to mobility), and setting up a SCIFⁱ for all of our personal data.

Computability presents a less dire set of choices and problems. The one theoretical work around is also only a partial work around. Known as “relative computability” it is the idea of regular computability that has been augmented with an “oracle function.” The oracle – not to be confused with the database manufacturing company – is like the priestesses of Delphi, and can channel an answer to a yes-or-no question basically from the gods.ⁱⁱ This question will typically not be computable itself. This might strike one as flat out cheating, selling the pass, but it is less of a give away than you might suppose. Even granting a countably infinite (the size of the set of integers) number of oracles, the number of unsolvable problems exceeds that of the solvable ones by the same scale that the real numbers exceeds that of the mere rational ones.

Which brings me to the tie-in with science:

For any theory to qualify as even remotely scientific, it must be relatively computable with only a finite number of oracles.

This is actually a wildly generous criterion. I’m willing to allow for many “Sid Harris step-two moments” (And then a miracle occurs),ⁱⁱⁱ while still requiring that the theory be capable of producing results. This places a significant bound on what kinds of claims can qualify as scientific, without even getting into issues of complexity. For instance, one can, “in principle,”^iv have an infinite string of oracles, “miracles happening,” but it defies the imagination how such an infinite collection could have any meaning in practice. One still remains limited to just and only those theories which are genuinely, TM computable, as having any possible scientific content.

And the issue of complexity is still with us. As a practical matter, any putative scientific theory that defies the bounds of computational complexity will never be more than “scientific” in name; in terms of actual research, it will be all but totally useless. I am inclined to say it would be totally useless, but I cannot discount the possibility that such a theory could nevertheless suggest tractable lines of actual research. (In much the way that metaphysics – which I clearly do approve of – can make such suggestions.) Certainly any scientific concept or principle which is going to be realized in application must fall within the scope of what is computationally tractable. But clearly not every concept that can be formulated need fit into such narrow confines. The very existence of unsolvable mathematical problems and intractable computing processes – that humans nevertheless imagined, conceived of, and formulated – proves that we can formulate more than we can act upon.

But our ability to analyze, to give analytical accounts of/for, things we can imagine &/or experience, remains fundamentally limited. And for this reason, it is a critical error – a primary category mistake – to try and conflate that which we can analyze with that which is real. This latter includes both that which exists in the concrete and that which is either possible or relationally real. Thus, for example, those speculations that go something like, “the universe is a computer program,” are annoying and superficial to the point of childish. They all collapse what is analytically possible into what is ontologically possible, and seriously, who these days is so uneducated as to do that?

This brings us back to Whitehead. One of the strengths of his system is that he eschews any possibility of such a collapse. Experience is radically bigger than what we can say about experience. This was already explicit in his 1920 Concept of Nature, and developed in more detail in his 1929 Process and Reality. (Both works significantly predate Gödel’s theorems, never mind Turing.) The limits of analyzing process do not define process.

– – – – – – – – – –

i Sensitive Compartmented Information Facility, often built inside a Faraday Cage to prevent any electromagnetic signals from being sent or received, either accidentally or through deliberate espionage.

ii Giving away my age here, I always think of Donald Pleasence’s character in the film Hallelujah Trail, “Oracle Jones.” Any time his name is mentioned, there’s a rising chorus in the background singing HALLELUJAH. Lest you had any lingering doubts, the film is a comedy. In any event, every time I think of an oracle function, I hear that hallelujah chorus.

iii Sid Harris was an incredibly funny cartoonist. Perhaps his most famous cartoon – ideally linked to in the above – is of two scientists at a chalkboard with formulae on the left and right, linked together in the middle by the phrase “And then a miracle occurs.” Pointing to this, one scientist says to the other, “I think you need to be more explicit in step two.”

iv Which is to say, one can pretend for mathematical purposes that such an infinite collection exists and is operable, and still produce intelligible mathematics.