Relativizing relativized computations

This paper introduces a technique of relativizing already relativized computations and gives two interesting applications. The techniques developed here are simpler than the usual methods for constructing oracles that satisfy several requirements simultaneously. The first application shows that a result of Karp and Lipton (if sets in NP are decidable with polynomial-size circuits, then Σ P 2 = Π P 2) cannot be strengthened in the presence of certain oracles. This means that relativizable proof techniques cannot strengthen the conclusion to, say, P=NP. Such a stronger conclusion would be desirable as it would establish the equivalence of polynomial-time programs and polynomial-size circuits for solving NP-complete problems and would extend the known equivalence of polynomial-time programs and programs that are allowed a single query to a polynomial-size table. The second application gives an oracle C for which P C ≠ (NP C ∩ coNP C ) ≠ NP C and NP C ∩ coNP C has complete sets under polynomial-time many-one reductions. This complements a result of Sipser in which an oracle B is constructed for which NP B ∩ coNP B has no complete sets. These results suggest that current proof methods will not settle whether NP ∩ coNP has complete sets.

Authors

• Neil Immerman
• Stephen R. Mahaney

Keywords

No keywords are indexed for this paper.