{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T13:00:24Z","timestamp":1648904424460},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory of Computing Systems"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/bf02679447","type":"journal-article","created":{"date-parts":[[2007,7,28]],"date-time":"2007-07-28T00:57:16Z","timestamp":1185584236000},"page":"165-180","source":"Crossref","is-referenced-by-count":3,"title":["Helping by unambiguous computation and probabilistic computation"],"prefix":"10.1007","volume":"30","author":[{"given":"P.","family":"Cintioli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,30]]},"reference":[{"key":"BF02679447_CR1","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading Group Theory for Randomness,Proc. 17th ACM Symposium on Theory of Computing, 1985, pp. 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"BF02679447_CR2","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0022-0000(90)90025-G","volume":"41","author":"J. L. Balc\u00e1zar","year":"1990","unstructured":"J. L. Balc\u00e1zar, Self-Reducibility,Journal of Computer and System Sciences 41(1990), 367\u2013388.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02679447_CR3","volume-title":"Introduction to the Theory of Complexity","author":"D. P. Bovet","year":"1994","unstructured":"D. P. Bovet and P. Crescenzi,Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1994."},{"key":"BF02679447_CR4","doi-asserted-by":"crossref","unstructured":"D. P. Bovet, P. Crescenzi, and R. Silvestri, Complexity Classes and Sparse Oracles,Proc. 6th Structure in Complexity Theory Conference, 1991, pp. 102\u2013108. AlsoJournal of Computer and System Sciences 50 (1995), 382\u2013390.","DOI":"10.1006\/jcss.1995.1030"},{"key":"BF02679447_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. P. Bovet","year":"1992","unstructured":"D. P. Bovet, P. Crescenzi, and R. Silvestri, A Uniform Approach to Define Complexity Classes,Theoretical Computer Science 104 (1992), 263\u2013283.","journal-title":"Theoretical Computer Science"},{"key":"BF02679447_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I, vol. 1","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3,Structural Complexity I, vol. 1, Springer-Verlag, Berlin, 1988."},{"key":"BF02679447_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural Complexity II, vol. 2","author":"J. L. Balc\u00e1zar","year":"1990","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3,Structural Complexity II, vol. 2, Springer-Verlag, Berlin, 1990."},{"key":"BF02679447_CR8","doi-asserted-by":"crossref","unstructured":"M. Blum and R. Impagliazzo, Generic Oracles and Oracle Classes,Proc. 28th IEEE Symposium on Foundations of Computer Science, 1987, pp. 118\u2013126.","DOI":"10.1109\/SFCS.1987.30"},{"key":"BF02679447_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/3-540-57785-8_169","volume-title":"Proc. 11th Symposium on Theoretical Aspects of Computer Science","author":"B. Borchert","year":"1994","unstructured":"B. Borchert, On the Acceptance Power of Regular Languages,Proc. 11th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 775, Springer-Verlag, Berlin, 1994, pp. 533\u2013541."},{"key":"BF02679447_CR10","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 (1990), 95\u2013106.","journal-title":"Mathematical Systems Theory"},{"key":"BF02679447_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-55808-X_14","volume-title":"Proc. 17th Symposium on Mathematical Foundations of Computer Science","author":"J. Cai","year":"1992","unstructured":"J. Cai, L. Hemachandra, and J. Visko\u010d, Promises Problems and Access to Unambiguous Computation,Proc. 17th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 629, Springer-Verlag, Berlin, 1992, pp. 162\u2013171."},{"key":"BF02679447_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/3-540-56939-1_72","volume-title":"Proc. 20th International Colloquium on Automata, Languages, and Programming","author":"L. Hemachandra","year":"1993","unstructured":"L. Hemachandra, Fault-Tolerance and Complexity,Proc. 20th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 700, Springer-Verlag, Berlin, 1993, pp. 189\u2013202."},{"key":"BF02679447_CR13","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, Complexity Classes Defined viak-Valued Functions,Proc. 9th Structure in Complexity Theory Conference, 1994, pp. 224\u2013234.","DOI":"10.1109\/SCT.1994.315801"},{"key":"BF02679447_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/3-540-57785-8_170","volume-title":"Proc. 11th Symposium on Theoretical Aspects of Computer Science","author":"U. Hertrampf","year":"1994","unstructured":"U. Hertrampf, Complexity Classes with Finite Acceptance Types,Proc. 11th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 775, Springer-Verlag, Berlin, 1994, pp. 543\u2013553."},{"key":"BF02679447_CR15","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(90)90138-8","volume":"74","author":"J. Hartmanis","year":"1990","unstructured":"J. Hartmanis and L. A. Hemachandra, Robust Machines Accept Easy Sets,Theoretical Computer Science 74 (1990), 217\u2013225.","journal-title":"Theoretical Computer Science"},{"key":"BF02679447_CR16","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1142\/S0129054191000157","volume":"2","author":"L. Hemachandra","year":"1991","unstructured":"L. Hemachandra and S. Jain, On the Limitations of Locally Robust Positive Reductions,International Journal of Foundations of Computer Science 2 (1991), 237\u2013255.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"BF02679447_CR17","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner, On the Power of Polynomial Time Bit-Reductions,Proc. 8th Structure in Complexity Theory Conference, 1993, pp. 200\u2013207.","DOI":"10.1109\/SCT.1993.336526"},{"key":"BF02679447_CR18","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Naor, Decision Trees and Downward Closures,Proc. 3rd Structure in Complexity Theory Conference, 1988, pp. 29\u201338.","DOI":"10.1109\/SCT.1988.5260"},{"key":"BF02679447_CR19","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0304-3975(87)90078-8","volume":"52","author":"K. Ko","year":"1987","unstructured":"K. Ko, On Helping by Robust Oracle Machines,Theoretical Computer Science 52 (1987), 15\u201336.","journal-title":"Theoretical Computer Science"},{"key":"BF02679447_CR20","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N. Nisan","year":"1991","unstructured":"N. Nisan, CREW PRAMs and Decision Trees,SIAM Journal on Computing 20 (1991), 999\u20131007.","journal-title":"SIAM Journal on Computing"},{"key":"BF02679447_CR21","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 (1982), 261\u2013268.","journal-title":"Journal of the ACM"},{"key":"BF02679447_CR22","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0304-3975(85)90158-6","volume":"40","author":"U. Sch\u00f6ning","year":"1985","unstructured":"U. Sch\u00f6ning, Robust Algorithms: a Different Approach to Oracles,Theoretical Computer Science 40 (1985), 57\u201366.","journal-title":"Theoretical Computer Science"},{"key":"BF02679447_CR23","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G. Tardos","year":"1989","unstructured":"G. Tardos, Query Complexity, or Why is it Difficult to Separate NP A \u2229 co-NP A from P A by Random Oracles,Combinatorica 9 (1989), 385\u2013392.","journal-title":"Combinatorica"},{"key":"BF02679447_CR24","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1070\/IM1994v042n02ABEH001537","volume":"42","author":"N. K. Vereshchagin","year":"1994","unstructured":"N. K. Vereshchagin, Relativizable and Nonrelativizable Theorems in the Polynomial Theory of Algorithms,Russian Academy of Sciences. Izvestiya. Mathematics (AMS) 42 (1994), 261\u2013298.","journal-title":"Russian Academy of Sciences. Izvestiya. Mathematics (AMS)"},{"key":"BF02679447_CR25","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF01374524","volume":"25","author":"T. Yamakami","year":"1992","unstructured":"T. Yamakami, Structural Properties for Feasibly Computable Classes of Type Two,Mathematical Systems Theory 25 (1992), 177\u2013201.","journal-title":"Mathematical Systems Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679447.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02679447\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679447","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T07:40:47Z","timestamp":1558338047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02679447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02679447"],"URL":"https:\/\/doi.org\/10.1007\/bf02679447","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}