Algoritmens komplexitet i genomsnitt

I beräkningskomplexitetsteorin är den genomsnittliga komplexiteten för en algoritm  mängden av vissa beräkningsresurser (vanligtvis tid) som krävs för att algoritmen ska fungera, i genomsnitt över alla möjliga indata. Konceptet kontrasteras ofta med värsta tänkbara komplexitet , där den maximala komplexiteten för en algoritm över alla indata beaktas.

Det finns tre huvudsakliga skäl för att studera komplexitet i genomsnitt [1] . För det första, även om vissa problem kan vara svåra att lösa i värsta fall, är indata som leder till detta beteende sällsynta i praktiken, så komplexitet i genomsnitt kan vara ett mer exakt mått på prestandan hos en algoritm. För det andra ger komplexitetsanalys i genomsnitt ett sätt och en teknik för att generera komplexa data för ett problem, som kan användas i kryptografi och derandomisering . För det tredje tillåter komplexitet en i genomsnitt att peka ut den mest effektiva algoritmen i praktiken bland algoritmer med samma underliggande komplexitet (som quicksort ).

Analysen av algoritmer kräver i genomsnitt begreppet "genomsnittliga" data för algoritmen, vilket leder till problemet med att tänka igenom sannolikhetsfördelningen av indata. En probabilistisk algoritm kan också användas . Analys av sådana algoritmer leder till den relaterade uppfattningen om förväntad komplexitet [2] .

Historik och bakgrund

Prestandan hos algoritmer i genomsnitt har studerats sedan introduktionen av moderna föreställningar om beräkningseffektivitet på 1950-talet. Det mesta av det inledande arbetet fokuserade på problem för vilka värsta tänkbara polynomtidsalgoritmer var kända [3] . År 1973 publicerade Donald Knuth [4] den tredje volymen av The Art of Computer Programming , där han gav en bred översikt över prestandan i genomsnitt av algoritmer för problem som i värsta fall kan lösas i polynomtid, såsom sortering och beräkna medianen .

En effektiv algoritm för NP-kompletta problem antar i allmänhet att den körs i polynomtid för alla ingångar, vilket motsvarar värsta tänkbara komplexitet. En algoritm som är ineffektiv på en "liten" mängd data kan dock vara ganska effektiv på "majoriteten" av data som påträffas i praktiken. Det är således önskvärt att studera egenskaperna hos algoritmer för vilka komplexiteten i genomsnitt kan skilja sig väsentligt från komplexiteten i värsta fall.

De grundläggande begreppen medelkomplexitet utvecklades av Levin, Leonid Anatolyevich , som publicerade en ensidig artikel [5] 1986 , där han definierade genomsnittlig komplexitet och fullständighet, vilket gav ett exempel på ett komplett problem med distNP-klassen, en analog. av NP-fullständighet för genomsnittlig komplexitet.

Definitioner

Genomsnittlig effektiv algoritm

Det första målet är att definiera exakt vad det betyder att algoritmen är effektiv "i genomsnitt". Man kan försöka definiera en genomsnittlig effektiv algoritm som en algoritm vars förväntade värde är polynom för alla möjliga indata. Denna definition har olika nackdelar. I synnerhet är denna definition inte stabil med avseende på förändringar i beräkningsmodellen (till exempel när en Turing-maskin med flera band byts ut mot en enkelbandsmaskin). Låt till exempel Algoritm A köra i tiden t A (x) på ingång x och algoritm B köra i tiden t A (x) 2 på ingång x. Det vill säga, B är kvadratiskt långsammare än A. Det är intuitivt klart att varje definition av medeleffektivitet måste använda tanken att A är medeleffektiv om och endast om B är medeleffektiv. Antag dock att inmatningen tas slumpmässigt från likformigt fördelade strängar med längden n, och att A löper i tiden n 2 på alla ingångar utom strängen 1 n , som tar tiden 2 n . Det är lätt att kolla den där mattan. förväntan på körtiden för algoritm A är polynom, men mattan. förväntan av algoritm B är exponentiell [3] .

För att skapa en starkare definition av medeleffektivitet är det vettigt att låta A köra på mer än polynomtid på vissa ingångar, men den del av data som A tar mer och mer tid på kommer att bli mindre och mindre. Denna idé fångas i följande formel för den genomsnittliga polynomets gångtid, där löptiden och ingångsfraktionen är balanserade:

för varje n, t, ε > 0 och polynom p, där t A (x) betyder körtiden för algoritmen A vid ingången x [6] . Alternativt kan det skrivas på följande sätt

