Сложеност просечног случаја

У теорији комплексности, сложеност просечног случаја одређеног алгоритма представља искоришћеност неког рачунарског ресурса (најчешће времена) у просеку за све могуће улазе. Често се супротставља сложености најгорег случаја која подразумева максималну сложеност алгоритма узимајући у обзир све могуће улазе.

Постоје три основне мотивације за проучавање сложености просечног случаја. Прво, иако неки проблеми могу бити сложени у најгорем случају, улази који изазивају овакво понашање се можда ретко јављају у пракси, тако да у том случају анализа просечне сложености може дати прецизније резултате приликом процене сложености алгоритма. Друго, анализа сложености просечног случаја обезбеђује алате и технике за генерисање примера проблема који се могу користити у областима као што су криптографија и дерандомизација (ен. derandomization). И трећа мотивација, сложеност просечног случаја омогућава разликовање најефикаснијег алгоритма у пракси међу алгоритмима са еквивалентно заснованом сложеношћу (нпр. квиксорт).

Анализа сложености просечног случаја захтева разумевање појма "просечног" улаза алгоритма, што доводи до проблема расподеле вероватноће над улазима. Алтернативно, може се користити рандомизовани алгоритам. Анализа таквих алгоритама доводи до сродног појма очекиване сложености.

Историја и позадина

Ефикасност алгоритама у просечном случају је почела да се изучава појавом савремених појмова ефикасности израчунавања који су развијени 1950—их година. Већи део овог иницијалног рада је био фокусиран на проблеме за које су већ били познати алгоритми са полиномијалном временском сложеношћу у најгорем случају. 1973. године, Доналд Кнут је објавио 3. том монографије Уметност рачунарског програмирања (енгл. The Art of Computer Programming) која опширно истражује ефикасност просечног случаја алгоритама за проблеме решиве у полиномијалном времену у најгорем случају (нпр. сортирање и тражење медијане).

Ефикасан алгоритам за NP-комплетне проблеме је окарактерисан као алгоритам који се извршава у полиномијалном времену за све улазе; то је еквивалентно захтеву за ефикасну сложеност у најгорем случају. Међутим, алгоритам који је неефикасан за мали број улаза и даље може бити ефикасан за већину улаза који се јављају у пракси. Према томе, пожељно је проучавати својства ових алгоритама где се просечна сложеност може разликовати од сложености најгорег случаја и пронаћи начин за налажење везе између њих.

Фундаменталне појмове сложености просечног случаја је 1986. године развио Леонид Левин када је објавио једнострани рад дефинисањем сложености просечног случаја и комплетности кроз пример за distNP.

Дефиниције

Ефикасност сложености просечног случаја

Први задатак је прецизно дефинисати шта се подразумева под алгоритмом чија је сложеност "у просеку". Иницијални покушај би био да покушамо да дефинишемо ефикасан алгоритам просечне сложености као алгоритам који се извршава у очекиваном полиномијалном времену за све могуће улазе. Оваква дефиниција има разне недостатке; специјално, није робусна променама у моделу израчунавања. На пример, претпоставимо да се алгоритам А извршава у времену t_A(x) за улаз x и алгоритам B се извршава у времену t_A(x)² за улаз x; тј, B је квадратно спорији од А. Интуитивно, било која дефиниција сложености просечног случаја би требало да обухвати идеју да је А ефикасан у просеку ако и само ако је B ефикасан у просеку. Претпоставимо, међутим, да су сви улази изведени насумично из униформне дистрибуције ниски дужине n, и да се А извршава у времену n² за све улазе изузев за стрингове 1ⁿ који захтевају 2ⁿ времена. Онда се лако може проверити да је очекивано време извршавања алгоритма А полиномијално, али очекивано време извршавања алгоритма B је експоненцијално. За креирање робусније дефиниције сложености просечног случаја, има смисла дозволити алгоритму А да се извршава дуже од полиномијалног времена за неке улазе, али да део улаза за које А захтева све веће и веће време извршавања постаје све мањи и мањи. Ова интуиција је обухваћена наредном формулом за просечно полиномијално време извршавања, која балансира полиномијални компромис између времена извршавања и дела улаза:

