Алгоритмнің орташа есеппен күрделілігі

Есептеу күрделілігі теориясында алгоритмнің орташа есеппен күрделілігі – бұл алгоритмді басқаруға қажетті белгілі бір есептеу ресурстарының (әдетте уақыт), барлық мүмкін болатын кіріс деректері бойынша орташаланған мөлшері. Тұжырымдама жиі нашар жағдайларда күрделілігі қарама-қарсы қойылады, мұнда барлық кірістер бойынша алгоритмнің максималды күрделілігі қарастырылады.

Орташа есеппен күрделілікті зерттеудің үш негізгі себебі бар . Біріншіден, ең нашар жағдайда кейбір мәселелерді шешу қиын болуы мүмкін, осындай беталысқа әкелетін кіріс мәліметтер іс жүзінде сирек кездеседі, сондықтан орташа есеппен күрделілігі алгоритм өнімділігінің дәлірек өлшемі болуы мүмкін. Екіншіден, орташа есеппен күрделілігі криптография мен дерандомизациялау қолдануға болатын қарастырылатын мәселе үшін күрделі деректерді генерациялау құралдары мен әдістемесін қамтамасыз етеді. Үшіншіден, орташа есеппен күрделілік бірдей негізгі күрделіліктегі (мысалы, жылдам сұрыптау ) алгоритмдер арасында тәжірибедегі ең тиімді алгоритмді анықтауға мүмкіндік береді.

Алгоритмдерді орташа есеппен талдау алгоритмнің "орташа" деректері ұғымын қажет етеді, бұл кіріс деректерінің, ықтималдығын үлестірілу туралы ойлауға әкеледі. Ықтималдық алгоритмін де қолдануға болады. Мұндай алгоритмдерді талдау күтілетін күрделілікті байланысты тұжырымдамасына әкеледі.

Тарих және негіздеме

Орташа есеппен алгоритмдердің өнімділігі 1950 жылдары есептеу тиімділігінің заманауи ұғымдарын енгізгеннен кейін зерттелді. Бастапқы жұмыстардың көпшілігі полиномиалды ең нашар жағдайда уақыты алгоритмдер үшін белгілі болған есептерге назар аударды . 1973 жылы Дональд Кнут «Бағдарламалау өнерінің» үшінші томын шығарды, онда ол сұрыптау және медиананы есептеу сияқты ең нашар жағдайда полиномиалды уақытта шешілетін есептер үшін орташа алгоритмдердің өнімділігіне кең шолу жасады.

NP-толық есептердің тиімді алгоритмі жалпы жағдайда барлық кірістер үшін полиномиалды уақытта жұмыс істейді деп болжайды, бұл ең нашар жағдайда күрделілікке тең. Дегенмен, деректердің "аз" санында тиімсіз алгоритм іс жүзінде кездесетін деректердің "көпшілігі" үшін жеткілікті тиімді болуы мүмкін. Осылайша, алгоритмдердің қасиеттерін зерттеген жөн, олар үшін орташа күрделілігі есеппен ең нашар жағдайда күрделіліктен айтарлықтай өзгеше болуы мүмкін.

Орташа есеппен күрделіліктің іргелі тұжырымдамаларын Левин, Леонид Анатольевич әзірледі, ол 1986 жылы бір беттік мақала жариялады , онда ол орташа есеппен күрделілікті және толықтылық бойынша анықтап, distNP класының толық мәселесінің мысалын келтірді, орташа есеппен күрделілік бойынша NP-толықтығының аналогы.

Белгілі үлестірімдері бар тапсырмалардың жинақталуы

Орташа есеппен тиімді алгоритм

Бірінші мақсат – алгоритм «орташа есеппен» тиімді дегенді дәл анықтау. Орташа есеппен тиімді алгоритм ретінде барлық мүмкін кірістер үшін математикалық күтуі полиномиалды болып табылатын алгоритм деп анықтауға болады. Бұл анықтаманың әртүрлі кемшіліктері бар. Атап айтқанда, бұл анықтама есептеу моделіндегі өзгерістерге қатысты тұрақты емес (мысалы, көп таспалы Тьюринг машинасын бір таспалы машинасына ауыстыру кезінде). Мысалы, А алгоритмі х кірісінде t _A (x) уақытында, ал B алгоритмі х кірісінде t _A (x) ² уақытында орындалсын. Яғни В А-ға қарағанда квадраттық баяу. Интуитивті түрде, орташа есеппен тиімділіктің кез-келген анықтамасы А орташа есеппен в орташа есеппен тиімді болған кезде ғана тиімді деген идеяны қолдануы керек. Дегенмен, кірістер ұзындығы n біркелкі бөлінген жолдан кездейсоқ алынғанын және A 1 ⁿ жолынан басқа барлық кірістерде n ² уақытында жұмыс істейді делік, бұл 2 ⁿ уақытты алады. А алгоритмінің жұмыс уақытын математикалық күту полиноминалды екенін тексеру оңай, бірақ В алгоритмінің жұмысын математикалық күту экспоненциалды .

