Кіріспе

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

Анықтама

Егер f функциясы үшін кез келген x мысалын бағалау, f функциясын бір немесе бірнеше кездейсоқ yi мысалында бағалауға полиномдық уақыт ішінде келтірілсе, онда ол өзін-өзі келісімді етеді (бұл бейімделмейтін біртекті өзін-өзі келісімділік деп те аталады). Кездейсоқ өзін-өзі келісімділікте, f доменіндегі ең нашар жағдай мысалы x, y1, …, yk мысалдарының кездейсоқ жиынтығына шартты түрде бейнеленеді. Бұл f(x)-ті полиномдық уақыт ішінде есептеу үшін жасалады, бейнелеуден алынған монета лақтыру тізбегі, x және f(y1), …, f(yk) берілгенде. Сондықтан, yi-дегі индукцияланған үлестірімге қатысты орташа мәнді ескере отырып, f функциясының орташа күрделілігі, f функциясының ең нашар жағдайдағы кездейсоқ күрделілігімен (полиномдық факторлар шегінде) бірдей болады. Атап айтарлық бір ерекше жағдай – әрбір кездейсоқ мысал yi, f доменіндегі |x| ұзындығындағы элементтердің барлық жиыны бойынша біркелкі таратылған кезде. Бұл жағдайда f орташа есеп бойынша ең нашар жағдайдағыдай қиын. Бұл тәсілде екі негізгі шектеу бар. Біріншіден, y1, …, yk мысалдарының жасалуы бейімделмейтін түрде жүзеге асырылады. Яғни, y2, f(y1) белгілі болғанға дейін таңдалады. Екіншіден, y1, …, yk нүктелерінің біркелкі таралуы міндетті емес.

Криптографиялық протоколдарда қолдану

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

Мысалдар

Дискретті логарифм мәселесі, квадраттық қалдық мәселесі, RSA инверсия мәселесі және матрицаның тұрақтысын есептеу мәселесі – әрқайсысы кездейсоқ түрде өзін-өзі қысқартатын проблемалар.

Дискреттік логарифм

Теорема: |G| өлшемді циклдік топ G берілген. Егер детерминистік полиномиалдық уақыт алгоритмі A барлық кірістердің 1/poly(n) бөлігі үшін дискретті логарифмді есептейді (мұнда n = log |G| кіріс өлшемі болса), онда барлық кірістер үшін дискретті логарифмді есептейтін кездейсоқ полиномиалдық уақыт алгоритмі бар. G = { gi | 0 ≤ i < |G| } циклдік тобының генераторы g және x ∈ G берілген болса, x-тің g негізіндегі дискретті логарифмі – x = gk теңдігін қанағаттандыратын k бүтін саны (0 ≤ k < |G|). B-ны {0, 1, ..., |G| − 1} жиыны бойынша біркелкі таралған деп есептейік, онда xgB = gk+B да G бойынша біркелкі таралған болады. Сондықтан xgB, x-тен тәуелсіз, ал оның логарифмін полиномиалдық уақыт ішінде 1/poly(n) ықтималдығымен есептеуге болады. Онда logg x ≡ logg xgB (mod |G|) және дискретті логарифм өзін-өзі келеді.

Матрицаның тұрақтысы

Матрицаның тұрақтысының анықтамасын ескере отырып, кез келген n × n матрицасы үшін PERM(M) – M матрицасының элементтері бойынша n дәрежелі көпмөлделік болып табылады. Матрицаның тұрақтысын есептеу – қиын есептеу мәселесі, және PERM #P толық екені дәлелденген. Сонымен қатар, көптеген матрицалар үшін PERM(M) есептеу мүмкіндігі барлық матрицалар үшін PERM(M) есептейтін кездейсоқ бағдарламаның болуын білдіреді. Бұл PERM-нің кездейсоқ түрде өзін-өзі қысқартатынын көрсетеді. Төмендегі талқылауда матрица элементтері белгілі бір жай сан p үшін шекті өріс Fp-ден алынған және барлық арифметика сол өрісте орындалатын жағдай қарастырылады. X болсын – Fp-ден алынған элементтері бар кездейсоқ n × n матрица. Кез келген M + kX матрицасының барлық элементтері k-ның сызықтық функциялары болғандықтан, осы сызықтық функцияларды PERM(M) есептейтін n дәрежелі көпмөлделікпен біріктіру арқылы k бойынша тағы бір n дәрежелі көпмөлделік аламыз, оны p(k) деп атаймыз. Әрине, p(0) M матрицасының тұрақтысына тең.

Егер біз PERM(A) матрицасының дұрыс мәнін Fp-ден алынған элементтері бар көптеген n × n матрицалар үшін, атап айтқанда, олардың 1 – 1/(3n) бөлігі үшін есептей алатын бағдарлама бар десек, онда шамамен екі бөліктен бірінің ықтималдығымен k = 1, 2, ..., n + 1 үшін PERM(M + kX) есептей аламыз. Бізде n + 1 мән болғаннан кейін, p(k) көпмөлделігінің коэффициенттерін интерполяция арқылы анықтай аламыз (p(k) n дәрежелі екенін есімізде сақтаңыз). p(k) нақты анықталғаннан кейін, p(0) мәнін есептейміз, ол PERM(M) тең. Мұндай жағдайда, 1/3 қателік болуы мүмкін, бірақ бірнеше кездейсоқ X матрицаларын таңдап, жоғарыдағы процедураны көп рет қайталап, тек көпшілік дауысқа сәйкес келетін жауапты ұсынсақ, қателік деңгейін өте төмендетуге болады.

Салдарлар

Егер NP толық проблемасы бейімделусіз кездейсоқ өзін-өзі азайтуға болатын болса, полиномиялық иерархия Σ3-ке дейін құлайды. Егер CoNP қиын мәселесі O(log n/n) уақытында кездейсоқ өзін-өзі азайтуға болатын болса, онда Σ2 = Π2.