{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:18:27Z","timestamp":1725455907279},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626169"},{"type":"electronic","value":"9783540683421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023474","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:06:33Z","timestamp":1132383993000},"page":"375-386","source":"Crossref","is-referenced-by-count":0,"title":["The complexity of generating test instances"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Karg","sequence":"first","affiliation":[]},{"given":"Johannes","family":"K\u00f6bler","sequence":"additional","affiliation":[]},{"given":"Rainer","family":"Schuler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0022-0000(89)90018-4","volume":"39","author":"M. Abadi","year":"1989","unstructured":"M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. Journal of Computer and System Sciences, 39:21\u201350, 1989.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar. Self-reducibility structures and solutions of NP problems. In Revista Matematica, volume 2, pages 175\u2013184. Universidad Complutense de Madrid, 1989.","key":"31_CR2","DOI":"10.5209\/rev_REMA.1989.v2.n2.18114"},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44(2):193\u2013219, 1992.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"A. Borodin and A. Demers. Some comments on functional self-reducibility and the NP hierarchy. Technical Report 76-284, Dept. of Computer Science, Cornell University, 1976.","key":"31_CR4"},{"doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity II. Springer-Verlag, 1990.","key":"31_CR5","DOI":"10.1007\/978-3-642-75357-2"},{"doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, second edition, 1995.","key":"31_CR6","DOI":"10.1007\/978-3-642-79235-9"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1137\/0222059","volume":"22","author":"A. Blass","year":"1993","unstructured":"A. Blass and Y. Gurevich. Randomized reductions of search problems. SIAM Journal of Computing, 22:949\u2013975, 1993.","journal-title":"SIAM Journal of Computing"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"R.B. Boppana, J. Hastad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:27\u201332, 1987.","journal-title":"Information Processing Letters"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran. Arthur-Merlin games: A randomized proof system, and a short hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R.V. Book","year":"1974","unstructured":"R.V. Book. Tally languages and complexity classes. Information and Control, 26:281\u2013287, 1974.","journal-title":"Information and Control"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143\u2013154, 1979.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"31_CR12","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich. Average case complexity. Journal of Computer and System Sciences, 42(3):346\u2013398, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0304-3975(82)80003-0","volume":"20","author":"K.-I. Ko","year":"1982","unstructured":"K.-I. Ko and H. Friedman. Computational complexity of real functions. Theoretical Computer Science, 20:323\u2013352, 1982.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and J. Tor\u00e1n. The Graph Isomorphism Problem: It's Structural Complexity. Birkh\u00e4user, 1993.","key":"31_CR14","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"L.A. Levin. Average case complete problems. SIAM Journal of Computing, 15:285\u2013286, 1986.","journal-title":"SIAM Journal of Computing"},{"unstructured":"A. Lozano and J. Tor\u00e1n. On the nonuniform complexity of the graph isomorphism problem. In K. Ambos-Spies, S. Homer, and U. Sch\u00f6ning, editors, Complexity Theory\u2014Current Research, pages 245\u2013271. Cambridge University Press, 1993.","key":"31_CR16"},{"unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.","key":"31_CR17"},{"unstructured":"L.A. Sanchis. Language instance generation and test case construction for NP-hard problems. Technical Report 296, University of Rochester, Dept. of Computer Science, 1989.","key":"31_CR18"},{"unstructured":"C.P. Schnorr. Optimal algorithms for self-transformable problems. In Proc. 3th International Colloquium on Automata, Languages and Programming, 1976.","key":"31_CR19"},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"U. Sch\u00f6ning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37:312\u2013323, 1988.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity theoretic approach to randomness. In Proc. 15th ACM Symposium on the Theory of Computing, pages 330\u2013335, 1983.","key":"31_CR21","DOI":"10.1145\/800061.808762"},{"doi-asserted-by":"crossref","unstructured":"W. Tompa and H. Woll. Random self-reducibility and zero-knowledge interactive proofs of possession of information. In Proc. 28st Symposium on Foundations of Computer Science, pages 472\u2013482, 1987.","key":"31_CR22","DOI":"10.1109\/SFCS.1987.49"},{"key":"31_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85\u201393, 1986.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"J. Wang. Average-case computational complexity theory. In A. Selman and L. Hemaspaandra, editors, Complexity Theory Retrospective II. Springer-Verlag. (to appear).","key":"31_CR24","DOI":"10.1007\/978-1-4612-1872-2_12"},{"doi-asserted-by":"crossref","unstructured":"O. Watanabe. Test instance generation for promised NP search problems. In Proc. 9th Conference on Structure in Complexity Theory, pages 205\u2013216, 1994.","key":"31_CR25","DOI":"10.1109\/SCT.1994.315803"},{"key":"31_CR26","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/jcss.1995.1014","volume":"50","author":"J. Wang","year":"1995","unstructured":"J. Wang and J. Belanger. On the NP-isomorphism problem with respect to random instances. Journal of Computer and System Sciences, 50:151\u2013164, 1995.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T01:31:49Z","timestamp":1586568709000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0023474","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}