Revision as of 20:32, 19 June 2025 edit OAbot (talk \| contribs) Bots 643,717 edits m Open access bot: url-access updated in citation with #oabot. ← Previous edit		Revision as of 01:29, 18 July 2025 edit undo BD2412 (talk \| contribs) Autopatrolled, Administrators 2,527,666 edits m clean up spacing around commas and other punctuation, replaced: ; → ; (2) Tag: AWB Next edit →
Line 34: </math> for some constants {{mvar\|C}} and {{mvar\|ε}}, where {{math\|''n'' {{=}} {{abs\|''x''}}}}.<ref name="ab09">{{cite book \|last1=Arora \|first1=Sanjeev \|title=Computational Complexity: A Modern Approach \|last2=Barak \|first2=Boaz \|date=2009 \|publisher=Cambridge University Press \|___location=Cambridge ; New York \|chapter=18. Average case complexity: Levin’s theory}}</ref> In other words, an algorithm {{mvar\|A}} has good average-case complexity if, after running for {{math\|''t''<sub>''A''</sub>(''n'')}} steps, {{mvar\|A}} can solve all but a {{math\|{{sfrac\|''n''<sup>''c''</sup>\|(''t''<sub>''A''</sub>(''n''))<sup>''ε''</sup>}}}} fraction of inputs of length {{mvar\|n}}, for some {{math\|''ε'', ''c'' > 0}}.<ref name="bog06"/> ===Distributional problem=== Line 111: * {{cite book \|last1=Wang \|first1=Jie \|url=https://www.cs.uml.edu/~wang/acc-forum/avgcomp.pdf \|title=Complexity Theory: Retrospective II \|date=1997 \|publisher=Springer Science & Business Media \|editor-last1=Hemaspaandra \|editor-first1=Lane A. \|volume=2 \|pages=295–328 \|chapter=Average-case computational complexity theory \|editor-last2=Selman \|editor-first2=Alan L.}} * {{Citation \|last=Goldreich \|first=Oded \|title=Average Case Complexity, Revisited \|date=2011 \|work=Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation \|series=Lecture Notes in Computer Science \|volume=6650 \|pages=422–450 \|editor-last=Goldreich \|editor-first=Oded \|url=https://www.wisdom.weizmann.ac.il/~oded/COL/aver.pdf \|place=Berlin, Heidelberg \|publisher=Springer Berlin Heidelberg \|doi=10.1007/978-3-642-22670-0_29 \|isbn=978-3-642-22669-4}} * {{cite book \|last1=Arora \|first1=Sanjeev \|title=Computational Complexity: A Modern Approach \|last2=Barak \|first2=Boaz \|date=2009 \|publisher=Cambridge University Press \|___location=Cambridge ; New York \|chapter=18. Average case complexity: Levin’s theory}} The literature of average case complexity includes the following work:

Average-case complexity: Difference between revisions