Is it possible to demonstrate that a sentence must be formally independent based on the fact that it is non-relativizing? In other words, are there examples of sentences in computability/complexity theory where it can be demonstrated both a) that all proofs that resolve the question of whether or not two classes are equal must relativize, and b) that there are no relativizing proofs that can be used in such a resolution?

I think that results satisfying part b would be easier to come by. Another way to ask this question is: Has there ever been a sentence in computability or complexity theory where it can be demonstrated that the equality or inequality must be established through the use of (and only through the use of) relativizing techniques? An example of this would be interesting to me.

Thanks; an answer to either version of this question would be very interesting to me.



1 Answer 1


There are no "natural" complexity-theory questions that have been proved independent of really powerful formal systems, such as ZF set theory or Peano Arithmetic. (One could certainly construct such a question artificially, by playing games with Gödel sentences.)

On the other hand, yes, you can interpret the statement that a sentence S relativizes as meaning that S can be proved from a certain restricted set of axioms (basically, the "Cobham axioms" that characterize closure under polynomial-time reductions). Conversely, the existence of oracles making S either true or false is equivalent to S being independent of those particular axioms. Here's the paper to read about this, by Arora, Impagliazzo, and Vazirani.

This is a very pretty connection mathematically---but it's worth stressing that we do have techniques (such as arithmetization) that go outside the relativizing axioms. And I don't know of any results of the form "if natural open problem P can be solved at all, then it can also be solved in a relativizing way."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.