{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:40Z","timestamp":1725663400845},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_168","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:50Z","timestamp":1330209530000},"page":"615-628","source":"Crossref","is-referenced-by-count":9,"title":["Average case complexity"],"prefix":"10.1007","author":[{"given":"Yuri","family":"Gurevich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, \u201cOn the Theory of Average Case Complexity\u201d, Symposium on Theory of Computing, ACM, 1989, 204\u2013216.","DOI":"10.1145\/73007.73027"},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"Andreas Blass and Yuri Gurevich, \u201cOn the Reduction Theory for Average-Case Complexity\u201d, in Proc. of CSL'90, 4th Workshop on Computer Science Logic (Eds. E. B\u00f6rger, H. Kleine B\u00fcning and M. Richter), Springer LNCS, 1991.","DOI":"10.1007\/3-540-54487-9_50"},{"key":"48_CR3","unstructured":"Michael R. Garey and David S. Johnson, \u201cComputers and Intractability: A Guide to the Theory of NP-Completeness\u201d, Freeman, New York, 1979."},{"key":"48_CR4","unstructured":"Oded Goldreich, \u201cTowards a Theory of Average Case Complexity: A survey\u201d, TR-531, Computer Science Dept., Technion, Haifa, Israel, March 1988."},{"key":"48_CR5","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/3-540-52846-6_104","volume":"447","author":"P. Grape","year":"1990","unstructured":"Per Grape, \u201cComplete Problems with L-Samplable Distributions\u201d, 2nd Scandinavian Workshop on Algorithm Theory, Springer Lecture Notes in Computer Science 447, 1990, 360\u2013367.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"48_CR6","unstructured":"Yuri Gurevich, \u201cAverage Case Complexity\u201d, J. Computer and System Sciences (a special issue on FOCS'87), to appear."},{"key":"48_CR7","unstructured":"Y. Gurevich, \u201cThe Challenger-Solver game: Variations on the Theme of P=?NP\u201d, Bulletin of European Assoc. for Theor. Computer Science, October 1989, 112\u2013121."},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Yuri Gurevich, \u201cMatrix Decomposition Problem is Complete for the Average Case\u201d, Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1990, 802\u2013811. A full version of this paper, coauthored by Blass and Gurevich, is being prepared for publication.","DOI":"10.1109\/FSCS.1990.89603"},{"issue":"3","key":"48_CR9","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Yuri Gurevich and Saharon Shelah, \u201cExpected computation time for Hamiltonian Path Problem\u201d, SIAM J. on Computing 16:3 (1987), 486\u2013502.","journal-title":"SIAM J. on Computing"},{"key":"48_CR10","doi-asserted-by":"crossref","unstructured":"Johan Hastad, \u201cPseudo-Random Generators under Uniform Functions\u201d, Symposium on Theory of Computing, ACM, 1990, 395\u2013404.","DOI":"10.1145\/100216.100270"},{"key":"48_CR11","unstructured":"Russel Impagliazzo and Stephen Rudich, private communication."},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"Russel Impagliazzo and Leonid A. Levin, \u201cNo Better Ways to Generate Hard NP Instances than Picking Uniformly at Random\u201d, Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1990, 812\u2013821.","DOI":"10.1109\/FSCS.1990.89604"},{"key":"48_CR13","doi-asserted-by":"crossref","unstructured":"Russel Impagliazzo, Leonid A. Levin and Michael Luby, \u201cPseudo-Random Generation from One-Way Functions\u201d, 21st Symposium on Theory of Computing, ACM, New York, 1989, 12\u201324.","DOI":"10.1145\/73007.73009"},{"key":"48_CR14","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0196-6774(84)90032-4","volume":"5","author":"D. S. Johnson","year":"1984","unstructured":"David S. Johnson, \u201cThe NP-Completeness Column\u201d, Journal of Algorithms 5 (1984), 284\u2013299.","journal-title":"Journal of Algorithms"},{"key":"48_CR15","unstructured":"P.M.W. Knijnenburg, \u201cOn Randomizing Decision Problems: A Survey of the Theory of Randomized NP\u201d, Tech. Report RUU-CS-88-15, Rijksuniversitait Utrecht, The Netherlands, March 1988."},{"key":"48_CR16","doi-asserted-by":"crossref","unstructured":"Leonid A. Levin, \u201cAverage Case Complete Problems\u201d, STOC 1984, the final version in SIAM Journal of Computing, 1986.","DOI":"10.1137\/0215020"},{"key":"48_CR17","doi-asserted-by":"crossref","unstructured":"Leonid A. Levin, \u201cOne-Way Functions and Pseudo-Random Generators\u201d, Symposium on Theory of Computing, ACM, 1985, 363\u2013375.","DOI":"10.1145\/22145.22185"},{"key":"48_CR18","unstructured":"Ming Li and Paul M. B. Vitani, \u201cAverage Case Complexity under the Universal Distribution Equals Worst Case Complexity\u201d, Manuscript, 1989."},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Robert E. Schapire, \u201cThe Emerging Theory of Average Case Complexity\u201d, Tech. Report MIT\/LCS\/TM-431, June 1990.","DOI":"10.21236\/ADA222821"},{"issue":"4","key":"48_CR20","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B. A. Trakhtenbrot","year":"1984","unstructured":"Boris A. Trakhtenbrot, \u201cA Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms\u201d, Annals of the History of Computing, 6:4 (1984), 384\u2013400.","journal-title":"Annals of the History of Computing"},{"key":"48_CR21","doi-asserted-by":"crossref","unstructured":"Ramarathnam Venkatesan and Leonid Levin, \u201cRandom Instances of a Graph Coloring Problem are Hard\u201d, Symposium on Theory of Computing, ACM, 1988, 217\u2013222.","DOI":"10.1145\/62212.62231"},{"key":"48_CR22","unstructured":"Ramarathnam Venkatesan, private correspondence."},{"key":"48_CR23","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1080\/00029890.1985.11971591","volume":"92","author":"H. S. Wilf","year":"1985","unstructured":"Herbert S. Wilf, Some Examples of Combinatorial Averaging, American Math. Monthly 92 (1985), 250\u2013261.","journal-title":"Monthly"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_168.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T03:42:12Z","timestamp":1640922132000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_168","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}