Průměrná složitost algoritmu

V teorii výpočetní složitosti je průměrná složitost algoritmu  množstvím některých výpočetních zdrojů (obvykle času) potřebných k tomu, aby algoritmus fungoval, zprůměrované přes všechny možné vstupy. Tento koncept je často v kontrastu se složitostí nejhoršího případu , kde je uvažována maximální složitost algoritmu přes všechny vstupy.

Existují tři hlavní důvody pro studium složitosti v průměru [1] . Za prvé, zatímco některé problémy může být v nejhorším případě obtížné vyřešit, vstupy, které k tomuto chování vedou, jsou v praxi vzácné, takže průměrná složitost může být přesnějším měřítkem výkonu algoritmu. Za druhé, analýza složitosti v průměru poskytuje prostředky a techniku ​​pro generování komplexních dat pro problém, které lze použít v kryptografii a derandomizaci . Za třetí, složitost v průměru umožňuje vybrat v praxi nejúčinnější algoritmus mezi algoritmy stejné základní složitosti (jako je quicksort ).

Analýza algoritmů v průměru vyžaduje pojem "průměrná" data algoritmu, což vede k problému promýšlení rozdělení pravděpodobnosti vstupních dat. Lze také použít pravděpodobnostní algoritmus . Analýza takových algoritmů vede k související představě očekávané složitosti [2] .

Historie a pozadí

Průměrný výkon algoritmů byl studován od zavedení moderních představ o výpočetní efektivitě v 50. letech 20. století. Většina počátečních prací se soustředila na problémy, pro které byly známy polynomiální časové algoritmy pro nejhorší případy [3] . V roce 1973 Donald Knuth [4] publikoval třetí díl The Art of Computer Programming , ve kterém podal široký přehled výkonnosti v průměru algoritmů pro problémy, které lze v nejhorším případě vyřešit v polynomiálním čase, jako je třídění a výpočet mediánu .

Efektivní algoritmus pro NP-úplné problémy obecně předpokládá, že běží v polynomiálním čase pro všechny vstupy, což je ekvivalent nejhoršího případu složitosti. Algoritmus, který je neefektivní na „malém“ množství dat, však může být docela účinný na „většinu“ dat, se kterými se v praxi setkáváme. Je tedy žádoucí studovat vlastnosti algoritmů, jejichž průměrná složitost se může výrazně lišit od složitosti v nejhorším případě.

Základní koncepty průměrné složitosti byly vyvinuty Levinem, Leonidem Anatolyevičem , který v roce 1986 publikoval jednostránkový článek [5] , ve kterém definoval průměrnou složitost a úplnost a poskytl příklad úplného problému třídy distNP, analogu NP-úplnosti pro průměrnou složitost.

Definice

Průměrně efektivní algoritmus

Prvním cílem je přesně definovat, co znamená, že algoritmus je efektivní „v průměru“. Lze se pokusit definovat průměrně účinný algoritmus jako algoritmus, jehož očekávaná hodnota je polynomiální pro všechny možné vstupy. Tato definice má různé nevýhody. Zejména tato definice není stabilní s ohledem na změny ve výpočetním modelu (například při výměně vícepáskového Turingova stroje za jednopáskový). Nechť například Algoritmus A běží v čase t A (x) na vstupu x a Algoritmus B běží v čase t A (x) 2 na vstupu x. To znamená, že B je kvadraticky pomalejší než A. Je intuitivně jasné, že jakákoli definice průměrné účinnosti musí používat myšlenku, že A je průměrně účinná právě tehdy, když B je průměrně účinná. Předpokládejme však, že vstup je převzat náhodně z rovnoměrně rozložených řetězců délky n a že A běží v čase n 2 na všech vstupech kromě řetězce 1 n , který trvá čas 2 n . Je snadné tuto podložku zkontrolovat. očekávaná doba běhu algoritmu A je polynomiální, ale mat. očekávání algoritmu B je exponenciální [3] .

Chcete-li vytvořit silnější definici průměrné účinnosti, dává smysl nechat A běžet za více než polynomiální čas na některých vstupech, ale zlomek dat, na kterém A zabírá stále více času, bude stále menší a menší. Tato myšlenka je zachycena v následujícím vzorci pro průměrnou dobu trvání polynomu, ve které jsou doba trvání a vstupní zlomek vyváženy:

