Revision as of 12:41, 14 August 2008 edit Erxnmedia (talk \| contribs) Autopatrolled, Extended confirmed users 3,864 edits wikilink paper ← Previous edit		Revision as of 12:44, 14 August 2008 edit undo Erxnmedia (talk \| contribs) Autopatrolled, Extended confirmed users 3,864 edits add article Next edit →
Line 7: * [[Leonid Levin]]. Average case complete problems. SIAM J. Comput., 15:285–286, 1986. * [[Philippe Flajolet]] and [[Jeffrey Vitter\|J.S. Vitter]]. Average-case analysis of algorithms and data structures. Technical report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France, August 1987. * [[Yuri Gurevich]] and Saharon Shelah. Expected computation time for [[Hamiltonian path problem]]. SIAM Journal on Computing, volume 16, issue 3, June 1897, pages 486-502. ISSN: 0097-5397. * Shai Ben-David, Benny Chor, [[Oded Goldreich]], and [[Michael Luby]]. On the theory of average case complexity. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 204–216. ACM, 1989. * [[Yuri Gurevich]]. Average case completeness. Journal of Computer and`System Sciences, 42:346–398, 1991. See also [http://research.microsoft.com/~gurevich/Opera/76.pdf 1989 draft].

Average-case complexity: Difference between revisions