Az algoritmus összetettsége átlagosan

A számítási komplexitás elméletében egy algoritmus átlagos összetettsége az algoritmus  működéséhez szükséges számítási erőforrások (általában idő) mennyisége, az összes lehetséges bemenetre átlagolva. A koncepciót gyakran szembeállítják a legrosszabb eset bonyolultságával , ahol egy algoritmus minden bemenetre kiterjedő maximális komplexitását veszik figyelembe.

A komplexitás tanulmányozásának átlagosan három fő oka van [1] . Először is, bár egyes problémákat a legrosszabb esetben nehéz megoldani, a gyakorlatban ritkák az ehhez a viselkedéshez vezető bemenetek, így az átlagos komplexitás pontosabb mércéje lehet egy algoritmus teljesítményének. Másodszor, a komplexitáselemzés átlagosan eszközt és technikát biztosít egy probléma összetett adatának előállítására, amely felhasználható a kriptográfiában és a derandomizálásban . Harmadszor, a komplexitás átlagosan lehetővé teszi a gyakorlatban leghatékonyabb algoritmus kiválasztását az azonos mögöttes összetettségű algoritmusok közül (mint például a Quicksort ).

Az algoritmusok átlagos elemzéséhez szükség van az algoritmus "átlagos" adatainak fogalmára, ami a bemeneti adatok valószínűségi eloszlásán keresztüli gondolkodás problémájához vezet. Valószínűségi algoritmus is használható . Az ilyen algoritmusok elemzése a várható komplexitás kapcsolódó fogalmához vezet [2] .

Előzmények és háttér

Az algoritmusok átlagos teljesítményét a számítási hatékonyság modern fogalmainak az 1950-es években történő bevezetése óta tanulmányozzák. A kezdeti munka nagy része olyan problémákra összpontosított, amelyekre a legrosszabb esetre ismert polinomiális idő algoritmusok voltak ismertek [3] . 1973-ban Donald Knuth [4] kiadta The Art of Computer Programming című könyvének harmadik kötetét , amelyben átfogó áttekintést adott a legrosszabb esetben polinomiális időben megoldható feladatok algoritmusainak átlagos teljesítményéről, mint például a rendezés. és a medián kiszámítása .

Az NP-teljes problémák hatékony algoritmusa általában azt feltételezi, hogy polinomiális időben fut minden bemenetre, ami megegyezik a legrosszabb eset bonyolultságával. Azonban egy olyan algoritmus, amely nem hatékony "kis" adatmennyiség esetén, meglehetősen hatékony lehet a gyakorlatban előforduló adatok "többségénél". Így kívánatos azoknak az algoritmusoknak a tulajdonságainak tanulmányozása, amelyek komplexitása átlagosan jelentősen eltérhet a legrosszabb esetben tapasztalt komplexitástól.

Az átlagos komplexitás alapfogalmait Levin, Leonyid Anatoljevics dolgozta ki , aki 1986-ban publikált egy egyoldalas cikket [5] , amelyben meghatározta az átlagos komplexitást és teljességet, példát adva a distNP osztály teljes problémájára, egy analógra. az NP-teljesség átlagos komplexitása esetén.

Definíciók

Átlagosan hatékony algoritmus

Az első cél az, hogy pontosan meghatározzuk, mit jelent az algoritmus „átlagosan” hatékony. Megpróbálhatunk egy átlagosan hatékony algoritmust úgy definiálni, mint olyan algoritmust, amelynek várható értéke polinomiális minden lehetséges bemenetre. Ennek a definíciónak számos hátránya van. Ez a definíció különösen nem stabil a számítási modell változásai tekintetében (például ha egy többszalagos Turing -gépet egyszalagosra cserélünk). Legyen például az A algoritmus t A (x) időben fut az x bemeneten, és a B algoritmus fut a t A (x) 2 időben az x bemeneten. Ez azt jelenti, hogy B négyzetesen lassabb, mint A. Intuitív módon világos, hogy az átlagos hatásfok bármely definíciójának használnia kell azt az elképzelést, hogy A akkor és csak akkor átlagosan hatékony, ha B átlagos hatékonyságú. Tegyük fel azonban, hogy a bemenetet véletlenszerűen vesszük egyenletes eloszlású n hosszúságú karakterláncokból, és A n 2 időben fut minden bemeneten, kivéve az 1 n karakterláncot, amely 2 n időt vesz igénybe . Ezt a szőnyeget könnyű ellenőrizni. az A algoritmus futási idejére vonatkozó elvárás polinomiális, de a mat. a B algoritmus elvárása exponenciális [3] .

Az átlagos hatékonyság pontosabb meghatározásához érdemes hagyni, hogy A-t több mint polinomiális idő alatt fusson néhány bemeneten, de az adatok azon része, amelyre A egyre több időt vesz igénybe, egyre kisebb lesz. Ezt az ötletet az átlagos polinomi futási idő alábbi képlete rögzíti, amelyben a futási idő és a bemeneti hányad egyensúlyban van:

bármely n, t, ε > 0 és p polinom esetén, ahol t A (x) az A algoritmus futási idejét jelenti az x bemeneten [6] . Alternatív megoldásként a következőképpen is felírható

valamilyen C állandóra, ahol n = |x| [7] . Más szóval, az A algoritmus átlagos komplexitása jó, ha t A (n) után az A lépések minden problémát megoldanak, kivéve az n bemeneti hosszúságú feladatok töredékét, néhány ε esetén c > 0 [3] .

Problémák az ismert disztribúciókkal

A következő lépés egy adott feladat "átlagos" bemenetének meghatározása. Ezt úgy érjük el, hogy az egyes feladatok bemenetét egy bizonyos valószínűségi eloszláshoz társítjuk. Vagyis az "átlagos" probléma az L nyelvből (vagyis a bemeneti adatokat reprezentáló szavak halmazából) és a hozzá tartozó D eloszlásból áll, ami egy (L, D) párt eredményez (probléma az ismert eloszlásoknál) [7] . A valószínűségi eloszlás két leggyakoribb osztálya:

  1. A polinomidőben kiszámítható (P-számítható) eloszlások olyan eloszlások, amelyekre bármely adott x bemenet összegsűrűsége kiszámítható. Formálisan egy μ eloszlás és egy x ∈ {0, 1} n sor esetén az érték polinomiális időben számítható ki . Ebből következik, hogy Pr[x] polinomiális időben is kiszámítható.
  2. A polinomidőben konstruálható (P-konstruálható) eloszlások olyan eloszlások, amelyek polinomiális időben véletlenszerűen mintavételezhetők.

A két fogalom nem ekvivalens, bár hasonlóak. Ha egy eloszlás P-számítható, akkor P-konstruálható is, de ennek fordítottja nem igaz, ha P ≠ P #P [7] .

AvgP és distNP

Egy ismert eloszlású (L, D) probléma az AvgP komplexitási osztályba tartozik, ha létezik egy átlagosan hatékony algoritmus L-hez a fent meghatározottak szerint. Az AvgP osztályt a szakirodalom néha distP-nek nevezi [7] .

Egy ismert eloszlású (L, D) probléma a distNP komplexitási osztályba tartozik, ha L NP-hez tartozik, D pedig P-számítható. Ha L az NP-hez tartozik, és D P-konstruálható, akkor (L, D) a sampNP-hez tartozik [7] .

Két osztály, az AvgP és a distNP az átlagos komplexitású P és NP analógiáját határozza meg [7] .

Az ismert disztribúciókkal kapcsolatos problémák csökkentése

Legyen (L,D) és (L',D') két probléma ismert eloszlásokkal. (L, D) átlagosan (L', D')-re redukál (írva (L, D) ≤ AvgP (L', D')), ha létezik olyan f függvény, amely bármely n esetén kiszámítható adja meg az x-et polinomiális időben n-ben és

  1. (Helyesség) x ∈ L akkor és csak akkor, ha f(x) ∈ L'
  2. (Domináció) Vannak olyan p és m polinomok, amelyek bármely n és y esetén

A dominancia feltétel ahhoz a gondolathoz vezet, hogy ha a feladat (L, D) átlagosan nehéz, akkor (L', D') is átlagosan nehéz. Intuitív módon a redukciónak módot kell adnia az x bemenetre vonatkozó L probléma megoldására az f(x) kiszámításával, és az algoritmus kimenetét betáplálnia kell az L'-t megoldó algoritmusba. Dominancia feltétel nélkül ez nem biztos, hogy lehetséges, hiszen egy L-t átlagosan polinomiális időben megoldó algoritmus kis számú bemenet esetén szuperpolinom időben is futhat, de ezek a bemenetek leképezhetők egy nagy halmazra D'-ben, így a Az A' algoritmus polinomiális időben átlagosan nem fog működni. A dominancia feltétele meghatározza, hogy az ilyen sorok gyakran előfordulnak D' polinomiálisan [6] .

DistNP-teljes feladatok

