{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T15:05:28Z","timestamp":1693407928971},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1992,3,1]],"date-time":"1992-03-01T00:00:00Z","timestamp":699408000000},"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":[[1992,3]]},"DOI":"10.1007\/bf01368782","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T10:33:36Z","timestamp":1112351616000},"page":"23-36","source":"Crossref","is-referenced-by-count":8,"title":["Simultaneous strong separations of probabilistic and unambiguous complexity classes"],"prefix":"10.1007","volume":"25","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[]},{"given":"Lane A.","family":"Hemachandra","sequence":"additional","affiliation":[]},{"given":"James","family":"Tisdall","sequence":"additional","affiliation":[]},{"given":"B\ufffdlent","family":"Yener","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"CR1","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?442, 1975.","journal-title":"SIAM Journal on Computing"},{"key":"CR2","volume-title":"Structural Complexity, I. EATCS Monographs in Theoretical Computer Science","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3.Structural Complexity, I. EATCS Monographs in Theoretical Computer Science. Springer-Verlag, New York, 1988."},{"issue":"2","key":"CR3","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1051\/ita\/1988220202271","volume":"22","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar and D. Russo. Immunity and simplicity in relativizations of probabilistic complexity classes.Theoretical Informatics and Applications (RAIRO),22(2):227?244, 1988.","journal-title":"Theoretical Informatics and Applications (RAIRO)"},{"key":"CR4","first-page":"216","volume-title":"On the relativized power of additional accepting paths","author":"R. Beigel","year":"1989","unstructured":"R. Beigel. On the relativized power of additional accepting paths. InProceedings of the 4th Structure in Complexity Theory Conference, pages 216?224. IEEE Computer Society Press, New York, June 1989."},{"issue":"2","key":"CR5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(91)90140-D","volume":"37","author":"R. Beigel","year":"1991","unstructured":"R. Beigel, L. Hemachandra, and G. Wechsung. Probabilistic polynomial time is closed under parity reductions.Information Processing Letters,37(2):91?94, 1991.","journal-title":"Information Processing Letters"},{"key":"CR6","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 oracle A, P A ? NP A with probability 1.SIAM Journal on Computing,10:96?113, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem.Information and Control,55:80?88, 1982.","journal-title":"Information and Control"},{"issue":"3","key":"CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1142\/S0129054190000151","volume":"1","author":"D. Bruschi","year":"1990","unstructured":"D. Bruschi, D. Joseph, and P. Young. Strong separations for the Boolean hierarchy over RP.International Journal of Foundations of Computer Science,1(3):201?218, 1990.","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"6","key":"CR9","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?1252, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"CR10","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?111, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02090768","volume":"23","author":"J. Cai","year":"1990","unstructured":"J. Cai and L. Hemachandra. On the power of parity polynomial time.Mathematical Systems Theory,23:95?106, 1990.","journal-title":"Mathematical Systems Theory"},{"key":"CR12","first-page":"65","volume-title":"Probabilistic and unambiguous computation are incomparable","author":"D. Eppstein","year":"1989","unstructured":"D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener. Probabilistic and unambiguous computation are incomparable. InComputing and Information: Proceedings of the 1989 International Conference on Computing and Information pages 65?70. North-Holland, Amsterdam, May 1989."},{"issue":"4","key":"CR13","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1137\/0216042","volume":"16","author":"W. Gasarch","year":"1987","unstructured":"W. Gasarch. Oracles for deterministic versus alternating classes.SIAM Journal on Computing,16(4):613?627, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0019-9958(83)80058-8","volume":"58","author":"W. Gasarch","year":"1983","unstructured":"W. Gasarch and S. Homer. Relativizations comparing NP and exponential time.Information and Control,58:88?100, 1983.","journal-title":"Information and Control"},{"issue":"2","key":"CR15","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?519, 1986.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"CR16","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?695, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"CR17","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:309?335, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"CR18","first-page":"395","volume":"6","author":"T. Gundermann","year":"1987","unstructured":"T. Gundermann and G. Wechsung. Counting classes with finite acceptance types.Computers and Artificial Intelligence,6(5):395?409, 1987.","journal-title":"Computers and Artificial Intelligence"},{"key":"CR19","first-page":"40","volume":"27","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis. Solvable problems with conflicting relativizations.Bulletin of the European Association for Theoretical Computer Science,27:40?49, 1985.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"CR20","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?12. Lecture Notes in Computer Science, Vol. 447. Springer-Verlag, Berlin, July 1990."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartmanis","year":"1988","unstructured":"J. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP.Theoretical Computer Science,58:129?142, 1988.","journal-title":"Theoretical Computer Science"},{"key":"CR22","first-page":"110","volume-title":"The strong exponential hierarchy collapses","author":"L. Hemachandra","year":"1987","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. InProceedings of the 19th ACM Symposium on Theory of Computing, pages 110?122. ACM Press, New York, May 1987."},{"key":"CR23","first-page":"59","volume-title":"Lecture Notes in Computer Science, Vol. 324","author":"L. Hemachandra","year":"1988","unstructured":"L. Hemachandra. Structure of complexity classes: Separations, collapses, and completeness. InProceedings of the 13th Symposium on Mathematical Foundations of Computer Science, pages 59?72. Lecture Notes in Computer Science, Vol. 324. Springer-Verlag, Berlin, August\/September 1988."},{"key":"CR24","volume-title":"On Relativization and the Existence of Turing Complete Sets","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra and S. Jain. On Relativization and the Existence of Turing Complete Sets. Technical Report TR-297, Department of Computer Science, University of Rochester, Rochester, NY 14627, June 1989."},{"key":"CR25","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979."},{"key":"CR26","first-page":"157","volume-title":"The isomorphism conjecture fails relative to a random oracle","author":"S. Kurtz","year":"1989","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The isomorphism conjecture fails relative to a random oracle. InProceedings of the 21st ACM Symposium on Theory of Computing, pages 157?166. ACM Press, New York, May 1989."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"14","author":"C. Lautemann","year":"1983","unstructured":"C. Lautemann. BPP and the polynomial hierarchy.Information Processing Letters,14:215?217, 1983.","journal-title":"Information Processing Letters"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1002\/malq.19860321702","volume":"32","author":"G. Lischke","year":"1986","unstructured":"G. Lischke. Oracle constructions to prove all possible relationships between relativizations of P, NP, NEL, EP, and NEP.Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik,32:257?270, 1986.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"issue":"1","key":"CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"C. Rackoff. Relativized questions involving probabilistic algorithms.Journal of the ACM,29(1):261?268, 1982.","journal-title":"Journal of the ACM"},{"key":"CR30","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":"CR31","unstructured":"S. Rudich. Limits on the Provable Consequences of One-way Functions. Ph.D. thesis, University of California at Berkeley, November 1988."},{"key":"CR32","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?337, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"CR33","first-page":"11","volume-title":"IP = PSPACE","author":"A. Shamir","year":"1990","unstructured":"A. Shamir. IP = PSPACE. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 11?15. IEEE Computer Society Press, New York, October 1990."},{"key":"CR34","first-page":"330","volume-title":"A complexity theoretic approach to randomness","author":"M. Sipser","year":"1983","unstructured":"M. Sipser. A complexity theoretic approach to randomness. InProceedings of the 15th ACM Symposium on Theory of Computing, pages 330?335. ACM Press, New York, 1983."},{"key":"CR35","unstructured":"S. Toda. On probabilistic computations with a restricted access to NP oracles. Manuscript, February 1989."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluating.Information Processing Letters,5:20?23, 1976.","journal-title":"Information Processing Letters"},{"key":"CR37","first-page":"383","volume-title":"Probabilistic quantifiers, adversaries, and complexity classes: An overview","author":"S. Zachos","year":"1986","unstructured":"S. Zachos. Probabilistic quantifiers, adversaries, and complexity classes: An overview. InProceedings of the 1st Structure in Complexity Theory Conference, pages 383?400. IEEE Computer Society Press, New York, June 1986."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01368782.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01368782\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01368782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T11:06:23Z","timestamp":1556795183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01368782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["BF01368782"],"URL":"https:\/\/doi.org\/10.1007\/bf01368782","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}