{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:38Z","timestamp":1759637738057},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1996,10,1]],"date-time":"1996-10-01T00:00:00Z","timestamp":844128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1996,10]]},"DOI":"10.1007\/bf01184814","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T16:49:25Z","timestamp":1108745365000},"page":"535-548","source":"Crossref","is-referenced-by-count":15,"title":["Strong self-reducibility precludes strong immunity"],"prefix":"10.1007","volume":"29","author":[{"given":"L. A.","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"M.","family":"Zimand","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01184814_CR1","first-page":"39","volume-title":"Lecture Notes in Computer Science, Vol. 450","author":"E. Allender","year":"1990","unstructured":"E. Allender. Oracles versus proof techniques that do not relativize. InProceedings of the 1990 SI-GAL International Symposium on Algorithms, pages 39\u201352. Lecture Notes in Computer Science, Vol. 450. Springer-Verlag, Berlin, 1990."},{"issue":"1","key":"BF01184814_CR2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0020-0190(87)90036-6","volume":"26","author":"L. Babai","year":"1987","unstructured":"L. Babai. A random oracle separates PSPACE from the polynomial hierarchy.Information Processing Letters, 26(1):51\u201353, 1987.","journal-title":"Information Processing Letters"},{"key":"BF01184814_CR3","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(90)90177-J","volume":"73","author":"R. Beigel","year":"1990","unstructured":"R. Beigel. Bi-immunity results for cheatable sets.Theoretical Computer Science, 73:249\u2013263, 1990.","journal-title":"Theoretical Computer Science"},{"key":"BF01184814_CR4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracleA, PA \u2260 NPA \u2260 coNPA with probability 1.SIAM Journal on Computing, 10:96\u2013113, 1981.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"BF01184814_CR5","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P =? NP question.SIAM Journal on Computing, 4(4):431\u2013442, 1975.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR6","doi-asserted-by":"crossref","unstructured":"M. Blum and R. Impagliazzo. Generic oracles and oracle classes. InProceedings of the 28th IEEE Symposium on Foundations of Computer Science, pages 118\u2013126, October 1987.","DOI":"10.1109\/SFCS.1987.30"},{"key":"BF01184814_CR7","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0304-3975(92)90232-5","volume":"102","author":"D. Bruschi","year":"1992","unstructured":"D. Bruschi. Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets.Theoretical Computer Science, 102:215\u2013252, 1992.","journal-title":"Theoretical Computer Science"},{"key":"BF01184814_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. Balc\u00e1zar","year":"1985","unstructured":"J. Balc\u00e1zar and U. Sch\u00f6ning. Bi-immune sets for complexity classes.Mathematical Systems Theory, 18:1\u201310, 1985.","journal-title":"Mathematical Systems Theory"},{"key":"BF01184814_CR9","first-page":"148","volume-title":"Lecture Notes in Computer Science, Vol. 247","author":"J. Cai","year":"1987","unstructured":"J. Cai. Probability one separation of the Boolean hierarchy. InProceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pages 148\u2013158. Lecture Notes in Computer Science, Vol. 247. Springer-Verlag, Berlin, 1987."},{"issue":"1","key":"BF01184814_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","volume":"38","author":"J. Cai","year":"1989","unstructured":"J. Cai. With probability one, a random oracle separates PSPACE from the polynomial-timehierarchy.Journal of Computer and System Sciences, 38(1):68\u201385, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01184814_CR11","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"R. Chang","year":"1994","unstructured":"R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. H\u00e5stad, and D. Ranjan. The random oracle hypothesis is false.Journal of Computer and System Sciences, 49:24\u201339, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"BF01184814_CR12","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"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\u20131252, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"BF01184814_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"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\u2013111, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR14","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0890-5401(92)90055-K","volume":"96","author":"M. Dowd","year":"1992","unstructured":"M. Dowd. Generic oracles, uniform machines, and codes.Information and Computation, 96:65\u201376, 1992.","journal-title":"Information and Computation"},{"issue":"1","key":"BF01184814_CR15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01368782","volume":"25","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener. Simultaneous strong separations of probabilistic and unambiguous complexity classes.Mathematical Systems Theory, 25(1):23\u201336, 1992.","journal-title":"Mathematical Systems Theory"},{"key":"BF01184814_CR16","first-page":"120","volume-title":"An oracle builder's toolkit","author":"S. Fenner","year":"1993","unstructured":"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\u2013131. IEEE Computer Society Press, New York, 1993."},{"key":"BF01184814_CR17","first-page":"229","volume":"52","author":"L. Fortnow","year":"1994","unstructured":"L. Fortnow. The role of relativization in complexity theory.Bulletin of the EATCS, (52):229\u2013244, 1994.","journal-title":"Bulletin of the EATCS"},{"key":"BF01184814_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0020-0190(93)90216-V","volume":"45","author":"J. Foster","year":"1993","unstructured":"J. Foster. The generic oracle hypothesis is false.Information Processing Letters, 45:59\u201362, 1993.","journal-title":"Information Processing Letters"},{"key":"BF01184814_CR19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow and M. Sipser. Are there interactive protocols for co-NP?Information Processing Letters, 28:249\u2013251, 1988.","journal-title":"Information Processing Letters"},{"key":"BF01184814_CR20","unstructured":"J. Geske. Nondeterminism, bi-immunity and almost-everywhere complexity.IEICE Transactions on Communications\/Electronics\/lnformation and Systems, E76, 1993."},{"issue":"2","key":"BF01184814_CR21","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1137\/0215035","volume":"16","author":"J. Geske","year":"1986","unstructured":"J. Geske and J. Grollmann. Relativizations of unambiguous and random polynomial time classes.SIAM Journal on Computing, 16(2):511\u2013519, 1986.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"BF01184814_CR22","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1137\/0220033","volume":"20","author":"J. Goldsmith","year":"1991","unstructured":"J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young. Near-testable sets.SIAM Journal on Computing, 20(3):506\u2013523, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"BF01184814_CR23","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic Turing machines.SIAM Journal on Computing, 6(4):675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR24","doi-asserted-by":"crossref","unstructured":"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\u201359, 1987.","DOI":"10.1109\/PSCT.1987.10319254"},{"key":"BF01184814_CR25","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0022-0000(93)90008-K","volume":"46","author":"J. Goldsmith","year":"1993","unstructured":"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\u2013362, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01184814_CR26","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L. Goldschlager","year":"1986","unstructured":"L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions.Theoretical Computer Science, 43:43\u201358, 1986.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"BF01184814_CR27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems.SIAM Journal on Computing, 17(2):309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR28","first-page":"266","volume-title":"Lecture Notes in Computer Science, Vol. 452","author":"R. Gavald\u00e0","year":"1990","unstructured":"R. Gavald\u00e0, L. Torenvliet, O. Watanabe, and J. Balc\u00e1zar. Generalized Kolmogorov complexity in relativized separations. InProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, pages 266\u2013276. Lecture Notes in Computer Science, Vol. 452. Springer-Verlag, Berlin, 1990."},{"key":"BF01184814_CR29","unstructured":"J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi. Relativization: A revisionistic retrospective.Bulletin of the EATCS, (47): 144\u2013153, 1992."},{"key":"BF01184814_CR30","first-page":"1","volume-title":"Lecture Notes in Computer Science, Vol. 447","author":"J. Hartmanis","year":"1990","unstructured":"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\u201312. Lecture Notes in Computer Science, Vol. 447. Springer-Verlag, Berlin, 1990."},{"issue":"1","key":"BF01184814_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1995.1119","volume":"121","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and S. Jha. Defying upward and downward separation.Information and Computation, 121(1):1\u201313, 1995.","journal-title":"Information and Computation"},{"issue":"3","key":"BF01184814_CR32","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1142\/S012905419300016X","volume":"4","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust Turing completeness.International Journal of Foundations of Computer Science, 4(3):245\u2013265, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"BF01184814_CR33","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1137\/S0097539792234901","volume":"24","author":"L. Hemachandra","year":"1995","unstructured":"L. Hemachandra and R. Silvestri. Easily checked generalized self-reducibility.SIAM Journal on Computing, 24(4):840\u2013858, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR34","first-page":"306","volume-title":"Average dependence and random oracles","author":"S. Kurtz","year":"1992","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. Average dependence and random oracles. InProceedings of the 7th Structure in Complexity Theory Conference, pages 306\u2013317. IEEE Computer Society Press, New York, 1992."},{"issue":"3","key":"BF01184814_CR35","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1051\/ita\/1990240302291","volume":"24","author":"K. Ko","year":"1990","unstructured":"K. Ko. A note on separating the relativized polynomial time hierarchy by immune sets.RAIRO Theoretical Informatics and Applications, 24(3):229\u2013240, 1990.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"BF01184814_CR36","doi-asserted-by":"crossref","first-page":"764","DOI":"10.2307\/2273469","volume":"48","author":"S. Kurtz","year":"1983","unstructured":"S. Kurtz. Notions of weak genericity.Journal of Symbolic Logic, 48:764\u2013770, 1983.","journal-title":"Journal of Symbolic Logic"},{"key":"BF01184814_CR37","first-page":"40","volume":"57","author":"S. Kurtz","year":"1983","unstructured":"S. Kurtz. On the random oracle hypothesis.Information and Computation, 57:40\u201347, 1983.","journal-title":"Information and Computation"},{"key":"BF01184814_CR38","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01202280","volume":"26","author":"H. M\u00fcller","year":"1993","unstructured":"H. M\u00fcller. A note on balanced immunity.Mathematical Systems Theory, 26:157\u2013167, 1993.","journal-title":"Mathematical Systems Theory"},{"key":"BF01184814_CR39","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0885-064X(91)90038-Y","volume":"7","author":"M. Mundhenk","year":"1991","unstructured":"M. Mundhenk and R. Schuler. Random languages for nonuniform complexity classes.Journal of Complexity, 7:296\u2013310, 1991.","journal-title":"Journal of Complexity"},{"key":"BF01184814_CR40","first-page":"269","volume-title":"Lecture Notes in Computer Science, Vol. 145","author":"C. Papadimitriou","year":"1983","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. InProceedings of the 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Lecture Notes in Computer Science, Vol. 145. Springer-Verlag, Berlin, 1983."},{"key":"BF01184814_CR41","volume-title":"The Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers, Jr.The Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967."},{"key":"BF01184814_CR42","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01303057","volume":"28","author":"K. Regan","year":"1995","unstructured":"K. Regan and J. Royer. On closure properties of bounded 2-sided error complexity classes.Mathematical Systems Theory, 28:229\u2013244, 1995.","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"BF01184814_CR43","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"A. Shamir. IP = PSPACE.Journal of the ACM, 39(4):869\u2013877, 1992.","journal-title":"Journal of the ACM"},{"key":"BF01184814_CR44","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0213023","volume":"13","author":"U. Sch\u00f6ning","year":"1984","unstructured":"U. Sch\u00f6ning and R. Book. Immunity, relativization, and nondeterminism.SIAM Journal on Computing, 13:329\u2013337, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"BF01184814_CR45","unstructured":"L. Torenvliet. Structural concepts in relativized hierarchies, 1986. Ph.D. thesis, Universiteit van Amsterdam."},{"key":"BF01184814_CR46","first-page":"330","volume-title":"Lecture Notes in Computer Science, Vol. 223","author":"L. Torenvliet","year":"1986","unstructured":"L. Torenvliet and P. van Emde Boas. Diagonalization methods in a polynomial setting. InProceedings of the 1st Structure in Complexity Theory Conference, pages 330\u2013346. Lecture Notes in Computer Science, Vol. 223. Springer-Verlag, Berlin, 1986."},{"key":"BF01184814_CR47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90020-5","volume":"80","author":"L. Torenvliet","year":"1989","unstructured":"L. Torenvliet and P. van Emde Boas. Simplicity, immunity, relativizations and nondeterminism.Information and Computation, 80:1\u201317, 1989.","journal-title":"Information and Computation"},{"key":"BF01184814_CR48","first-page":"132","volume-title":"Relationships between NP-sets, co-NP-sets, and P-sets relative to random oracles","author":"N. Vereshchagin","year":"1993","unstructured":"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\u2013138. IEEE Computer Society Press, New York, 1993."},{"key":"BF01184814_CR49","first-page":"335","volume-title":"Randomness and the density of hard problems","author":"R. Wilber","year":"1983","unstructured":"R. Wilber. Randomness and the density of hard problems. InProceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 335\u2013342. IEEE Computer Society Press, New York, 1983."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01184814.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01184814\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01184814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T17:02:25Z","timestamp":1706029345000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01184814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["BF01184814"],"URL":"https:\/\/doi.org\/10.1007\/bf01184814","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}