Az NP-komplexitás közepes komplexitású analógiája a distNP-teljesség. Az ismert eloszlások (L', D') problémája distNP-teljes, ha (L', D') a distNP-hez tartozik, és a distNP-ben (közepes komplexitású) bármely (L, D') redukálható (L', D') ) [ 7] .

A distNP-teljes probléma egy példája a korlátozott leállítási probléma , BH, a következőképpen definiálva:

BH = {(M,x,1 t ) : M egy nem determinisztikus Turing-gép , amely x ≤ t lépésben veszi fel [7] .

Levin dolgozatában példát mutatott egy olyan burkolás problémára, amely átlagosan NP-teljes [5] . Az ismert distNP-teljes problémák áttekintése megtalálható Wang [6] könyvében .

Aktív kutatások folynak új distNP-teljes problémák keresése érdekében. Azonban az ilyen problémák megtalálása nehéz lehet Gurevich eredménye miatt, amely azt mutatta, hogy az ismert eloszlásokkal kapcsolatos bármely probléma nem lehet distNP-teljes, hacsak nem EXP = NEXP [8] . (A μ egyenletes eloszlás az egyik olyan eloszlás, amelyre ε > 0 van úgy, hogy bármely x μ(x) esetén ≤ 2 -|x| ε .) Livne eredménye azt mutatja, hogy minden természetes NP-probléma rendelkezik DistNP-teljes változattal [ 9] . A DistNP-teljes természetes eloszlási problémák megtalálásának célját azonban nem sikerült elérni [10] .

Alkalmazások

Rendezési algoritmusok

Ahogy fentebb említettük, az átlagos összetettséggel foglalkozó korai munkák nagy része olyan problémákra összpontosított, amelyekre polinomiális idő algoritmusokat ismertek, mint például a rendezés. Például sok rendezési algoritmus, mint például a quicksort , a legrosszabb eset futásideje O(n 2 ), de az átlagos futási ideje O(nlog(n)), ahol n a rendezett adatok hossza [ 11] .

Kriptográfia

A legtöbb probléma esetében átlagos komplexitáselemzést végeztek, hogy hatékony algoritmusokat találjanak egy olyan problémára, amelyet a legrosszabb esetben bonyolultnak tekintenek. A kriptográfiában azonban ennek az ellenkezője igaz – a bonyolultság a legrosszabb esetben nem fontos; ehelyett azt szeretnénk garantálni, hogy minden átlagosan összetett algoritmus, amely "megtöri" a kriptográfiai sémát, nem hatékony [12] .

Így minden kriptográfiai séma az egyirányú függvények meglétén alapul [3] . Bár az egyirányú függvények létezése továbbra is nyitott probléma, az egyirányú függvényekre sok jelölt nehéz problémákon alapul, mint például az egész számok faktorizálása vagy a diszkrét logaritmus kiszámítása . Megjegyezzük, hogy nem kívánatos, hogy egy jelölt függvény NP-teljes legyen, mivel ez csak azt biztosítja, hogy ne legyen hatékony algoritmus a legrosszabb eset bonyolultságára. Valójában azt szeretnénk elérni, hogy ne legyen olyan hatékony algoritmus, amely véletlenszerű bemenetekre (vagyis átlagosan bonyolultságra) oldja meg a problémát. Valójában mind az egész számok faktorálásának, mind a diszkrét logaritmus kiszámításának problémája NP ∩ coNP -hez tartozik , ezért nem hisszük, hogy NP-teljesek [7] . Az a tény, hogy minden kriptográfia az NP-ben átlagosan nehezen megoldható problémák meglétén alapul, az egyik fő oka annak, hogy az átlagos komplexitást tanulmányozzuk.

Egyéb eredmények

1990-ben Impagliazzo és Levin kimutatta, hogy ha van egy átlagosan hatékony algoritmus egy distNP-teljes problémára egyenletes eloszlás mellett, akkor létezik egy átlagos hatékony algoritmus az NP bármely problémájára bármely polinomidőben szerkesztett eloszlásra [13] . Ennek az elméletnek az alkalmazása a természetes ismert eloszlások problémáira továbbra is nyitott kérdés [3] .

1992-ben Ben-David és munkatársai kimutatták, hogy ha a distNP összes nyelvének jó átlagos döntési algoritmusa van, akkor jó átlagos keresési algoritmusaik is vannak. Sőt, kimutatták, hogy ez gyengébb feltevés esetén is érvényes – ha az NP-ben bármelyik nyelv átlagosan egyszerű az egyenletes eloszlású kiválasztási algoritmusok számára, akkor az egyenletes eloszlású keresőalgoritmusok esetében is átlagosan egyszerű [14] . Így a kriptográfiai egyirányú függvények csak akkor létezhetnek, ha a distNP-ből olyan problémák vannak egyenletes eloszláson, amelyek átlagosan nehézkesek a döntési algoritmusok számára .

1993-ban Feigenbaum és Fortnow kimutatta, hogy nem adaptív véletlenszerű redukcióval lehetetlen bizonyítani, hogy egy jó átlagos algoritmus létezése egy distNP-teljes problémára egyenletes eloszlás mellett azt jelenti, hogy létezik a legrosszabb eset hatékony algoritmusa NP-ben. [15] . 2003-ban Bogdanov és Trevisan ezt az eredményt önkényes, nem adaptív redukcióra általánosította [16] . Ez az eredmény azt mutatja, hogy az átlagos komplexitás és a legrosszabb eset komplexitása között aligha lehet kapcsolatot találni redukcióval [3] .

Lásd még

Jegyzetek

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

Irodalom

További olvasnivalók