för någon konstant C, där n = |x| [7] . Algoritm A har med andra ord en bra medelkomplexitet om efter t A (n) steg A kan lösa alla problem, förutom en bråkdel av problem med ingångslängd n, för vissa ε, c > 0 [3] .

Problem med kända distributioner

Nästa steg är att bestämma den "genomsnittliga" inmatningen för en viss uppgift. Detta uppnås genom att associera varje uppgifts input med en viss sannolikhetsfördelning. Det vill säga, det "genomsnittliga" problemet består av språket L (det vill säga en uppsättning ord som representerar indata) och distributionen D som är associerad med det, vilket resulterar i ett par (L, D) (ett problem med kända distributioner) [7] . De två vanligaste klasserna av sannolikhetsfördelning är:

  1. Polynom-tidsberäknarbara (P-beräknade) distributioner är distributioner för vilka summadensiteten för en given ingång x kan beräknas. Formellt, givet en fördelning μ och en rad x ∈ {0, 1} n , kan man beräkna värdet i polynomtid. Av detta följer att Pr[x] också är beräkningsbar i polynomtid.
  2. Polynom-tidskonstruerbara (P-konstruerbara) distributioner är fördelningar som kan tas slumpmässigt i polynomtid.

De två begreppen är inte likvärdiga, även om de är lika. Om en fördelning är P-beräkbar är den också P-konstruerbar, men det omvända är inte sant om P ≠ P #P [7] .

AvgP och distNP

Ett problem med kända fördelningar (L, D) tillhör AvgP-komplexitetsklassen om det finns en genomsnittlig effektiv algoritm för L enligt definitionen ovan. AvgP-klassen kallas ibland i litteraturen för distP [7] .

Ett problem med kända fördelningar (L, D) tillhör distNP-komplexitetsklassen om L tillhör NP och D är P-beräknarbar. Om L tillhör NP och D är P-konstruerbar, så tillhör (L, D) sampNP [7] .

Två klasser, AvgP och distNP, definierar en analogi av P och NP med genomsnittlig komplexitet, respektive [7] .

Reducerbarhet av problem med kända distributioner

Låt (L,D) och (L',D') vara två problem med kända distributioner. (L, D) minskar i genomsnitt till (L', D') (skriven (L, D) ≤ AvgP (L', D')) om det finns en funktion f så att den för varje n kan beräknas vid mata in x i polynomtid i n och

  1. (riktighet) x ∈ L om och endast om f(x) ∈ L'
  2. (Domination) Det finns polynom p och m så att för alla n och y,

Dominansvillkoret leder till tanken att om problemet (L, D) är svårt i genomsnitt, så är (L', D') också svårt i genomsnitt. Intuitivt bör reduktion ge ett sätt att lösa problem L för ingång x genom att beräkna f(x) och mata algoritmens utdata till algoritmen som löser L'. Utan ett dominansvillkor kanske detta inte är möjligt, eftersom en algoritm som löser L i polynomtid i genomsnitt kan köras i superpolynomtid för ett litet antal ingångar, men dessa ingångar kan mappas till en stor mängd i D', så Algoritm A' i polynomtid i genomsnittlig tid fungerar inte. Dominansvillkoret anger att sådana rader kommer att förekomma i D' polynomiskt ofta [6] .

DistNP-fullständiga uppgifter

Analogin med medelkomplexitet för NP-komplexitet är distNP-fullständighet. Ett problem med kända distributioner (L', D') är distNP-komplett om (L', D') tillhör distNP och någon (L, D) i distNP (i medelkomplexitet) kan reduceras till (L', D' ) [7] .

Ett exempel på ett distNP-komplett problem är det begränsade stoppproblemet , BH, definierat enligt följande:

