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.

  • $\begingroup$ 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. $\endgroup$ – Craig Sep 2 '11 at 14:30
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Sep 2 '11 at 14:58
  • $\begingroup$ 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? $\endgroup$ – Craig Sep 2 '11 at 15:26
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Sep 2 '11 at 15:57

Relativization is usually defined for specific models of computation (not problems or sets of problems), and even in that context there is not always a consensus on what is the right way of defining the relativized version of the model.

Relativization is an obstacle for separating P from NP because it shows that any proof separating P from NP needs to do something that does not relativize. (On the other hand, if you are proving that they are equal then it is not an obstacle, but most experts think that is not the case). The problem is that we don't have that many non-relativizing methods, we really don't understand what a possible polynomial algorithms can do to argue that none can solve a problem like HamPath, we need to use very general methods that will take care of all polynomial time algorithms and there are very few such methods.

I don't remember a general way of defining a relativized version of a concrete problem like HamPath. Why would you like to define such a problem in the first place?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.