Strong self-reducibility precludes strong immunity
Tóm tắt
Do self-reducible sets inherently lack immunity from deterministic polynomial time? Though this is unlikely to be true in general, in this paper we prove that sufficiently strong self-reducibility precludes sufficiently strong immunity from deterministic polynomial time. In particular, we prove that NT isnot P balanced immune. However, we prove that NT, a class whose sets have very strong self-reducibility properties, is P bi-immune relative to a generic oracle. Thus, the previous result cannot be relativizably extended to bi-immunity. We also prove that NP and ⊕P are both P balanced immune relative to a random oracle; the former provides the strongest known relativized separation of NP from P.
Tài liệu tham khảo
E. Allender. Oracles versus proof techniques that do not relativize. InProceedings of the 1990 SI-GAL International Symposium on Algorithms, pages 39–52. Lecture Notes in Computer Science, Vol. 450. Springer-Verlag, Berlin, 1990.
L. Babai. A random oracle separates PSPACE from the polynomial hierarchy.Information Processing Letters, 26(1):51–53, 1987.
R. Beigel. Bi-immunity results for cheatable sets.Theoretical Computer Science, 73:249–263, 1990.
C. Bennett and J. Gill. Relative to a random oracleA, PA ≠ NPA ≠ coNPA with probability 1.SIAM Journal on Computing, 10:96–113, 1981.
T. Baker, J. Gill, and R. Solovay. Relativizations of the P =? NP question.SIAM Journal on Computing, 4(4):431–442, 1975.
M. Blum and R. Impagliazzo. Generic oracles and oracle classes. InProceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 118–126, October 1987.
D. Bruschi. Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets.Theoretical Computer Science, 102:215–252, 1992.
J. Balcázar and U. Schöning. Bi-immune sets for complexity classes.Mathematical Systems Theory, 18:1–10, 1985.
J. Cai. Probability one separation of the Boolean hierarchy. InProceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pages 148–158. Lecture Notes in Computer Science, Vol. 247. Springer-Verlag, Berlin, 1987.
J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-timehierarchy.Journal of Computer and System Sciences, 38(1):68–85, 1989.
R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Håstad, and D. Ranjan. The random oracle hypothesis is false.Journal of Computer and System Sciences, 49:24–39, 1994.
J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties.SIAM Journal on Computing, 17(6):1232–1252, 1988.
J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications.SIAM Journal on Computing, 18(1):95–111, 1989.
M. Dowd. Generic oracles, uniform machines, and codes.Information and Computation, 96:65–76, 1992.
D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener. Simultaneous strong separations of probabilistic and unambiguous complexity classes.Mathematical Systems Theory, 25(1):23–36, 1992.
S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit. InProceedings of the 8th Structure in Complexity Theory Conference, pages 120–131. IEEE Computer Society Press, New York, 1993.
L. Fortnow. The role of relativization in complexity theory.Bulletin of the EATCS, (52):229–244, 1994.
J. Foster. The generic oracle hypothesis is false.Information Processing Letters, 45:59–62, 1993.
L. Fortnow and M. Sipser. Are there interactive protocols for co-NP?Information Processing Letters, 28:249–251, 1988.
J. Geske. Nondeterminism, bi-immunity and almost-everywhere complexity.IEICE Transactions on Communications/Electronics/lnformation and Systems, E76, 1993.
J. Geske and J. Grollmann. Relativizations of unambiguous and random polynomial time classes.SIAM Journal on Computing, 16(2):511–519, 1986.
J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young. Near-testable sets.SIAM Journal on Computing, 20(3):506–523, 1991.
J. Gill. Computational complexity of probabilistic Turing machines.SIAM Journal on Computing, 6(4):675–695, 1977.
J. Goldsmith, D. Joseph, and P. Young. Self-reducible, P-selective, near-testable, and P-cheatable sets: The effect of internal structure on the complexity of a set. InProceedings of the 2nd Structure in Complexity Theory Conference, pages 50–59, 1987.
J. Goldsmith, D. Joseph, and P. Young. A note on bi-immunity and p-closeness of p-cheatable sets in P/Poly.Journal of Computer and System Sciences, 46:349–362, 1993.
L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions.Theoretical Computer Science, 43:43–58, 1986.
J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems.SIAM Journal on Computing, 17(2):309–335, 1988.
R. Gavaldà, L. Torenvliet, O. Watanabe, and J. Balcázar. Generalized Kolmogorov complexity in relativized separations. InProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, pages 266–276. Lecture Notes in Computer Science, Vol. 452. Springer-Verlag, Berlin, 1990.
J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi. Relativization: A revisionistic retrospective.Bulletin of the EATCS, (47): 144–153, 1992.
J. Hartmanis, R. Chang, D. Ranjan, and P. Rohatgi. Structural complexity theory: Recent surprises. InProceedings of the 2nd Scandinavian Workshop on Algorithm Theory, pages 1–12. Lecture Notes in Computer Science, Vol. 447. Springer-Verlag, Berlin, 1990.
L. Hemaspaandra and S. Jha. Defying upward and downward separation.Information and Computation, 121(1):1–13, 1995.
L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust Turing completeness.International Journal of Foundations of Computer Science, 4(3):245–265, 1993.
L. Hemachandra and R. Silvestri. Easily checked generalized self-reducibility.SIAM Journal on Computing, 24(4):840–858, 1995.
S. Kurtz, S. Mahaney, and J. Royer. Average dependence and random oracles. InProceedings of the 7th Structure in Complexity Theory Conference, pages 306–317. IEEE Computer Society Press, New York, 1992.
K. Ko. A note on separating the relativized polynomial time hierarchy by immune sets.RAIRO Theoretical Informatics and Applications, 24(3):229–240, 1990.
S. Kurtz. Notions of weak genericity.Journal of Symbolic Logic, 48:764–770, 1983.
S. Kurtz. On the random oracle hypothesis.Information and Computation, 57:40–47, 1983.
H. Müller. A note on balanced immunity.Mathematical Systems Theory, 26:157–167, 1993.
M. Mundhenk and R. Schuler. Random languages for nonuniform complexity classes.Journal of Complexity, 7:296–310, 1991.
C. Papadimitriou and S. Zachos. Two remarks on the power of counting. InProceedings of the 6th GI Conference on Theoretical Computer Science, pages 269–276. Lecture Notes in Computer Science, Vol. 145. Springer-Verlag, Berlin, 1983.
H. Rogers, Jr.The Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
K. Regan and J. Royer. On closure properties of bounded 2-sided error complexity classes.Mathematical Systems Theory, 28:229–244, 1995.
A. Shamir. IP = PSPACE.Journal of the ACM, 39(4):869–877, 1992.
U. Schöning and R. Book. Immunity, relativization, and nondeterminism.SIAM Journal on Computing, 13:329–337, 1984.
L. Torenvliet. Structural concepts in relativized hierarchies, 1986. Ph.D. thesis, Universiteit van Amsterdam.
L. Torenvliet and P. van Emde Boas. Diagonalization methods in a polynomial setting. InProceedings of the 1st Structure in Complexity Theory Conference, pages 330–346. Lecture Notes in Computer Science, Vol. 223. Springer-Verlag, Berlin, 1986.
L. Torenvliet and P. van Emde Boas. Simplicity, immunity, relativizations and nondeterminism.Information and Computation, 80:1–17, 1989.
N. Vereshchagin. Relationships between NP-sets, co-NP-sets, and P-sets relative to random oracles. InProceedings of the 8th Structure in Complexity Theory Conference, pages 132–138. IEEE Computer Society Press, New York, 1993.
R. Wilber. Randomness and the density of hard problems. InProceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 335–342. IEEE Computer Society Press, New York, 1983.