$\Pr _{x\in _{R}D_{n}}[t_{A}(x)\geq t]\leq {\frac {p(n)}{t^{\epsilon }}}$

за свако n, t, ε > 0 и полином p, где t_A(x) означава време извршавања алгоритма А за улаз x. Алтернативно, ово може бити записано као

$E_{x\in _{R}D_{n}}[{\frac {t_{A}(x)^{\epsilon }}{n}}]\leq C$

за неку константу C, где је n = |x|. Другачије речено, алгоритам А има има добру сложеност просечног случаја ако, након покретања за t_A(n) корака, А може да реши све осим ${\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}$ делова улаза дужине n, за неке ε, c > 0.

Проблем расподеле

Следећи корак је дефинисање просечног улаза за одређени проблем. Ово се постиже удруживањем улаза сваког проблема са конкретном расподелом вероватноће. Проблем просечног случаја се састоји од језика L и придружене расподеле вероватноће D која формира пар (L, D). Две најчешће класе расподеле које су дозвољене су:

1. Полиномијално израчунљиве расподеле (П-израчунљиве): ово су расподеле за које је могуће израчунати кумулативну густину за било који улаз x. Формалније, за дату расподелу вероватноће μ и ниску x ∈ {0, 1}ⁿ могуће је израчунати све могуће вредности $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ у полиномијалном времену. Ово подразумева да је Pr[x] такође израчунљив у полиномијалном времену.
2. Полиномијално узорковане расподеле (П-узорковане): ово су расподеле из којих је могуће извући насумичне узорке у полиномијалном времену.

Ове две формулације, иако су сличне, нису еквивалентне. Ако је расподела П-израчунљива она је такође и П-узоркована, али обрнуто није тачно ако P ≠ P^#P.

AvgP и distNP

Проблем расподеле (L, D) је у класи сложености AvgP ако постоји ефикасни алгоритам просечне сложености за L, као што је дефинисано горе. Класа AvgP се у литератури понекад назива distP.

Проблем расподеле (L, D) је у класи сложености distNP ако је L у NP и ако је D П-израчунљива. Када је L у NP и D је П-узоркована, (L, D) припада sampNP.

Заједно, AvgP и distNP дефинишу аналогије просечног случаја од P и NP.

Редукције између проблема расподеле

Нека су (L,D) и (L',D') два проблема расподеле. Просечан случај (L, D) се редукује на (L', D') (пише се (L, D) ≤_AvgP (L', D')) ако постоји функција f која за свако n, за улаз x може бити израчуната у полиномијалном времену од n и

1. (Исправност) x ∈ L ако и само ако f(x) ∈ L'
2. (Доминација) Постоје полиноми p and m такви да, ѕа свако n и y, $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

Услов доминације намеће идеју да ако је проблем (L, D) тежак у просеку, онда је и (L', D') такође тежак у просеку. Интуитивно, редукција би требало да обезбеди начин решавања инстанце x проблема L израчунавањем f(x) и прослеђивањем излаза алгоритму који решава L'. Без овог услова, ово можда не би било могуће пошто алгоритам који решава L у полиномијалном времену у просеку може трајати у времену које није полиномијално за мали број улаза, али f можда пресликава ове улазе у много већи скуп D', па се онда алгоритам A' више не извршава у полиномијалном времену у просеку.

DistNP-комплетни проблеми

Аналогија просечне сложености NP-комплетности је distNP-комплетност. Проблем расподеле (L', D') је distNP-комплетан ако је (L', D') у distNP и за сваку (L, D) у distNP, (L, D) је сводљива на (L', D').

Пример distNP-комплетног проблема је ограничени Халтинг проблем, BH, дефинисан као:

BH = {(M,x,1^t) : M је недетерминистичка Тјурингова машина која прихвата x у ≤ t корака.}

У његовом оригиналном раду, Левин приказује пример дистрибутивног поплочавања који је NP-комплетан. Истраживања познатих distNP-комплетних проблема су доступна на Вебу.

