I have been thinking about Dr Galloway’s Alternative Algorithms, particularly in relation to two of my obsessions in theoretical computer science: the P versus NP problem , and quantum computers. Here, I will try to improvise very quickly some ideas, simplifying or excluding some of the mathematical technicalities.
The P versus NP problem, probably the most central unsolved problem in theoretical computer science (you get a millions bucks if you solve it), basically asks this:
Can questions whose solution can be checked ‘easily’ can also be solved ‘easily’?
If, for a problem, there is an easy way to check whether some proposed solution to it is right, then does that immediately imply that finding that solution, from scratch, is easy too? If we can find a procedure that can check easily a solution, does that mean there will always exist a procedure that can generate easily the solution, ex nihilo? If yes, then P equals NP, otherwise P does not equal NP.
Real-world Example 1 (from Herr Brunton) - Finding a complete computational procedure for determining whether an email is spam might be an NP problem, while creating spam that escapes all spam filters might be a P problem. Real-world Example 2 - Evaluating whether a movie is good, that might be an NP problem. But making a good film by yourself, that might be a P problem. P versus NP is analogous to the question on whether great film reviewers can also, automatically, be great filmmakers. The often-heard remark from filmmakers to their critics: ‘If you’re really so good as to call my film awful, then make me a better one and show it to me!’
(Of course, defining what makes an ‘easy’ computation is itself difficult. In this case, an ‘easy’ computation is one that can be done using a polynomial amount of computation time. Mathematicians still debate this understanding of ‘easy’. An example of a non-easy computation would be one that takes an exponential amount of time to solve, like the usual ‘compare-them-all’ methods for finding the shortest route between two cities, which is not a quick computation because the time it takes to find the route increases exponentially with more roads.)
One theme invoked here is that of checking versus creating. Verifying versus constructing. Some mathematicians and computer theorists think that P is not NP because they think that figuring out a solution to a problem is fundamentally more difficult than just verifying one. Compared to finding a solution, checking it, for the most part, is usually understood to be not hard since it does not require some deep internal understanding of the problem in question. To construct a solution, you sometimes need a Eureka moment, that leap of inspiration. The question of P versus NP could also be a question about the event, the new, the rupture, and discontinuity.
Another possible dichotomy: solving by trial-and-error versus solving by figuring out ‘directly’. Brute force versus generative methods. In the former, you check all the - perhaps gazillion - possibilities one by one and discover the solution using that verifying procedure (This is sometimes possible through parallel processing or certain types of quantum algorithms): solving a problem ‘from the outside’ by searching and detecting the solutions. In the latter, you figure out the solution by just figuring it out, by thinking hard about it: solving, in a sense, ‘internally’ through constructive reasoning.
This dichotomy might be related to a particular issue about adaptive or evolutionary systems, the issue on how a family of organisms mutates in order to overcome some external obstacle. It can either do so directly, by reacting to the problem and reshaping accordingly — Lamarckism (there are many aporias about this process, this welcoming and responding, I know). Or it can adapt by brute force, by first mutating in almost all ways, and then only the mutation that is able to overcome the obstacle survives the verification, the natural selection — Darwinism. So emergence, on one hand, as single analytic reaction, and, on the other hand, as the filtering out of the whole universe of all its alternate possibilities.
But then, it could be said that some adaptations only seem direct from a macro standpoint, but are really brute-force from a micro point of view. We can iron out all these singularities, all these apparently direct adaptations, into brute-force adaptations. So, could it be that all P computations are really, deep-down, NP? Is there always an element of trial-and-error or heuristic behind every cogitation, behind every reasoning? A problem for the stability of the P versus NP binary opposition.
We often use brute force problem-solving methods in our real lives. Every heuristic or instinctual process relies on it at some stage. And statistical approaches to problem share the same ‘external’ viewpoint as brute force. So does every problem that is solvable by brute force always have a short and deep way of being solved? This has been surprisingly possible for some nontrivial cases (like checking whether a number is a prime number). But for all problems? This might be possible if we are able to handle what is known as NP-complete problems (although very little progress has been made there during the last three decades — details too technical to provide them here). If P = NP, then we can always avoid brute force solutions. If a problem has a trial-and-error way of solving it, then that problem has another simpler solution without trial-and-error. An extremely powerful possibility.
Kurt Godel, with his Incompleteness Theorem, and Alan Turing, with his Halting problem, have pointed out the limits of (certain kinds of) formal algorithms. Certain problems or statements - Godelian problems, Hilbert’s 10th, Halting, and many more yet to be determined — cannot be solved using a computer. P versus NP does not, strictly speaking, ask about the ultimate horizon of algorithms but about their pragmatic problem-solving power. So it is a post-Godelian problem, and it is interesting that Godel was one of the earliest people to formulate it explicitly (in a famous letter to Jon von Neumann, who received it in bed while dying of cancer). Is solving something ‘by accident’ — albeit with the help of some heuristic, dialectic, open source, emergent, statistical, quantum, probabilistic, or oracular method - really different from solving something ‘head on’ through deep understanding? Does it really give extra computational power? What is this ‘deep understanding’ anyway? What does it do, epistemologically, pragmatically and ontologically? Again, perhaps the difference between P and NP, and between deep understanding and brute force, is not that clear cut and is ‘open’ to deconstruction.
Another very interesting possibility is that P versus NP is really an undecidable problem: it is impossible to show if its true or not. Like the Axiom of Choice or the Continuum Hypothesis, we cannot demonstrate its truth or falsehood. Just like we cannot prove or disprove that there is a midpoint between the size of discrete infinite sets and continuous infinite sets, we cannot prove or disprove that P = NP. It is outside of logic (or at least outside the very powerful and broad ZFC logic) and maybe reason itself, in the broad sense of that word. (Speculative remark: No Aufhebung? No synthesis between P and NP? A failure of dialectic, then?).
Some mathematicians think that P versus NP is neither an important nor a deep problem. For example, it will have no bearing once quantum computers become a reality. Results in the theory of quantum algorithms — still in its infancy — might be related to the alternative algorithms that Dr Galloway called for. What we do know for now is that quantum algorithms, theoretically, have greater computational power than Turing algorithms. Problems that take an exponential amount of time to solve can now be solved more efficiently (e.g. Schor’s groundbreaking quantum algorithm for integer factorization). I remember that some physicist - or was it a mathematician? - once speculated that classical computation is to the conscious mind what quantum computation is to the unconscious mind. Certain versions of quantum algorithms can even solve Turing’s halting problem, the canonical limit for Turing machines (although they cannot solve their own quantum versions of Halting). Quantum theory has provided an enlargement to the classical Church-Turing-Post notion of algorithm, and could be said, in that sense, to be ‘alternative’.
