Abstract It is known that no classical diagonal argument -and few classical arguments- are sufficiently strong to decide between P = NP and P != NP. The reason is that these arguments tend to “relativize”, meaning that they are equally valid in our world, where computation costs time, and in fantasy-worlds where -thanks to the ability of Turing machines to query oracles- it is for free. But in some of these fantasy-worlds, P = NP, while in others, P != NP… An exception is the halting theorem. An oracular Turing machine can decide whether particular Turing machines will halt on particular inputs, but it cannot decide, in general, whether a Turing machine will halt, because it cannot decide if Turing machines equivalent to itself will halt. This creates a hierarchy of machines, each with a more powerful oracle, and a higher order halting problem. In this note, the argument that the inequality of P and NP is a consequence of this extended form of the halting problem is presented in parable form.
In a story co-authored with Adolfo Caesars called Del Rigor en la Ciencia, or On Exactitude in Science, Jorge Luis Borges tells of a map of an empire that is identical with that empire:
A map is a way of finding a location in an unknown territory without performing an exhaustive search of that territory, and if we have no map, or if -equivalently- the smallest map we have of a territory is the same size as that territory itself, then as the size of the territory grows arithmetically, the number of places we have to search in order to find our location grows exponentially (a complete graph of n vertices has for example 1/2 (n-1)! Hamiltonian cycles). Non-metaphorically, when the smallest program we have to operate on an input is as complex as that input itself, then as the complexity of the input grows arithmetically, it is inevitable that the number of operations grows exponentially. More generally, a scientific theory can be regarded as a computer program for predicting observations, and if the smallest program we have is as complex as the data-set itself, then as the complexity of the data-set grows arithmetically, the number of operations needed to analyze the data and make a prediction grows exponentially. In a fantasy-world where computation is free, it is possible that P = NP; but in the real world, where there are exponentially steep time-costs to be paid by computational devices running self-inputs, P != NP…
Baker, T (1975), et al, Relativizations of the P=?NP question
Börger, E (1989), Computability, Complexity, Logic
Borges, Jorge, Luis (1975), A Universal History of Infamy
Turing, Alan (1936-37), On Computable Numbers, with an Application to the Entscheidungsproblem
Turing, Alan (1939), Systems of Logic Based on Ordinals