{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:07Z","timestamp":1725664507450},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_7","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:04:59Z","timestamp":1330272299000},"page":"75-86","source":"Crossref","is-referenced-by-count":3,"title":["The complexity of generating and checking proofs of membership"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I & II. EATCS Monographs on Theoretical Computer Science, Springer-Verlag (1988, 1991)","DOI":"10.1007\/978-3-642-97062-7"},{"key":"7_CR2","unstructured":"Beigel, R.: NP-hard sets are P-superterse unless R=NP. Technical Report 88-04, Dept. of Computer Science, The John Hopkins University (1988)."},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"Blass, A., Gurevich, Y.: On the unique satisfiability problem. Information and Control 55 (1982) 80\u201388","journal-title":"Information and Control"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Kadin, J., Thierauf, T.: On functions computable with nonadaptive queries to NP. Proc. 9th Structure in Complexity Theory Conference (1994) 43\u201352","DOI":"10.1109\/SCT.1994.315819"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1028","volume":"50","author":"R. Chang","year":"1995","unstructured":"Chang, R., Kadin, J., Rohatgi, P.: On Unique Satisfiability and the threshhold behavior of randomized reductions. Journal of Computer and System Science 50 (1995) 359\u2013373.","journal-title":"Journal of Computer and System Science"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: The Complexity of Theorem-Proving Procedures. Proc. 3rd ACM Symposium on Theory of Computing (1971) 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1142\/S0129054191000133","volume":"2","author":"Z. Chen","year":"1991","unstructured":"Chen, Z., Toda, S.: On the Complexity of Computing Optimal Solutions. International Journal of Foundations of Computer Science 2 (1991) 207\u2013220","journal-title":"International Journal of Foundations of Computer Science"},{"key":"7_CR8","unstructured":"Chen, Z., Toda, S.: An Exact Characterization of FP \u2225 NP . Manuscript (1993)"},{"key":"7_CR9","first-page":"398","volume":"665","author":"S. Fenner","year":"1993","unstructured":"Fenner, S., Homer, S., Ogiwara, M., Selman, A.: On Using Oracles That Compute values. 10-th Annual Symposium on Theoretical Aspects of Computer Science, Springer Verlag LNCS 665 (1993) 398\u2013407","journal-title":"Springer Verlag LNCS"},{"key":"7_CR10","unstructured":"Fortnow, L.: Personal Communication. In the plane to Madras (India) (December 7, 1994)"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"Hemachandra, L.: The strong exponential hierarchy collapses. Journal of Computer and System Sciences 39(3) (1989) 299\u2013322","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR12","first-page":"56","volume":"834","author":"L. Hemaspaandra","year":"1994","unstructured":"Hemaspaandra, L., Naik, A., Ogihara, M., Selman, A.: Finding Satisfying Assignments Uniquely Isn't so Easy: Unique Solutions Collapes the Polynomial Hierarchy. Algorithms and Compuatation, International Symposium ISAAC '94, Springer Verlag LNCS 834 (1994) 56\u201364","journal-title":"Springer Verlag LNCS"},{"key":"7_CR13","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979)"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Tardos, G.: Decision Versus Search Problems in Super-Polynomial Time. Proc. 30th IEEE Annual Symposium on Foundations of Computer Science (1989) 222\u2013227","DOI":"10.1109\/SFCS.1989.63482"},{"key":"7_CR15","unstructured":"Kadin, J.: Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy. PhD thesis, Cornell University (1988)"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Krentel, M.: The Complexity of Optimization Problems. Proc. 18th ACM Symposium on Theory of Computing (1986) 69\u201376","DOI":"10.1145\/12130.12138"},{"key":"7_CR17","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin, L.: Universal Sorting Problems. Problems of Information Transmission 9 (1973) 265\u2013266","journal-title":"Problems of Information Transmission"},{"key":"7_CR18","unstructured":"Ogihara, M.: Functions Computable with Limited Access to NP. Technical Report 538, University of Rochester (1995)"},{"issue":"2","key":"7_CR19","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.: On the complexity of unique solutions. Journal of the ACM 31(2) (1984) 392\u2013400","journal-title":"Journal of the ACM"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C., Yannakakis, M.: On the complexity of facets. Journal of Computer and System Sciences 28 (1984) 244\u2013259","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR21","first-page":"269","volume":"145","author":"C. Papadimitriou","year":"1983","unstructured":"Papadimitriou, C., Zachos, D.: Two remarks on the power of counting. 6th GI Conference on TCS, Springer Verlag LNCS 145 (1983) 269\u2013276","journal-title":"Springer Verlag LNCS"},{"key":"7_CR22","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A. Selman","year":"1994","unstructured":"Selman, A.: A taxonomy of complexity classes of functions. Journal of Computer and System Science 48 (1994) 357\u2013381.","journal-title":"Journal of Computer and System Science"},{"key":"7_CR23","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF02090391","volume":"24","author":"S. Toda","year":"1991","unstructured":"Toda, S.: On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory 24 (1991) 69\u201382.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"7_CR24","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. Theoretical Computer Science 47(1) (1986) 85\u201393","journal-title":"Theoretical Computer Science"},{"key":"7_CR25","first-page":"53","volume":"226","author":"K. Wagner","year":"1986","unstructured":"Wagner, K.: More complicated questions about maxima and minima and some closure properties of NP. Proc. 13th International Colloquium on Automata, Languages, and Programming (ICALP), Springer Verlag LNCS 226 (1986) 53\u201380","journal-title":"Springer Verlag LNCS"},{"issue":"5","key":"7_CR26","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"Wagner, K.: Bounded query classes. SIAM Journal on Computing 19(5) (1990) 833\u2013846","journal-title":"SIAM Journal on Computing"},{"key":"7_CR27","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01202283","volume":"26","author":"O. Watanabe","year":"1993","unstructured":"Watanabe, O., Toda, S.: Structural Analysis on the Complexity of Inverse Functions. Mathematical Systems Theory 26 (1993) 203\u2013214","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:02:40Z","timestamp":1605628960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}