Relativizing relativized computations. (English) Zbl 0679.68084

Summary: We introduce 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 \(\Sigma^ P_ 2=\Pi^ 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\neq (NP^ C\cap coNP^ C)\neq NP^ C\) and \(NP^ C\cap 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\cap coNP^ B\) has no complete sets. These results suggest that current proof methods will not settle whether NP\(\cap coNP\) has complete sets.


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P = ?NP question, SIAM J. comput., 4, 431-442, (1975) · Zbl 0323.68033
[2] Baker, T.; Selman, A., A second step toward the polynomial hierarchy, Theoret. comput. sci., 8, 177-187, (1979) · Zbl 0397.03023
[3] Berman, L.; Hartmanis, J., On isomorphism and density of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059
[4] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (), 63-71
[5] J. Hartmanis, N. Immerman, On complete problems for NP ∩ coNP, in: Twelfth International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science {\bf194} (Springer, Berlin) 250-259.
[6] Heller, H., On relativized exponential and probabilistic complexity classes, Inform. and control, 71, 231-243, (1986) · Zbl 0628.68047
[7] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[8] Immerman, N.; Mahaney, S., Oracles for which NP has polynomial size circuits, (), 89-93
[9] Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (), 302-309
[10] Li, M., Lower bounds in computational complexity, ()
[11] Mahaney, S., Sparse complete sets for NP: solution of a conjecture of berman and hartmanis, J. comput. systems sci., 25, 130-143, (1982) · Zbl 0493.68043
[12] M. Sipser, On relativization and the existence of complete sets, Ninth International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science {\bf140} (Springer, Berlin) 523-531. · Zbl 0515.68040
[13] Stockmeyer, L.J., The polynomial time hierarchy, Theoret. comput. sci., 3, 1, 1-22, (1974) · Zbl 0353.02024
[14] Wilson, C., Relativized circuit complexity, J. comput. systems sci., 31, 169-181, (1985) · Zbl 0583.68023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.