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.

Read the rest of this entry »