Орташа есеппен тиімділіктің неғұрлым берік анықтамасын жасау үшін А алгоритмінің кейбір кірістерде полиноминалды уақыттан артық жұмыс істеуіне мүмкіндік беру мағынасы бар, бірақ А көп уақытты қажет ететін деректердің үлесі азаяды. Бұл идея жұмыс уақыты мен кіріс үлесі теңдестірілген орташа полиноминалды жұмыс уақыты үшін келесі формулада жазылған:

$\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 кірісіндегі A алгоритмінің орындалу уақытын білдіреді . Немесе оны келесідей жазуға болады

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

кейбір тұрақты С үшін, мұндағы n = |x| . Басқаша айтқанда, A алгоритмінің орташа күрделілігі жақсы, егер t _A (n) қадамнан кейін А қадамдарынан басқа барлық есептерді шеше алатын болса. ${\frac {n^{c}}{(t_{A}(n))^{\epsilon }}}$ кіріс ұзындығы n, кейбір ε үшін c > 0 болатын тапсырмалардың үлесі . Белгілі үлестірімдерге қатысты мәселелер

Белгілі үлестірімдерге қатысты мәселелер

Келесі қадам белгілі бір тапсырма үшін «орташа» кірісті анықтау болып табылады. Бұған әрбір тапсырманың кірісін белгілі бір ықтималдық үлестіріміне салыстыру арқылы қол жеткізіледі. Яғни, «орташа» есеп L тілінен (яғни кіріс деректерін білдіретін сөздер жиынынан) және байланысты D таралудан тұрады, нәтижесінде жұп (L, D) (белгілі үлестірімдері бар есеп) шығады . Ықтималдық үлестірімінің ең көп тараған екі класы:

1. Полиномиалды уақытта есептелетін үлестірімдер (P-есептелетін) кез келген берілген x кірісінің жиынтық тығыздығын есептеуге болатын үлестірімдер. Ресми түрде μ үлестірімі мен x ∈ {0, 1} ⁿ жолын ескере отырып, мәнді есептеуге болады $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$ полиномиалды уақытта. Бұдан шығатыны, Pr[x] да полиномиалды уақытта есептелетін болады.
2. Полиномиалды уақыта (P-құрастырылмалы) құрастырылмалы үлестірімдер деп полиномдық уақытта кездейсоқ іріктеу таңдауға болатын үлестірімдер болып табылады.

Бұл екі ұғым ұқсас болғанымен, баламасы емес. Егер үлестірім P-есептелетін болса, ол да P-құрастырылмалы, бірақ егер P ≠ P ^#P болса, керісінше жағдай дұрыс емес.

AvgP және distNP

Белгілі үлестірімдері бар есепте (L, D) жоғарыда анықталғандай L үшін орташа есеппен тиімді алгоритм болса, AvgP күрделілік сыныбына жатады. AvgP класы кейде әдебиетте distP деп аталады .

