In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.
There are three primary motivations for studying average-case complexity.[1] First, although some problems may be intractable in the worst-case, the inputs which elicit this behavior may rarely occur in practice, so the average-case complexity may be a more accurate measure of an algorithm's performance. Second, average-case complexity analysis provides tools and techniques to generate hard instances of problems which can be utilized in areas such as cryptography and derandomization. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instance Quicksort).
Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a probability distribution over inputs. Alternatively, a randomized algorithm can be used. The analysis of such algorithms leads to the related notion of an expected complexity.[2]: 28
History and background
The average-case performance of algorithms has been studied since modern notions of computational efficiency were developed in the 1950s. Much of this initial work focused on problems for which worst-case polynomial time algorithms were already known.[3] In 1973, Donald Knuth[4] published Volume 3 of the Art of Computer Programming which extensively surveys average-case performance of algorithms for problems solvable in worst-case polynomial time, such as sorting and median-finding.
An efficient algorithm for NP-complete problems is generally characterized as one which runs in polynomial time for all inputs; this is equivalent to requiring efficient worst-case complexity. However, an algorithm which is inefficient on a "small" number of inputs may still be efficient for "most" inputs that occur in practice. Thus, it is desirable to study the properties of these algorithms where the average-case complexity may differ from the worst-case complexity and find methods to relate the two.
The fundamental notions of average-case complexity were developed by Leonid Levin in 1986 when he published a one-page paper[5] defining average-case complexity and completeness while giving an example of a complete problem for distNP, the average-case analogue of NP.
Definitions
Efficient average-case complexity
The first task is to precisely define what is meant by an algorithm which is efficient "on average". An initial attempt might define an efficient average-case algorithm as one which runs in expected polynomial time over all possible inputs. Such a definition has various shortcomings; in particular, it is not robust to changes in the computational model. For example, suppose algorithm A runs in time tA(x) on input x and algorithm B runs in time tA(x)2 on input x; that is, B is quadratically slower than A. Intuitively, any definition of average-case efficiency should capture the idea that A is efficient-on-average if and only if B is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with length n, and that A runs in time n2 on all inputs except the string 1n for which A takes time 2n. Then it can be easily checked that the expected running time of A is polynomial but the expected running time of B is exponential.[3]
To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm A to run longer than polynomial time on some inputs but the fraction of inputs on which A requires larger and larger running time becomes smaller and smaller. This intuition is captured in the following formula for average polynomial running time, which balances the polynomial trade-off between running time and fraction of inputs:
for every n, t > 0 and polynomial p, where tA(x) denotes the running time of algorithm A on input x, and ε is a positive constant value.[6] Alternatively, this can be written as
for some constants C and ε, where n = |x|.[7] In other words, an algorithm A has good average-case complexity if, after running for tA(n) steps, A can solve all but a nc/(tA(n))ε fraction of inputs of length n, for some ε, c > 0.[3]
Distributional problem
The next step is to define the "average" input to a particular problem. This is achieved by associating the inputs of each problem with a particular probability distribution. That is, an "average-case" problem consists of a language L and an associated probability distribution D which forms the pair (L, D).[7] The two most common classes of distributions which are allowed are:
Polynomial-time computable distributions (P-computable): these are distributions for which it is possible to compute the cumulative density of any given input x. More formally, given a probability distribution μ and a string x ∈ {0, 1}n it is possible to compute the value in polynomial time. This implies that Pr[x] is also computable in polynomial time.
Polynomial-time samplable distributions (P-samplable): these are distributions from which it is possible to draw random samples in polynomial time.
These two formulations, while similar, are not equivalent. If a distribution is P-computable it is also P-samplable, but the converse is not true if P ≠ P#P.[7]
AvgP and distNP
A distributional problem (L, D) is in the complexity class AvgP if there is an efficient average-case algorithm for L, as defined above. The class AvgP is occasionally called distP in the literature.[7]
A distributional problem (L, D) is in the complexity class distNP if L is in NP and D is P-computable. When L is in NP and D is P-samplable, (L, D) belongs to sampNP.[7]
Together, AvgP and distNP define the average-case analogues of P and NP, respectively.[7]
Reductions between distributional problems
Let (L,D) and (L′, D′) be two distributional problems. (L, D) average-case reduces to (L′, D′) (written (L, D) ≤AvgP (L′, D′)) if there is a function f that for every n, on input x can be computed in time polynomial in n and
(Correctness) x ∈ L if and only if f(x) ∈ L′
(Domination) There are polynomials p and m such that, for every n and y,
The domination condition enforces the notion that if problem (L, D) is hard on average, then (L′, D′) is also hard on average. Intuitively, a reduction should provide a way to solve an instance x of problem L by computing f(x) and feeding the output to the algorithm which solves L'. Without the domination condition, this may not be possible since the algorithm which solves L in polynomial time on average may take super-polynomial time on a small number of inputs but f may map these inputs into a much larger set of D' so that algorithm A' no longer runs in polynomial time on average. The domination condition only allows such strings to occur polynomially as often in D'.[6]
DistNP-complete problems
The average-case analogue to NP-completeness is distNP-completeness. A distributional problem (L′, D′) is distNP-complete if (L′, D′) is in distNP and for every (L, D) in distNP, (L, D) is average-case reducible to (L′, D′).[7]
An example of a distNP-complete problem is the Bounded Halting Problem, (BH,D) (for any P-computable D) defined as follows:
In his original paper, Levin showed an example of a distributional tiling problem that is average-case NP-complete.[5] A survey of known distNP-complete problems is available online.[6]
One area of active research involves finding new 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 distNP-complete unless EXP = NEXP.[8] (A flat distribution μ is one for which there exists an ε > 0 such that for any x, μ(x) ≤ 2−|x|ε.) A result by Livne shows that all natural NP-complete problems have DistNP-complete versions.[9] However, the goal of finding a natural distributional problem that is DistNP-complete has not yet been achieved.[10]
Applications
Sorting algorithms
As mentioned above, much early work relating to average-case complexity focused on problems for which polynomial-time algorithms already existed, such as sorting. For example, many sorting algorithms which utilize randomness, such as Quicksort, have a worst-case running time of O(n2), but an average-case running time of O(n log(n)), where n is the length of the input to be sorted.[2]
Cryptography
For most problems, average-case complexity analysis is undertaken to find efficient algorithms for a problem that is considered difficult in the worst-case. In cryptographic applications, however, the opposite is true: the worst-case complexity is irrelevant; we instead want a guarantee that the average-case complexity of every algorithm which "breaks" the cryptographic scheme is inefficient.[11]
Thus, all secure cryptographic schemes rely on the existence of one-way functions.[3] Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on hard problems such as integer factorization or computing the discrete log. Note that it is not desirable for the candidate function to be NP-complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are in NP ∩ coNP, and are therefore not believed to be NP-complete.[7] The fact that all of cryptography is predicated on the existence of average-case intractable problems in NP is one of the primary motivations for studying average-case complexity.
Other results
In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for a distNP-complete problem under the uniform distribution, then there is an average-case algorithm for every problem in NP under any polynomial-time samplable distribution.[12] Applying this theory to natural distributional problems remains an outstanding open question.[3]
In 1992, Ben-David et al. showed that if all languages in distNP have good-on-average decision algorithms, they also have good-on-average search algorithms. Further, they show that this conclusion holds under a weaker assumption: if every language in NP is easy on average for decision algorithms with respect to the uniform distribution, then it is also easy on average for search algorithms with respect to the uniform distribution.[13] Thus, cryptographic one-way functions can exist only if there are distNP problems over the uniform distribution that are hard on average for decision algorithms.
In 1993, Feigenbaum and Fortnow showed that it is not possible to prove, under non-adaptive random reductions, that the existence of a good-on-average algorithm for a distNP-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in NP.[14] In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions.[15] These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.[3]
^O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.
^ abCormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN0-262-03384-4.
^ abcdefA. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.
^O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.
^J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
^R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.
^S. Ben-David, B. Chor, O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.
^J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.
^A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 2003.
Further reading
The literature of average case complexity includes the following work:
Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem", Information Processing Letters, 23 (2): 103–106, doi:10.1016/0020-0190(86)90051-7.
Flajolet, Philippe; Vitter, J. S. (August 1987), Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France.
Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems", Proc. 10th National Conference on Artificial Intelligence, pp. 459–465.
Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity", Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp. 128–139.
Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Precise average case complexity", Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661.
Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures[online]Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
Pembantaian SinjarBagian dari Serangan di Irak Utara (Agustus 2014) dan intervensi Amerika Serikat di Irak 2014Pesawat F/A-18C Hornet di atas kapal induk USS George H.W. Bush sebelum melancarkan serangan udara.Tanggal3–14 Agustus 2014(1 minggu dan 4 hari)LokasiŞingal (Sinjar), Provinsi Nineveh, IrakHasil Daulah Islamiyah merebut Sinjar[6] dan membantai 500 orang Yazidi;[7] Serangan udara Amerika Serikat menghentikan pengepungan Daulah Islamiyah atas[8] 50.000…
Jenna OrtegaJenna Ortega, 2022LahirJenna Marie Ortega[1]27 September 2002 (umur 21)[2]Coach Valley, California[2]PekerjaanAktrisTahun aktif2012–sekarangTanda tangan Jenna Marie Ortega[1] (lahir 27 September 2002[2]) adalah seorang aktris asal Amerika Serikat. Di televisi, ia memerankan Jane Muda di serial drama romantis, Jane the Virgin, Harley Diaz di serial Disney Channel, Stuck in the Middle dan Ellie Alves di serial thriller Netflix, You. P…
Brittany MurphyMurphy pada 26 November 2006 London premiere pada Happy FeetLahirBrittany Anne Bertolotti[1](1977-11-10)10 November 1977Atlanta, Georgia, Amerika SerikatMeninggal20 Desember 2009(2009-12-20) (umur 32)Los Angeles, California, Amerika SerikatSebab meninggalPneumonia dan anaemia[2]MakamForest Lawn Memorial ParkLos Angeles, California, Amerika SerikatBright Eternity, Lot 7402, Grave 1[3]34°08′39″N 118°19′11″W / 34.14414°N 11…
Artikel ini berisi tentang divisi dari divisi Grup Fiat yang memproduksi mobil dengan merek Fiat. Untuk induk perusahaannya, lihat Fiat Fiat Automobiles S.p.A.JenisPrivatIndustriOtomotifDidirikan11 Juli 1899 di Turin, ItaliaPendiriGiovanni AgnelliKantorpusatTurin, ItaliaWilayah operasiInternasionalTokohkunciLuca di Montezemolo (Presiden)Sergio Marchionne (CEO)ProdukMobilIndukStellantisSitus webFiat.com Fiat Grande Punto - Auto Moto Show Katowice 2006. Fiat, akronim dari Fabbrica Italiana Automob…
Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Noel Evelyn Norris (25 Desember 1918 - 15 Februari 2014) adalah pendidik berkewarganegaraan Singapura yang dikenal terkait erat dengan Raffles Girls' Primary School. Norris adalah kepala sekolah Crescent Girls' School. Norris adalah relawan di Angkatan Ud…
2008 United States Senate election in Louisiana ← 2002 November 4, 2008 2014 → Nominee Mary Landrieu John Kennedy Party Democratic Republican Popular vote 988,298 867,177 Percentage 52.11% 45.72% Parish resultsCongressional district resultsPrecinct resultsLandrieu: 40-50% 50–60% 60–70% 70–80% 80–90% &…
شعار جائزة نوبل. تمنُح جوائز نوبل (بالسويدية: Nobelpriset، وبالنرويجية: Nobelprisen) كل عام من قبل الأكاديمية الملكية السويدية للعلوم والأكاديمية السويدية ومعهد كارولنسكا ولجنة نوبل النرويجية، وذلك للأفراد والمنظمات ذوي الإسهامات البارزة في مجالات الكيمياء والفيزياء والأدب والسلام …
Dwight McNeil Dwight McNeil bermain untuk Burnley, 2018Informasi pribadiNama lengkap Dwight McNeilTanggal lahir 22 November 1999 (umur 24)Tempat lahir Rochdale, InggrisTinggi 1,83 m (6 ft 0 in)Posisi bermain GelandangInformasi klubKlub saat ini EvertonNomor 7Karier junior0000–2004 JJB Sports2004–2014 Manchester United2014–2018 BurnleyKarier senior*Tahun Tim Tampil (Gol)2018–2022 Burnley 134 (7)2022– Everton 40 (7)Tim nasional‡2019 Inggris U-20 6 (1)2019–2021 Ing…
Фазовая диаграмма двухкомпонентного положительного азеотропа (состав отмечен пунктирной линией) Азеотро́пная смесь — смесь двух или более жидкостей с таким составом, который (при данном конкретном давлении) не меняется при кипении, то есть составы равновесных жидкой …
Untuk kegunaan lain, lihat East of Eden (disambiguasi). Eden of the EastGambar sampul volume DVD versi Jepang menampilkan tokoh protagonis Saki Morimi dan Akira Takizawa東のエデン(Higashi no Eden)GenreMisteri, psikologi Seri animeSutradaraKenji KamiyamaProduserKoji YamamotoTomohiko IshiiSkenarioKenji KamiyamaMusikKenji KawaiStudioProduction I.GPelisensiAUS Madman EntertainmentID PonimuNA FunimationUK Anime LimitedSaluranasliFuji TV (Noitamina)Saluran bahasa InggrisUS Funimation ChannelTayan…
Paralel utara ke-38 (Hangul: 삼팔선/Sampalseon, Hanja: 八線/Samp'alsŏn) adalah sebuah lingkaran lintang imajiner yang berada pada lintang 38 derajat sebelah utara garis khatulistiwa Bumi. Paralel ke-38 amat penting dalam sejarah terkini Korea. Bermula di meridian utama yang menghadap ke arah timur, parallel 38° utara melintasi: Laut Tengah; Italia (Sisilia dan sejumlah kecil daratan utama; Laut Ionia; Yunani; Laut Aegea; Turki; Iran; Laut Kaspia; Turkmenistan; Uzbekistan; Tajikistan; Afga…
Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Tekla TrapszoLahir(1873-09-23)23 September 1873Kalisz, Polandia, Kekaisaran Rusia (kini Kalisz, Polandia)Meninggal27 Oktober 1944(1944-10-27) (umur 71)Warsawa, PolandiaPekerjaanPemeranTahun aktif1911-1939 Tekla Trapszo (23 September 1873 …
1940 film by Anatole Litvak This article is about the film. For the album by Andrew Gold, see All This and Heaven Too (album). All This, and Heaven TooTheatrical release posterDirected byAnatole LitvakScreenplay byCasey RobinsonBased onAll This, and Heaven Too (1938 novel)by Rachel FieldProduced byDavid LewisHal B. WallisStarringBette DavisCharles BoyerBarbara O'NeilCinematographyErnie HallerEdited byWarren LowMusic byMax SteinerDistributed byWarner Bros.Release date July 4, 1940 …
Ne doit pas être confondu avec Jean Malo-Renault ou Nori Malo-Renault. Malo-RenaultMalo-Renault dans sa chambre-atelier (1900 Paris)Naissance 5 octobre 1870Saint-Malo, FranceDécès 19 juillet 1938 (à 67 ans)Mort accidentelle au le Havre, FranceSépulture Saint-Malo, Cimetière de RocabeyNom de naissance Émile Auguste RenaultPseudonyme Malo-RenaultNationalité FrançaisActivités Dessinateur, pastelliste,graveur,illustrateurAutres activités AuteurFormation École nationale supérieure d…
Underground publications in the Soviet bloc For other uses, see Samizdat (disambiguation). SamizdatRussian samizdat and photo negatives of unofficial literatureRussianсамиздатRomanizationsamizdatLiteral meaningself-publishing Samizdat (Russian: самиздат, lit. 'self-publishing') was a form of dissident activity across the Eastern Bloc in which individuals reproduced censored and underground makeshift publications, often by hand, and passed the documents from reader t…
ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Раннее христианство Гностическое христианство Вселенские соборы Ни…
Ballon d'Or 2009Pemenang Ballon d'Or 2009 Lionel MessiTanggal1 Desember 2009 (2009-12-01)LokasiParis, PrancisNegaraPrancisDipersembahkan olehFrance FootballIkhtisarDimenangkan oleh Lionel Messi (gelar pertama)Situs webwww.francefootball.fr← 2008 Ballon d'Or2010 → Ballon d'Or 2009, yang diberikan kepada pemain sepak bola terbaik di dunia menurut penilaian panel jurnalis olahraga internasional, dianugerahkan kepada Lionel Messi dari Barcelona pada 1 Desember 2009.[1] Messi…