Једна област активног истраживања укључује проналажење нових distNP-комплетних проблема. Међутим, проналажење таквих проблема може бити компликовано због резултата Гуревича који показују да било који проблем расподеле са плитком расподелом не може бити distNP-комплетан осим уколико не важи EXP = NEXP. (Плитка расподела μ је расподела за коју важи да је ε > 0 за свако x, μ(x) ≤ 2^-|x|ε.) Ливнови резултати показују да сви природни NP проблеми имају DistNP-комплетне верзије. Међутим, циљ проналажења природних проблема расподеле који су DistNP-комплетни и даље није постигнут.

Примене

Алгоритми сортирања

Као што је већ речено, много раних радова се односи на сложеност просечног случаја за проблеме за које алгоритми са полиномијалном сложеношћу већ постоје (нпр. сортирање). На пример, многи алгоритми сортирања који користе случајност (нпр. квиксорт), у најгорем случају имају сложеност O(n²), али у просечном случају време извршавања је O(nlog(n)), где n представља величину улаза који се сортира.

Криптографија

За многе проблеме, анализа сложености просечног случаја се врши како би се пронашли ефикасни алгоритми за проблеме за које се сматра да су тешки у најгорем случају. Код примена у криптографији, међутим, важи обрнуто: сложеност најгорег случаја је ирелевантна; уместо тога желимо да гарантујемо да је сложеност просечног случаја за сваки алгоритам који разбија енкрипцију неефикасан.

Према томе, све енкрипције се заснивају на постојању такозваних one-way функција (функције које се лако израчунавају у једном смеру, али у супротном смеру не). Иако је постојање one-way функција и даље отворен проблем, многи кандидати one-way функција су базирани на NP-тешким проблемима као што су факторизација целих бројева или прорачунавање дискретног логаритма. Потребно је нагласити да није пожељно да функција кандидат буде NP-комплетна зато што то гарантује само да највероватније не постоји ефикасан алгоритам за решавање проблема у најгорем случају; оно што ми заправо желимо је да гарантујемо да не постоји ефикасан алгоритам који решава проблем за случајне улазе. Заправо, и факторизација бројева и дискретни логаритам су у NP ∩ coNP и због тога се не верује да су NP-комплетни. Чињеница да је цела криптографија заснована на постојању сложености просечних случајева сложених проблема у NP је једна од главних мотивација за изучавање просечне сложености.

Други резултати

1990-их, Impagliazzo и Левин показују да ако постоји ефикасан алгоритам у просечном случају за distNP-комплетан проблем према униформној расподели, онда постоји алгоритам у просечном случају за сваки проблем у NP према било којој полиномијално узоркованој расподели. Примене ове теорије за природне расподеле и даље остају као отворено питање.

1992., Ben-David et al., показују да ако сви језици у distNP имају у просеку добре алгоритме одлучивања, они такође у просеку имају и добре алгоритме за претрагу. Додатно, они показују да овај закључак важи и под слабијом претпоставком: ако је сваки језик у NP у просеку лак за алгоритме одлучивања у погледу уноформне расподеле, онда је он такође лак у просеку и за алгоритме за претрагу у погледу униформне расподеле. Према томе, криптографичке one-way функције могу да постоје само ако постоје distNP проблеми у погледу униформне расподеле који су тешки у просеку за алгоритме одлучивања.

1993., Feigenbaum и Fortnow показују да није могуће доказати, под неприлагодљивим случајним редукцијама, да постојање у просеку доброг алгоритма за distNP-комплетан проблем према униформној расподели имплицира постојање ефикасног алгоритма у најгорем случају за све проблеме у NP. 2003., Bogdanov и Trevisan генерализују овај резултат за произвољне неприлагодљиве редукције. Ови резултати показују да вероватно није могуће пронаћи везу између сложености просечног случаја и сложености најгорег случаја преко редукција.

Види још

• Анализа алгоритама
• НП-комплетни проблеми

Литература

• J. Katz; Y. Lindell (2007). Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series). Chapman and Hall/CRC.