Белгілі үлестірімдері бар есептер (L, D) distNP күрделілік класына жатады, егер L NP-ге жатады және D P-есептелетін болса. Егер L NP-ге тиесілі болса және D P- құрастырылмалы болса, (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. (Үстемдік) Кез келген n және y үшін p және m көпмүшелері бар, $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

Үстемдік шарты, егер мәселе (L, D) орташа есеппен қиын болса, онда (L', D') да орташа есеппен қиын деген ойға әкеледі. Интуитивті түрде қысқарту f(x) есептеу арқылы x кірісіне арналған L есебін шешу жолын қамтамасыз етуі және алгоритмнің шығысын L' шешетін алгоритмге беруі керек. Үстемдік шартынсыз бұл мүмкін болмауы мүмкін, өйткені L мәнін полномиалды уақытта шешетін алгоритм кірістердің аз саны үшін суперполиномиялық уақытта жұмыс істей алады, бірақ бұл кірістер D'-дегі үлкен жиынмен салыстырылуы мүмкін, осылайша алгоритм орташа есеппен уақытта полиномдық уақытта A' алгоритм жұмыс істемейді. Үстемдік шарты мұндай жолдардың D' ішінде полномиалды жиі кездесетінін анықтайды.

DistNP-толық есепетер

NP-күрделілігі үшін орташа есеппен күрделілікұқсастық distNP-толықтығы болып табылады. Белгілі үлестірімдері бар мәселе (L', D') distNP-толық болып табылады, егер (L', D') distNP-ге тиесілі болса және кез келген (L, D) distNP-дегі (орташа есеппен күрделілікте) (L', D') -ге дейін қысқартылатын болады .

DistNP-толық есептің мысалы ретінде шектелген тоқтату мәселесі, BH болып табылады, төмендегідей анықталған:

BH = {(M,x,1 ^t ) : M – детерминирленген емес Тьюринг машинасы, ол x-ті ≤ t қадаммен қабылдайды .

Левин өз жұмысында орташа есеппен NP-толық болатын плиткаларды төсеу мәселесінің мысалын көрсетті . Танымал distNP-толық есептерді шолуды Ванг кітабынан табуға болады .

Жаңа distNP-толық есептерді іздеуде белсенді зерттеулер жүргізілуде. Дегенмен, мұндай есептерді табу Гуревичтің нәтижесіне байланысты қиын болуы мүмкін, ол белгілі үлестірімдері бар кез келген есеп EXP = NEXP болмаса, distNP-толық бола алмайтындығын көрсетті. (Біркелкі үлестірім μ кез келген x μ(x) ≤ 2 ^{-|x| ε} болатындай ε > 0 болатын үлестірімдердің бірі. ) Ливненің нәтижесі барлық табиғи NP есептерінің DistNP-толық нұсқасы бар екенін көрсетеді . Дегенмен, DistNP-толық болып табылатын табиғи таралу есептерін табу мақсатына қол жеткізілмеді .

Қолдану

Сұрыптау алгоритмдері

Жоғарыда айтылғандай, орташа есеппен күрделілігі бойынша көптеген ерте жұмыстар полиномиалды уақыт алгоритмдері белгілі болған мәселелерге назар аударды, оның ішінде сұрыптау. Мысалы, жылдам сұрыптау сияқты көптеген сұрыптау алгоритмдерінің ең нашар жұмыс уақыты O( ⁿ² ), бірақ орташаша есеппен жұмыс уақыты O(nlog(n)), мұндағы n сұрыпталатын деректердің ұзындығы .

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

Көптеген есепер үшін ең нашар жағдайда қиын деп саналатын есеп үшін тиімді алгоритмдерді табу үшін орташа есеппен күрделілік талдауы жасалды. Алайда криптографияда керісінше —күрделілік ең нашар жағдайда маңызды емес, біз оның орнына криптографиялық схеманы "бұзатын" кез-келген күрделі орташа есеппен алгоритмнің тиімсіз екендігіне кепілдік бергіміз келеді. .

Осылайша, барлық криптографиялық схемалар бір жақты функциялардың болуына негізделген . Бір жақты функциялардың болуы ашық мәселе болып қала бергенімен, көптеген бір жақты функция үміткерлері бүтін сандарды факторинг немесе дискретті логарифмді есептер сияқты қиын есептерге негізделген. Функция-үміткердің NP-толық болуы қажет емес екенін ескеріңіз, өйткені бұл ең нашар жағдайда күрделіліктің тиімді алгоритмі жоқ екеніне кепілдік береді. Шындығында, біз кездейсоқ кірістер үшін есепті шешетін тиімді алгоритм жоқ екеніне кепілдік бергіміз келеді (яғни орташа есеппен күрделілік бойынша)..Шын мәнінде, бүтін сандарды көбейткіштерге жіктеу, дискретті логарифмді есептеу  де NP ∩ coNP -ге жатады, сондықтан оларды NP-толық екеніне сенімділік жоқ . Барлық криптографияның NP-де орташа есеппен шешілмейтін есептердің болуына негізделуі орташа есеппен күрделілікті зерттеудің негізгі себептерінің бірі болып табылады.

Басқа нәтижелері

1990 жылы Импаглиаццо мен Левин егер distNP-үшін тиімді орташа алгоритм болса-біркелкі үлестіру кезінде толық тапсырма болса, онда NP-дегі кез-келген тапсырма үшін көпмүшелік уақытта жасалған кез-келген үлестіру кезінде тиімді орташа алгоритм бар екенін көрсетті. Бұл теорияны табиғи белгілі үлестірімдері бар мәселелерге қолдану ашық сұрақ болып қала береді.

1992 жылы Бен-Дэвид және т.б. егер distNP-дегі барлық тілдерде жақсы шешім қабылдау, алгоритмдері болса, оларда жақсы іздеу алгоритмдері бар екенін көрсетті. Сонымен қатар, олар мұны әлсіз болжамдармен орындайтынын көрсетті -егер NP-дегі кез-келген тіл біркелкі үлестіруді таңдау алгоритмдері үшін орташа есеппен қарапайым болса, онда ол біркелкі үлестіруді іздеу алгоритмдері үшін орташа есеппен қарапайым болады . Осылайша, криптографиялық біржақты функциялар тек шешім қабылдау алгоритмдері үшін орташа есеппен қиын болатын біркелкі үлестіруден жоғары distNP есептері болған жағдайда ғана өмір сүре алады.

1993 жылы Файгенбаум мен Фортноу бейімделмеген кездейсоқ редукция кезінде distNP-толық есептер үшін орташа есеппен жақсы алгоритмнің бар екендігін дәлелдеу мүмкін көрсетті. 2003 жылы Богданов пен Тревисан бұл нәтижені ерікті бейімделмеген редукцияға қорытындылады . Бұл нәтиже редукция арқылы орташа есеппен күрделілік және ең нашар жағдайда күрделілік арасындағы байланысты табу екіталай екенін көрсетеді.