BH = {(M,x,1 t ) : M är en icke -deterministisk Turingmaskin som tar x i ≤ t steg [7] .

I sin uppsats visade Levin ett exempel på ett kakelproblem som är NP-komplett i genomsnitt [5] . En översikt över kända distNP-kompletta problem finns i Wangs bok [6] .

Aktiv forskning pågår för att hitta nya distNP-kompletta problem. Det kan dock vara svårt att hitta sådana problem på grund av Gurevichs resultat, som visade att alla problem med kända distributioner inte kan vara distNP-kompletta om inte EXP = NEXP [8] . (Den enhetliga fördelningen μ är en av fördelningarna för vilka det finns ε > 0 så att för varje x μ(x) ≤ 2 -|x| ε .) Livnes resultat visar att alla naturliga NP-problem har en DistNP-komplett version [ 9] . Målet att hitta naturliga fördelningsproblem som är DistNP-kompletta har dock inte uppnåtts [10] .

Applikationer

Sorteringsalgoritmer

Som nämnts ovan fokuserade mycket av det tidiga arbetet med medelkomplexitet på problem för vilka polynomtidsalgoritmer var kända, såsom sortering. Till exempel har många sorteringsalgoritmer, såsom quicksort , en körtid i värsta fall på O(n 2 ), men en genomsnittlig körtid på O(nlog(n)), där n är längden på data som sorteras [ 11] .

Kryptografi

För de flesta problem har medelkomplexitetsanalys genomförts för att hitta effektiva algoritmer för ett problem som i värsta fall anses vara svårt i komplexiteten. Inom kryptografi är dock motsatsen sant – komplexitet är i värsta fall oviktigt, istället vill vi garantera att alla algoritmer som i genomsnitt är komplexa, som "bryter" ett kryptografiskt schema, är ineffektiva [12] .

Alltså är alla kryptografiska scheman baserade på förekomsten av envägsfunktioner [3] . Även om förekomsten av envägsfunktioner förblir ett öppet problem, är många kandidater för envägsfunktioner baserade på svåra problem, såsom heltalsfaktorisering eller beräkning av den diskreta logaritmen . Observera att det inte är önskvärt att en kandidatfunktion är NP-komplett, eftersom detta bara säkerställer att det inte finns någon effektiv algoritm för värsta tänkbara komplexitet. Faktum är att vi vill säkerställa att det inte finns någon effektiv algoritm som löser problemet för slumpmässiga indata (det vill säga i komplexitet i genomsnitt). Faktum är att både problemet med att faktorisera heltal och problemet med att beräkna den diskreta logaritmen tillhör NP ∩ coNP , och därför tror man inte att de är NP-kompletta [7] . Det faktum att all kryptografi baseras på att det finns problem som är svåra att lösa i genomsnitt i NP är en av huvudorsakerna till att studera komplexitet i genomsnitt.

Andra resultat

1990 visade Impagliazzo och Levin att om det finns en genomsnittlig effektiv algoritm för ett distNP-komplett problem under enhetlig fördelning, så finns det en genomsnittlig effektiv algoritm för alla problem i NP för vilken fördelning som helst konstruerad i polynomtid [13] . Tillämpningen av denna teori på problem med naturliga kända distributioner är fortfarande en öppen fråga [3] .

1992 visade Ben-David et al. att om alla språk i distNP har bra genomsnittliga beslutsalgoritmer , har de bra genomsnittliga sökalgoritmer. Dessutom visade de att detta gäller under svagare antaganden - om något språk i NP är enkelt i genomsnitt för urvalsalgoritmer under enhetlig fördelning, så kommer det också att vara genomsnittligt enkelt för sökalgoritmer under enhetlig fördelning [14] . Således kan kryptografiska envägsfunktioner endast existera om det finns problem från distNP över en enhetlig fördelning som i genomsnitt är svåra för beslutsalgoritmer .

1993 visade Feigenbaum och Fortnow att det är omöjligt att bevisa, under icke-adaptiv slumpmässig reduktion, att förekomsten av en bra medelalgoritm för ett distNP-komplett problem under enhetlig fördelning innebär att det finns en värsta tänkbar effektiv algoritm i NP [15] . År 2003 generaliserade Bogdanov och Trevisan detta resultat till en godtycklig icke-adaptiv minskning [16] . Detta resultat visar att det knappast är möjligt att hitta ett samband mellan genomsnittlig komplexitet och värsta tänkbara komplexitet med hjälp av reduktion [3] .

Se även

Anteckningar

  1. ↑ Goldreich, Vadhan, 2007 , sid. 325–330.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2009 , sid. 28.
  3. ↑ 1 2 3 4 5 6 Bogdanov och Trevisan, 2006 , sid. 1–106.
  4. ↑ Knuth, 1973 .
  5. ↑ 12 Levin , 1986 , sid. 285–286.
  6. ↑ 1 2 3 Wang, 1997 , sid. 295–328.
  7. ↑ 1 2 3 4 5 6 7 8 9 Arora, Barak, 2009 .
  8. ↑ Gurevich, 1987 , sid. 111–117.
  9. ↑ Livene, 2006 .
  10. ↑ Goldreich, 1997 .
  11. ↑ Cormen, Leiserson, Rivest, Stein, 2009 .
  12. ↑ Katz, Lindell, 2007 .
  13. ↑ Impagliazzo och Levin 1990 , sid. 812–821.
  14. ↑ Ben-David, Chor, Goldreich, Luby, 1992 , sid. 193–219.
  15. ↑ Feigenbaum, Fortnow, 1993 , sid. 994–1005.
  16. ↑ Bogdanov, Trevisan, 2003 , sid. 308–317.

Litteratur

Ytterligare läsning