pro libovolné n, t, ε > 0 a polynom p, kde t A (x) znamená dobu běhu algoritmu A na vstupu x [6] . Případně to lze napsat následovně

pro nějakou konstantu C, kde n = |x| [7] . Jinými slovy, algoritmus A má dobrou průměrnou složitost, pokud po t A (n) kroky A mohou vyřešit všechny problémy, kromě zlomku problémů se vstupní délkou n, pro některé ε, c > 0 [3] .

Problémy se známými distribucemi

Dalším krokem je určení „průměrného“ vstupu pro konkrétní úlohu. Toho je dosaženo spojením vstupu každé úlohy s určitým rozdělením pravděpodobnosti. To znamená, že „průměrný“ problém se skládá z jazyka L (tedy množiny slov reprezentujících vstupní data) a distribuce D s ním spojené, výsledkem je dvojice (L, D) (problém se známými distribucemi) [7] . Dvě nejběžnější třídy rozdělení pravděpodobnosti jsou:

  1. Polynomiálně-časově vyčíslitelná (P-vypočítatelná) distribuce jsou distribuce, pro které lze vypočítat hustotu součtu libovolného daného vstupu x. Formálně, za předpokladu rozdělení μ a řádku x ∈ {0, 1} n , lze vypočítat hodnotu v polynomiálním čase. Z toho vyplývá, že Pr[x] je také vypočitatelný v polynomiálním čase.
  2. Polynomiálně-časově sestavitelná (P-konstruktivní) distribuce jsou distribuce, která lze náhodně vybrat v polynomiálním čase.

Tyto dva pojmy nejsou ekvivalentní, i když jsou podobné. Je-li rozdělení P-vypočitatelné, je také P-konstruktivní, ale obráceně to neplatí, pokud P ≠ P #P [7] .

AvgP a distNP

Problém se známými distribucemi (L, D) patří do třídy složitosti AvgP, pokud existuje průměrně účinný algoritmus pro L, jak je definováno výše. Třída AvgP je někdy v literatuře označována jako distP [7] .

Problém se známými distribucemi (L, D) patří do třídy složitosti distNP, pokud L patří do NP a D je P-vypočítatelné. Jestliže L patří do NP a D je P-konstruovatelné, pak (L, D) patří do sampNP [7] .

Dvě třídy, AvgP a distNP, definují analogii P a NP s průměrnou složitostí [7] .

Redukovatelnost problémů se známými distribucemi

Nechť (L,D) a (L',D') jsou dva problémy se známými rozděleními. (L, D) redukuje v průměru na (L', D') (psáno (L, D) ≤ AvgP (L', D')), pokud existuje funkce f taková, že pro libovolné n ji lze vypočítat na vstup x v polynomiálním čase v n a

  1. (Správnost) x ∈ L právě tehdy, když f(x) ∈ L'
  2. (Dominance) Existují polynomy p a m takové, že pro libovolné n a y,

Podmínka dominance vede k myšlence, že pokud je problém (L, D) v průměru těžký, pak (L', D') je v průměru také těžký. Intuitivně by redukce měla poskytnout způsob, jak vyřešit problém L pro vstup x pomocí výpočtu f(x) a přivést výstup algoritmu do algoritmu, který řeší L'. Bez podmínky dominance to nemusí být možné, protože algoritmus, který řeší L v průměru v polynomiálním čase, může běžet v superpolynomiálním čase pro malý počet vstupů, ale tyto vstupy mohou být mapovány na velkou množinu v D', takže Algoritmus A' v polynomiálním čase v průměrném čase nebude fungovat. Podmínka dominance specifikuje, že takové řady se budou vyskytovat v D' polynomiálně často [6] .

Úlohy DistNP-complete

Analogií střední složitosti pro NP-komplexitu je distNP-úplnost. Problém se známými distribucemi (L', D') je distNP-úplný, pokud (L', D') patří do distNP a jakékoli (L, D) v distNP (ve střední složitosti) je redukovatelné na (L', D' ) [7] .

Příkladem problému distNP-complete je omezený problém zastavení , BH, definovaný takto:

BH = {(M,x,1 t ) : M je nedeterministický Turingův stroj , který bere x v ≤ t krocích [7] .

Levin ve svém článku ukázal příklad problému s dlaždicemi, který je v průměru NP-úplný [5] . Přehled známých distNP-complete problémů lze nalézt ve Wangově knize [6] .

Probíhá aktivní výzkum při hledání nových distNP-úplných problémů. Nalezení takových problémů však může být obtížné kvůli Gurevichovu výsledku, který ukázal, že jakýkoli problém se známými distribucemi nemůže být distNP-úplný, pokud EXP = NEXP [8] . (Rovnoměrné rozdělení μ je jedním z rozdělení, pro které existuje ε > 0 takové, že pro libovolné x μ(x) ≤ 2 -|x| ε .) Livneův výsledek ukazuje, že všechny přirozené NP problémy mají DistNP-úplnou verzi [ 9] . Cíl najít přirozené distributivní problémy, které jsou úplné DistNP, však nebylo dosaženo [10] .

Aplikace

Algoritmy řazení

Jak bylo zmíněno výše, velká část raných prací o průměrné složitosti se soustředila na problémy, pro které byly známy polynomiální časové algoritmy, jako je třídění. Například mnoho třídicích algoritmů, jako je quicksort , má v nejhorším případě dobu běhu O(n 2 ), ale průměrnou dobu běhu O(nlog(n)), kde n je délka tříděných dat [ 11] .

Kryptografie

U většiny problémů byla provedena analýza průměrné složitosti, aby se našly účinné algoritmy pro problém, který je v nejhorším případě považován za složitý. V kryptografii je však opak pravdou – složitost je přinejhorším nedůležitá, místo toho chceme zaručit, že jakýkoli průměrně složitý algoritmus, který „rozbije“ kryptografické schéma, bude neefektivní [12] .

Všechna kryptografická schémata jsou tedy založena na existenci jednosměrných funkcí [3] . Ačkoli existence jednosměrných funkcí zůstává otevřeným problémem, mnoho kandidátů na jednosměrné funkce je založeno na obtížných problémech, jako je faktorizace celého čísla nebo výpočet diskrétního logaritmu . Všimněte si, že je nežádoucí, aby kandidátní funkce byla NP-úplná, protože to pouze zajišťuje, že neexistuje žádný účinný algoritmus pro složitost nejhoršího případu. Ve skutečnosti chceme zajistit, aby neexistoval žádný účinný algoritmus, který by řešil problém pro náhodné vstupy (to znamená v průměru ve složitosti). Ve skutečnosti jak problém faktorizace celých čísel, tak problém výpočtu diskrétního logaritmu patří k NP ∩ coNP , a proto se nevěří, že jsou NP-úplné [7] . Skutečnost, že veškerá kryptografie je založena na existenci problémů, které jsou v NP v průměru těžko řešitelné, je jedním z hlavních důvodů pro studium složitosti v průměru.

Další výsledky

V roce 1990 Impagliazzo a Levin ukázali, že pokud existuje průměrně účinný algoritmus pro distNP-úplný problém pod rovnoměrným rozdělením, pak existuje průměrně účinný algoritmus pro jakýkoli problém v NP pro jakékoli rozdělení konstruované v polynomiálním čase [13] . Otevřenou otázkou zůstává aplikace této teorie na problémy s přirozenými známými distribucemi [3] .

V roce 1992 Ben-David a kol. ukázali, že pokud všechny jazyky v distNP mají dobré průměrné rozhodovací algoritmy , mají dobré průměrné vyhledávací algoritmy. Navíc ukázali, že to platí za slabších předpokladů — pokud je nějaký jazyk v NP v průměru jednoduchý pro selekční algoritmy s rovnoměrným rozdělením, pak bude průměrně jednoduchý i pro vyhledávací algoritmy s rovnoměrným rozdělením [14] . Kryptografické jednosměrné funkce tedy mohou existovat pouze tehdy, pokud existují problémy z distNP nad rovnoměrným rozdělením, které jsou v průměru obtížné pro rozhodovací algoritmy .

V roce 1993 Feigenbaum a Fortnow ukázali, že je nemožné prokázat při neadaptivní náhodné redukci, že existence dobrého průměrného algoritmu pro distNP-úplný problém při rovnoměrném rozdělení implikuje existenci nejhoršího případu efektivního algoritmu v NP. [15] . V roce 2003 Bogdanov a Trevisan zobecnili tento výsledek na svévolné neadaptivní snížení [16] . Tento výsledek ukazuje, že pomocí redukce je stěží možné najít vztah mezi průměrnou složitostí a složitostí nejhoršího případu [3] .

Viz také

Poznámky

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

Literatura

Další čtení