{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T19:21:27Z","timestamp":1649186487020},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,6,1]],"date-time":"1993-06-01T00:00:00Z","timestamp":738892800000},"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":[[1993,6]]},"DOI":"10.1007\/bf01202283","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T08:05:42Z","timestamp":1111737942000},"page":"203-214","source":"Crossref","is-referenced-by-count":14,"title":["Structural analysis of the complexity of inverse functions"],"prefix":"10.1007","volume":"26","author":[{"given":"Osamu","family":"Watanabe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seinosuke","family":"Toda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3,Structural Complexity I, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, New York (1988)."},{"key":"CR2","unstructured":"R. Beigel. NP-hard sets are P-superterse unless R = NP. Technical Report 88-04, Department of Computer Science, The Johns Hopkins University."},{"key":"CR3","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, P A ? NP A ? co-NP A with probability 1,SIAM J. Comput. 10 (1981), 96?113.","journal-title":"SIAM J. Comput."},{"key":"CR4","first-page":"224","volume-title":"On truth-table reducibility to SAT and the difference hierarchy over NP","author":"S. Buss","year":"1988","unstructured":"S. Buss and L. Hay, On truth-table reducibility to SAT and the difference hierarchy over NP, inProc. 3rd Structure in Complexity Theory Conference, IEEE, New York (1988), pp. 224?233."},{"key":"CR5","first-page":"495","volume-title":"Complexity measures for public-key cryptosystems","author":"J. Grollmann","year":"1984","unstructured":"J. Grollmann and A. Selman, Complexity measures for public-key cryptosystems, inProc. 25th IEEE Symposium on Foundations of Computer Science, IEEE, New York (1984), pp. 495?503; the final version appeared inSIAM J. Comput. 17 (1988), 309?335."},{"key":"CR6","first-page":"278","volume-title":"The polynomial hierarchy collapses if the Boolean hierarchy collapses","author":"J. Kadin","year":"1988","unstructured":"J. Kadin, The polynomial hierarchy collapses if the Boolean hierarchy collapses, inProc. 3rd Structure in Complexity Theory Conference, IEEE, New York (1988), pp. 278?292."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel, The complexity of optimization problems,J. Comput. System Sci. 36 (1988), 490?509.","journal-title":"J. Comput. System Sci."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman, A comparison of polynomial time reducibilities,Theoret. Comput. Sci. 1 (1975), 103?123.","journal-title":"Theoret. Comput. Sci."},{"key":"CR9","first-page":"2","volume-title":"Probabilistic complexity classes and lowness","author":"U. Sch\u00f6ning","year":"1987","unstructured":"U. Sch\u00f6ning, Probabilistic complexity classes and lowness, inProc. 2nd Structure in Complexity Theory Conference, IEEE, New York (1987), pp. 2?8."},{"key":"CR10","first-page":"88","volume-title":"One-way functions in complexity theory","author":"A. Selman","year":"1990","unstructured":"A. Selman, One-way functions in complexity theory, inProc. Mathematical Foundations of Computer Science 1990, Springer-Verlag, New York (1990), pp. 88?104."},{"key":"CR11","unstructured":"A. Selman, A taxonomy of complexity classes of functions, submitted for publication."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1137\/0218031","volume":"18","author":"S. Tang","year":"1989","unstructured":"S. Tang and O. Watanabe, On tally relativizations ofBP-complexity classes,SIAM J. Comput. 18 (1989), 449?462.","journal-title":"SIAM J. Comput."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF02090391","volume":"24","author":"S. Toda","year":"1991","unstructured":"S. Toda, On polynomial time truth-table reducibility of intractable sets to p-selective sets,Math. Systems Theory 24 (1991), 69?82.","journal-title":"Math. Systems Theory"},{"key":"CR14","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, Relative complexity of checking and evaluating,Inform. Process. Lett. 5 (1976), 20?23.","journal-title":"Inform. Process. Lett."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani, NP is as easy as detecting unique solutions,Theoret. Comput. Sci. 47 (1986), 85?93.","journal-title":"Theoret. Comput. Sci."},{"key":"CR16","first-page":"260","volume-title":"Bounded query computations","author":"K. Wagner","year":"1988","unstructured":"K. Wagner, Bounded query computations, inProc. 3rd Structure in Complexity Theory Conference, IEEE, New York (1988), pp. 260?277."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe, A comparison of polynomial time completeness notions,Theoret. Comput. Sci. 54 (1987), 249?265.","journal-title":"Theoret. Comput. Sci."},{"key":"CR18","first-page":"31","volume-title":"Lecture Notes in Computer Science, Vol. 450","author":"O. Watanabe","year":"1990","unstructured":"O. Watanabe and S. Toda, Structural Analyses on the complexity of inverting functions, inProc. International Symposium SIGAL '90, Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York (1990), pp. 31?38."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0022-0000(88)90037-2","volume":"36","author":"S. Zachos","year":"1988","unstructured":"S. Zachos, Probabilistic quantifiers and games,J. Comput. System Sci. 36 (1988), 433?451.","journal-title":"J. Comput. System Sci."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202283.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01202283\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T17:01:49Z","timestamp":1556730109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01202283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["BF01202283"],"URL":"https:\/\/doi.org\/10.1007\/bf01202283","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}