Use of "oracles" in computational complexity.

http://en.wikipedia.org/wiki/Oracle_machine

by amichail • 17 years ago

7 5 17 years ago

en.wikipedia.org

amichail• 17 years ago

Also see http://rjlipton.wordpress.com/2009/05/21/i-hate-oracle-resul....

jey• 17 years ago

I ain't no CS theorist, so I have to ask: what does it mean for a result in TCS to "relativize"?

sp332• 17 years ago

By Wikipedia, a proof that relativizes is one that isn't affected by the addition of an oracle.

ck113• 17 years ago

To make it even more abstruse, it's not usually results that we describe as "relativizing", but proofs and proof techniques.

For example, the proof technique we call "diagonalization" relativizes. If I prove that complexity class A is contained in complexity class B, what I'm formally proving is that a Turing machine obeying the resource constraints of class B (e.g., polynomial time) can solve any problem that can be solved by a TM obeying the resource constraints of class A (e.g., logarithmic space). If I prove this by diagonalization, then I've also proved that this inclusion holds even if the Turing machines are granted access to an "oracle" that can solve problems that the machines themselves could not solve.

Here's an example of where this gets interesting: it's been proven that there are oracles relative to which P=NP, and other oracles relative to which P != NP. This means that no relativizing proof (in particular, no proof by diagonalization) can ever resolve the P vs. NP question. (See why?)

So, oracle results don't tell us too much about the actual relationships between complexity classes, but they tell us about what kind of proofs we should and shouldn't bother trying to use to prove those relationships. It's a sign of just how hard complexity theory is that it's often considered a big achievement just to get an oracle result that tells you that the other proofs you were trying will never solve your problem.

If you're really interested, this line of research now goes beyond relativization. There's another barrier to proving complexity separations called "Natural Proofs" (http://en.wikipedia.org/wiki/Natural_proof), and more recently a third has been proposed called "Algebrization", which (far as I can tell) generalizes relativization to the case where we get access not only to oracles but to low-degree polynomial extensions of oracles. (Unfortunately, if you know what that means, you were probably already aware of the new results.)

ctkrohn• 17 years ago

Funny, I just finished reading Charles Stross' novel "Accelerando," where the concept of a Turing oracle is mentioned more than once. I get the feeling that's the only time these things appear in fiction... see http://www.antipope.org/charlie/accelerando/accelerando.html and search for "oracle."

Very fun book, if a little far out. If you're itching to read a fictional account of the Singularity, you'll probably enjoy this.

Use of "oracles" in computational complexity.

Related Stories