You are currently browsing the tag archive for the ‘relativisation’ tag.

The most fundamental unsolved problem in complexity theory is undoubtedly the P=NP problem, which asks (roughly speaking) whether a problem which can be solved by a non-deterministic polynomial-time (NP) algorithm, can also be solved by a deterministic polynomial-time (P) algorithm. The general belief is that ${P \neq NP}$, i.e. there exist problems which can be solved by non-deterministic polynomial-time algorithms but not by deterministic polynomial-time algorithms.

One reason why the ${P \neq NP}$ question is so difficult to resolve is that a certain generalisation of this question has an affirmative answer in some cases, and a negative answer in other cases. More precisely, if we give all the algorithms access to an oracle, then for one choice ${A}$ of this oracle, all the problems that are solvable by non-deterministic polynomial-time algorithms that calls ${A}$ (${NP^A}$), can also be solved by a deterministic polynomial-time algorithm algorithm that calls ${A}$ (${P^A}$), thus ${P^A = NP^A}$; but for another choice ${B}$ of this oracle, there exist problems solvable by non-deterministic polynomial-time algorithms that call ${B}$, which cannot be solved by a deterministic polynomial-time algorithm that calls ${B}$, thus ${P^B \neq NP^B}$. One particular consequence of this result (which is due to Baker, Gill, and Solovay) is that there cannot be any relativisable proof of either ${P=NP}$ or ${P \neq NP}$, where “relativisable” means that the proof would also work without any changes in the presence of an oracle.

The Baker-Gill-Solovay result was quite surprising, but the idea of the proof turns out to be rather simple. To get an oracle ${A}$ such that ${P^A=NP^A}$, one basically sets ${A}$ to be a powerful simulator that can simulate non-deterministic machines (and, furthermore, can also simulate itself); it turns out that any PSPACE-complete oracle would suffice for this task. To get an oracle ${B}$ for which ${P^B \neq NP^B}$, one has to be a bit sneakier, setting ${B}$ to be a query device for a sparse set of random (or high-complexity) strings, which are too complex to be guessed at by any deterministic polynomial-time algorithm.

Unfortunately, the simple idea of the proof can be obscured by various technical details (e.g. using Turing machines to define ${P}$ and ${NP}$ precisely), which require a certain amount of time to properly absorb. To help myself try to understand this result better, I have decided to give a sort of “allegory” of the proof, based around a (rather contrived) story about various students trying to pass a multiple choice test, which avoids all the technical details but still conveys the basic ideas of the argument. This allegory was primarily for my own benefit, but I thought it might also be of interest to some readers here (and also has some tangential relation to the proto-polymath project of determinstically finding primes), so I reproduce it below.