Average-case complexity: Difference between revisions

Revision as of 20:32, 19 June 2025

Latest revision as of 07:18, 21 July 2025

(One intermediate revision by one other user not shown)

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''_''A''(''n'')}} steps, {{mvar|A}} can solve all but a {{math|{{sfrac|''n''^''c''|(''t''_''A''(''n''))^''ε''}}}} fraction of inputs of length {{mvar|n}}, for some {{math|''ε'', ''c'' &gt; 0}}.<ref name="bog06"/>

===Distributional problem===

Line 68:

In his original paper, Levin showed an example of a distributional tiling problem that is average-case {{math|'''NP'''}}-complete.<ref name="levin86"/> A survey of known {{math|'''distNP'''}}-complete problems is available online.<ref name="wangsurvey"/>

One area of active research involves finding new {{math|'''distNP'''}}-complete problems. However, finding such problems can be complicated due to a result of Gurevich which shows that any distributional problem with a flat distribution cannot be {{math|'''distNP'''}}-complete unless [[EXP|{{math|'''EXP'''}}]] = [[NEXP|{{math|'''NEXP'''}}]].<ref name="gur87">{{Cite book |last=Gurevich |first=Yuri |chapter=Complete and incomplete randomized NP problems |date=October 1987 |title=28th Annual Symposium on Foundations of Computer Science (SFCS 1987) |chapter-url=https://ieeexplore.ieee.org/document/4568261 |pages=111–117 |doi=10.1109/SFCS.1987.14|isbn=0-8186-0807-2 }}</ref> (A flat distribution {{mvar|μ}} is one for which there exists an {{math|''ε'' &gt; 0}} such that for any {{mvar|x}}, {{math|''μ''(''x'') ≤ 2^{−{{abs|''x''}}^''ε''}}}.) A result by Livne shows that all natural {{math|'''NP'''}}-complete problems have {{math|'''DistNP'''}}-complete versions.<ref name="livne06">{{Cite journal |last=Livne |first=Noam |date=December 2010 |title=All Natural NP-Complete Problems Have Average-Case Complete Versions |url=http://link.springer.com/10.1007/s00037-010-0298-9 |journal=Computational Complexity |language=en |volume=19 |issue=4 |pages=477–499 |doi=10.1007/s00037-010-0298-9 |issn=1016-3328|url-access=subscription }}</ref> However, the goal of finding a natural distributional problem that is {{math|'''DistNP'''}}-complete has not yet been achieved.<ref name="gol97">{{Citation |last=Goldreich |first=Oded |title=Notes on Levin's Theory of Average-Case Complexity |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=233–247 |editor-last=Goldreich |editor-first=Oded |url=http://link.springer.com/10.1007/978-3-642-22670-0_21 |access-date=2025-05-21 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-22670-0_21 |isbn=978-3-642-22669-4|url-access=subscription }}</ref>

==Applications==

Line 108:

Pedagogical presentations:

* {{Cite book |last=Impagliazzo |first=R. |chapter=A personal view of average-case complexity |date=1995 |title=Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference |chapter-url=https://ieeexplore.ieee.org/document/514853 |publisher=IEEE Comput. Soc. Press |pages=134–147 |doi=10.1109/SCT.1995.514853 |isbn=978-0-8186-7052-7}}

* {{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: