# Oracles and relativization in non-TM settings

I am looking to understand relativization in non-Turing Machine settings. For example, what is the "natural" relativization of Graph Isomorphism to an oracle A? How about HAMPATH?

Specifically, they say that relativization is an obstacle to proofs of $P?NP$ because there are oracles A relative to which $P^A=NP^A$ and oracles B relative to which $P^B \neq NP^B$.

However, consider e.g. HAMPATH and the following oracle A: A is a function that takes a number n to some number in $[n!]$. So you pass it $(n,x)$ and it tells you if $x=A(n)$. So you solve HAMPATH and if you find a hamiltonian path you pass it to A to see if it is "valid". That turns HAMPATH into HAMPATH + an exponential search, so $HAMPATH^A$ is provably not in $P^A$ (and $NP^A \neq P^A$).

Now, why would this be an obstacle to a proof of $P=NP$? If you claim that your algorithm solves HAMPATH in polynomial time, it obviously won't solve $HAMPATH^A$ in polynomial time with polynomial calls to the oracle. Relativization would only be an obstacle if your algorithm would also run in polynomial time in situations where $P^A \neq NP^A$, but it obviously doesn't for this oracle. How do we know that there are separating oracles where this is less obvious? Why is relativization a compelling argument?

In general, what does an oracle look like in a graph theory setting?

-

It's an "obstacle" in the sense that any proof of $P=NP$ or $P\ne NP$ will have to contain at least one core step that is not valid relative to arbitrary oracles.

This means that solutions will necessarily have to consider more low-level details of actual computation mechanisms than if they could stay very abstract and say, "consider some cost model and any class of problems that is closed under such-and-such operations ..."

It's not clear to me why you would think this looks any different with graph-related problem specifically.

-
Okay, thank you! That's very helpful. And I'm not looking at $P?NP$ in a graph theory context necessarily, the second part of my question is if there is some natural way to define a relativized version of a graph theory question -- I didn't think my example was particularly natural. –  Craig Sep 2 '11 at 14:30
@Craig, not entirely clear what you're looking for. For example, "Assume that you have a (linear-time) oracle for graph isomorphism; how hard would it then be to decide Hamiltonian paths?" sounds like a fairly natural way to state a relativized problem about graphs. –  Henning Makholm Sep 2 '11 at 14:58
Going back to the $P?NP$ setting, I don't really have a good understanding of what an $NP^A$-complete problem might look like. Or even if that concept makes sense. For an arbitrary oracle A, is there a nice type of problem such that all problems in $NP^A$ are polynomial-time reducible to a problem of that type? –  Craig Sep 2 '11 at 15:26
I think you'd get a NP^A-complete problem by defining a programming language that has a primitive A operation and asking: "Given a program and a time bound, is there any input that will make the program terminate within the given time bound?". Possibly you'd need to express the time bound in unary. I'm not sure you would consider this a nice problem, but I doubt there are more natural constructions that work for arbitrary oracles. –  Henning Makholm Sep 2 '11 at 15:57