Диссертация (1103424), страница 4
Текст из файла (страница 4)
Êàê òîëüêî Àðòóð áðîñèë ìîíåòêó ñòîëüêî ðàç, ñêîëüêî åìó íóæíî, Ìåðëèí ìàãè÷åñêèì îáðàçîì óçíà¼ò ðåçóëüòàòûáðîñêîâ è ìîæåò âûáðàòü q . Ýòî ñîîòâåòñòâóåò çàïèñè W (p, y, r): íåäåòåðìèíèðîâàííûé ñïîñîá îïèñàíèÿ ïîëó÷àåò r â êà÷åñòâå àðãóìåíòà, ïîýòîìóñåðòèôèêàò q ìîæåò çàâèñåòü îò r. Íóæíî, ÷òîáû óñëîâèå W (p, y, r) = xáûëî âûïîëíåíî ñ âåðîÿòíîñòüþ õîòÿ áû 32 , ò.å.
íå âûïîëíåíî ñ âåðîÿòíîñòüþ íå áîëüøå 31 . Ýòî çíà÷èò, ÷òî Ìåðëèí ìîæåò îáìàíóòü Àðòóðà (ò.å.ìîæåò êàêèì-òî ñîîáùåíèåì çàñòàâèòü åãî ïîðîäèòü ñëîâî, îòëè÷íîå îò x)èëè íå ìîæåò óáåäèòü Àðòóðà (ò.å. íèêàêèì ñîîáùåíèåì íå ìîæåò çàñòàâèòü ïîðîäèòü ñëîâî x) ñ ñóììàðíîé âåðîÿòíîñòüþ íå áîëüøå 31 .Äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû ïîÿâëÿåòñÿ íåýêâèâàëåíòíîå(äëÿ äåòåðìèíèðîâàííûõ ìàøèí) èñõîäíîìó ïîíÿòèå ñëîæíîñòè ðàçëè÷åíèÿ. Âìåñòî ñïîñîáîâ îïèñàíèÿ ìû áóäåì ãîâîðèòü î ðàçðåøàþùèõ àëãîðèòìàõ, ò.å.
ìàøèíàõ, âîçâðàùàþùèõ 0 èëè 1.Îïðåäåëåíèå 2.9 ( [43]). Óñëîâíîé ñëîæíîñòüþ ðàçëè÷åíèÿ CDs,tV (x|y)íàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òî V (p, x, y) = 1 èV (p, z, y) = 0 ïðè z 6= x, ïðè ýòîì ïðè âñåõ z ïðîãðàììà V (p, z, y) ðàáîòàåò âðåìÿ t è èñïîëüçóåò ïàìÿòü s.Àíàëîãè÷íî ïðåäûäóùåìó îïðåäåëÿåòñÿ áåçóñëîâíàÿ ñëîæíîñòü ðàçëè÷åíèÿ.
Òàêæå âåðíà òåîðåìà îá îïòèìàëüíîì ðàçðåøàþùåì àëãîðèòìå, àíàëîãè÷íàÿ òåîðåìå 2.5, ïîýòîìó â äàëüíåéøåì ìû áóäåì îïóñêàòü èíäåêñ, ñîîòâåòñòâóþùèé ðàçðåøàþùåìó àëãîðèòìó. Ìîæíî äàòü îïðåäåëåíèÿ ñëîæíîñòåé ðàçëè÷åíèÿ äëÿ äðóãèõ âû÷èñëèòåëüíûõ ìîäåëåé, íî â íàøåé ðàáîòå îíè íå ïîíàäîáÿòñÿ (à äëÿ íåäåòåðìèíèðîâàííûõ âû÷èñëåíèé îíè áóäóòýêâèâàëåíòíû îáû÷íîé ñëîæíîñòè).17ßñíî, ÷òî ñëîæíîñòü ðàçëè÷åíèÿ íå áîëüøå ñëîæíîñòè ïîðîæäåíèÿ: åñëèìàøèíà ìîæåò ïîðîäèòü íóæíîå ñëîâî, òî îíà ìîæåò è ïðîâåðèòü, îíî ëèïîñòóïèëî íà âõîä.Íàì òàêæå ïîòðåáóåòñÿ ñëîæíîñòü ðàçëè÷åíèÿ ñ îðàêóëîì:Îïðåäåëåíèå 2.10. Óñëîâíîé ñëîæíîñòüþ ðàçëè÷åíèÿ CDs,t,A(x|y) ñ îðàVêóëîì A íàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òî V A (p, x, y) = 1è V A (p, z, y) = 0 ïðè z 6= x.
Çäåñü ïðîãðàììà V ìîæåò äåëàòü çàïðîñûê îðàêóëó A, ò.å. çà îäèí øàã âûÿñíÿòü ïðî ëþáîå ñëîâî, ëåæèò ëè îíî âìíîæåñòâå A, ïðè ýòîì V ðàáîòàåò íå äîëüøå t øàãîâ è çàíèìàåò ïàìÿòüíå áîëüøå s.Èìååò ìåñòî ñëåäóþùàÿ âåðõíÿÿ îöåíêà èç [13] (ïîõîæàÿ ëåììà âñòðå÷àëàñü â ðàáîòå Ñèïñåðà [43]) íà CDA :Òåîðåìà 2.11 ( [13]). Ïóñòü A ⊂ {0, 1}∗ . Ââåä¼ì îáîçíà÷åíèå A=n =A ∩ {0, 1}n . Òîãäà äëÿ íåêîòîðûõ ïîëèíîìîâ t(n) è s(n) ïðè âñåõ x ∈ A=n=nâûïîëíåíî CDs(n),t(n),A (x) 6 2 log |A=n | + O(log n). Áîëåå òîãî, ñîîòâåòñòâóþùàÿ ïðîãðàììà îáðàùàåòñÿ ê îðàêóëó òîëüêî îäèí ðàç è çàäà¼òâîïðîñ îòíîñèòåëüíî ñâîåãî âõîäà.Íàì ïîíàäîáèòñÿ ñëåäóþùåå ñëåäñòâèå:Ñëåäñòâèå 2.12.
Äëÿ íåêîòîðûõ ïîëèíîìîâ t(n) è s(n) ïðè âñåõ A ⊂{0, 1}∗ è x ∈ A=n ñóùåñòâóåò ïðîãðàììà äëèíû íå áîëåå 2 log |A=n | +O(log n), ðàáîòàþùàÿ íå áîëåå t(n) øàãîâ, èñïîëüçóþùàÿ ïàìÿòü íå áîëüøå s(n), ïðèíèìàþùàÿ x è îòâåðãàþùàÿ âñå îñòàëüíûå ýëåìåíòû A=n .Ïðè ýòîì ïðîãðàììà ìîæåò êàê ïðèíèìàòü, òàê è îòâåðãàòü ñëîâà, íåëåæàùèå â A=n .Äîêàçàòåëüñòâî.
Âíåñ¼ì â ïðîãðàììó, ñóùåñòâóþùóþ ïî òåîðåìå 2.11,ñëåäóþùåå èçìåíåíèå: âìåñòî çàïðîñà ê îðàêóëó, ïðèíàäëåæèò ëè å¼ âõîäê A, îíà áóäåò ïî óìîë÷àíèþ ñ÷èòàòü, ÷òî å¼ âõîä ëåæèò â A. Òîãäà îðàêóëáîëåå íå ïîíàäîáèòñÿ, ïðè ýòîì íà ñëîâàõ èç A=n ðåçóëüòàò áóäåò òàêèìæå, à ýòî è òðåáóåòñÿ.2.2ÝêñòðàêòîðûÌíîãèå âû÷èñëèòåëüíûå çàäà÷è ðåøàþòñÿ âåðîÿòíîñòíûìè àëãîðèòìàìè áîëåå ýôôåêòèâíî, ÷åì äåòåðìèíèðîâàííûìè. Îäíàêî, âåðîÿòíîñò18íûå àëãîðèòìû òðåáóþò èñòî÷íèêà ñëó÷àéíûõ áèòîâ, êîòîðûé ìîæåò îòñóòñòâîâàòü, áûòü äîðîãèì èëè íåñîâåðøåííûì.
×òîáû óìåíüøèòü ïîòðåáíîñòü â ñëó÷àéíûõ áèòàõ, èùóò ñïîñîáû äåðàíäîìèçèðîâàòü àëãîðèòì [10; 25; 26; 31]. Îäíà èç èäåé äåðàíäîìèçàöèè [46] ñîñòîèò â òîì,÷òîáû âçÿòü íå î÷åíü ðàâíîìåðíî ðàñïðåäåë¼ííûå ñëó÷àéíûå áèòû èïðåîáðàçîâàòü èõ â ïî÷òè ðàâíîìåðíûå. Òàêèå ïðåîáðàçîâàíèÿ íàçûâàþòýêñòðàêòîðàìè. Èñõîäíàÿ èäåÿ ìîæåò óòî÷íÿòüñÿ ðàçëè÷íûìè ñïîñîáàìè(íàèáîëåå ïîëíûå îáçîðû ïðèâåäåíû â [40; 41; 50]), ìû ñôîðìóëèðóåì äâàíàèáîëåå ÷àñòî âñòðå÷àþùèõñÿ è èñïîëüçóåìûõ âàðèàíòà. Íà÷í¼ì ñ ôîðìàëüíûõ îïðåäåëåíèé ñòåïåíè ðàâíîìåðíîñòè ðàñïðåäåëåíèÿ.
Ìû áóäåìèñïîëüçîâàòü ðàçëè÷íûå ôîðìàëèçàöèè äëÿ èñõîäíîãî è ïðåîáðàçîâàííîãîðàñïðåäåëåíèé.Îïðåäåëåíèå 2.13. Ìèí-ýíòðîïèåé ñëó÷àéíîé âåëè÷èíû ξ , ïðèíèìàþùåé çíà÷åíèÿ íà ìíîæåñòâå X , íàçûâàåòñÿ ìàêñèìàëüíîå ÷èñëî k , òàêîå÷òî äëÿ ëþáîãî x ∈ X âåðîÿòíîñòü òîãî, ÷òî ξ = x, íå ïðåâûøàåò 21k .Îáîçíà÷åíèå: H∞ (ξ).Èíûìè ñëîâàìè, H∞ (ξ) = − log maxx∈X {Pr [ξ = x]} .Îïðåäåëåíèå 2.14. Ñòàòèñòè÷åñêèì ðàññòîÿíèåì ìåæäó ñëó÷àéíûìè âåëè÷èíàìè ξ è η , ïðèíèìàþùèìè çíà÷åíèÿ íà ìíîæåñòâå X íàçûâàåòñÿ âåëè÷èíà maxS⊂X Pr [ξ ∈ S] − Pr [η ∈ S]. Ýòà æå âåëè÷èíà ðàâíà1PPr [ξ = x] − Pr [η = x].
Îáîçíà÷åíèå: dist(ξ, η).2x∈XÍåòðóäíî çàìåòèòü, ÷òî ëþáîå äåòåðìèíèðîâàííîå ïðåîáðàçîâàíèå ñëó÷àéíîé âåëè÷èíû íå óâåëè÷èâàåò å¼ ìèí-ýíòðîïèþ è íå óìåíüøàåò ðàññòîÿíèå äî ðàâíîìåðíîãî ðàñïðåäåëåíèÿ. Ïîýòîìó äëÿ ïîëó÷åíèÿ ðàñïðåäåëåíèÿ, áëèçêîãî ê ðàâíîìåðíîìó, íóæíî õîòÿ áû äâà íåçàâèñèìûõ èñòî÷íèêà ñëó÷àéíîñòè. Ìåðîé êà÷åñòâà èñòî÷íèêà ñëó÷àéíîñòè (ò.å. ñëó÷àéíîéâåëè÷èíû) áóäåì ñ÷èòàòü å¼ ìèí-ýíòðîïèþ. Íàïîìíèì, ÷òî ÷åðåç Ul ìûîáîçíà÷àåì ñëó÷àéíóþ âåëè÷èíó, ðàñïðåäåë¼ííóþ ðàâíîìåðíî íà {0, 1}l .Îïðåäåëåíèå 2.15 ( [35]).
Íàçîâ¼ì (k, ε)-ýêñòðàêòîðîì ñ îäíèì èñòî÷íèêîì ôóíêöèþ Ext : {0, 1}n × {0, 1}d → {0, 1}m , òàêóþ ÷òî äëÿ ëþáîéñëó÷àéíîé âåëè÷èíû ξ íà {0, 1}n ñ ìèí-ýíòðîïèåé íå ìåíüøå k èíäóöèðîâàííàÿ âåëè÷èíà Ext(ξ, Ud ) ðàñïîëîæåíà íà ðàññòîÿíèè íå áîëüøå ε îò Um .(Çäåñü ïðåäïîëàãàåòñÿ, ÷òî ðàñïðåäåëåíèå Ud , Um è ξ íåçàâèñèìû).19Ðàçóìååòñÿ, ôîðìàëüíî ó ýòîãî ýêñòðàêòîðà äâà èñòî÷íèêà ñëó÷àéíîñòè. Íî âòîðîé èç íèõ ôèêñèðîâàí, ÷òî ïîçâîëÿåò ðàññìàòðèâàòü òàêîéýêñòðàêòîð êàê ñëó÷àéíîå ïðåîáðàçîâàíèå îäíîé ñëó÷àéíîé âåëè÷èíû.
Âàíãëîÿçû÷íîé ëèòåðàòóðå òàêîé îáúåêò íàçûâàþò seeded extractor (ýêñòðàêòîð ñî ñëó÷àéíûì çåðíîì). Åñëè èñõîäíûõ èñòî÷íèêîâ ñëó÷àéíîñòèõîòÿ áû äâà, òî íåîáõîäèìîñòü â ñëó÷àéíîì çåðíå îòïàäàåò.Îïðåäåëåíèå 2.16. Íàçîâ¼ì (k, ε)-ýêñòðàêòîðîì ñ äâóìÿ èñòî÷íèêàìèôóíêöèþ Ext : {0, 1}n × {0, 1}n → {0, 1}m , òàêóþ ÷òî äëÿ ëþáûõ íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ξ1 è ξ2 , òàêèõ ÷òî H∞ (ξ1 ) > k è H∞ (ξ2 ) > k ,âûïîëíåíî dist(Ext(ξ1 , ξ2 ), Um ) < ε.Ìîæíî ðàññìàòðèâàòü ýêñòðàêòîðû è ñ áîëüøèì ÷èñëîì èñòî÷íèêîâ, íîíàì îíè íå ïîíàäîáÿòñÿ.Ôóíêöèþ äâóõ àðãóìåíòîâ, â ÷àñòíîñòè ýêñòðàêòîð ñ îäíèì èñòî÷íèêîì,ìîæíî ýêâèâàëåíòíî ðàññìàòðèâàòü êàê äâóäîëüíûé ãðàô ñ êðàòíûìè ð¼áðàìè è îäèíàêîâûìè ñòåïåíÿìè âñåõ âåðøèí ëåâîé äîëè.  òàêîì ñëó÷àåïåðâûé àðãóìåíò çàäà¼ò âåðøèíó ëåâîé äîëè, âòîðîé àðãóìåíò íîìåð èñõîäÿùåãî ðåáðà, à çíà÷åíèå âåðøèíó ïðàâîé äîëè.
Äëÿ äâóäîëüíûõ ãðàôîâ îïðåäåëÿþùåå ñâîéñòâî ýêñòðàêòîðà ìîæíî ïåðåôîðìóëèðîâàòü ñëåäóþùèì îáðàçîì.Îïðåäåëåíèå 2.17. Äâóäîëüíûé ãðàô ñ êðàòíûìè ð¼áðàìè (L, R, E), ãäåL ëåâàÿ äîëÿ, ñîñòîÿùàÿ èç N ýëåìåíòîâ, R ïðàâàÿ äîëÿ, ñîñòîÿùàÿ èçM ýëåìåíòîâ, à E ìíîæåñòâî ð¼áåð, ò.å. ìóëüòèìíîæåñòâî ïàð èç L×R, âêîòîðîì ó êàæäîé âåðøèíû ëåâîé äîëè ñòåïåíü ðàâíà D, íàçûâàåòñÿ (K, ε)ýêñòðàêòîðîì, åñëè äëÿ ëþáîãî ìíîæåñòâà S ⊂ L, òàêîãî ÷òî |S| > K , èëþáîãî ìíîæåñòâà Y ⊂ R âûïîëíåíî: |Y | |E(S, Y )| (2.1) |R| − |E(S, R)| < ε,ãäå ÷åðåç E(P, Q) îáîçíà÷åíî ìíîæåñòâî E ∩ (P × Q), ò.å. ìíîæåñòâî ð¼áåð,âåäóùèõ èç âåðøèí ìíîæåñòâà P â âåðøèíû ìíîæåñòâà Q.
Èíûìè ñëîâàìè,äîëÿ âûõîäÿùèõ èç S ð¼áåð, èäóùèõ â ìíîæåñòâî Y , îòëè÷àåòñÿ îò äîëèâåðøèí, ëåæàùèõ â ìíîæåñòâå Y , íå áîëüøå, ÷åì íà ε.Îïðåäåëåíèÿ ãðàôà-ýêñòðàêòîðà è ôóíêöèè-ýêñòðàêòîðà (ñ îäíèì èñòî÷íèêîì) ýêâèâàëåíòíû â ñëåäóþùåì ñìûñëå:20Óòâåðæäåíèå 2.18 (Íåÿâíî â [16]). Åñëè ôóíêöèÿ Ext ÿâëÿåòñÿ(k ,ε)-ýêñòðàêòîðîì, òî ñîîòâåòñòâóþùèé åé ãðàô ÿâëÿåòñÿ (2k ,ε)ýêñòðàêòîðîì. Åñëè N = 2n , M = 2m è D = 2d , ãäå n, m, d ñóòü öåëûå ÷èñëà, à ãðàô ÿâëÿåòñÿ (K, ε)-ýêñòðàêòîðîì, òî ñîîòâåòñòâóþùàÿôóíêöèÿ ÿâëÿåòñÿ (log K, ε)-ýêñòðàêòîðîì. äàëüíåéøåì áóäåì íàçûâàòü äâóäîëüíûì ãðàôîì òèïà (n, m, d) ãðàôñ êðàòíûìè ð¼áðàìè, èìåþùèé N = 2n âðåøèí â ëåâîé äîëå, M = 2mâåðøèí â ïðàâîé äîëå è ñòåïåíü êàæäîé âåðøèíû ñëåâà D = 2d .Ñôîðìóëèðîâàííîå óòâåðæäåíèå ñëåäóåò èç ëåììû 5 â [16], íî äëÿ ïîëíîòû èçëîæåíèÿ ìû ïðèâåä¼ì åãî ïðÿìîå äîêàçàòåëüñòâî, êîòîðîå àâòîðóçíàë îò Ìàêñèìà Áàáåíêî.
Òàêæå ñòîèò îòìåòèòü, ÷òî íà ïîõîæåé èäååîñíîâàíà 6-àÿ çàäà÷à îñåííåãî òóðà äâàäöàòü ñåäüìîãî Òóðíèðà Ãîðîäîâ çà89 êëàññû [7].2Äîêàçàòåëüñòâî. Ñâîéñòâî ãðàôà-ýêñòðàêòîðà ñëåäóåò èç ñâîéñòâàôóíêöèè-ýêñòðàêòîðà äëÿ ðàñïðåäåëåíèÿ, ðàâíîìåðíîãî íà ìíîæåñòâå S .Ïîýòîìó â îäíó ñòîðîíó óòâåðæäåíèå î÷åâèäíî.  äðóãóþ ñòîðîíó íóæíîäîêàçàòü, ÷òî åñëè ñâîéñòâî ôóíêöèè-ýêñòðàêòîðà âûïîëíåíî äëÿ âñåõðàâíîìåðíûõ ðàñïðåäåëåíèé íà ìíîæåñòâàõ ðàçìåðà 2k , òî îíî âûïîëíåíî äëÿ âñåõ ðàñïðåäåëåíèé ñ ìèí-ýíòðîïèåé íå ìåíüøå k . Äëÿ ýòîãîäîêàæåì, ÷òî ëþáîå òàêîå ðàñïðåäåëåíèå ìîæíî ïðåäñòàâèòü â âèäå âûïóêëîé êîìáèíàöèè ðàâíîìåðíûõ ðàñïðåäåëåíèé íà ìíîæåñòâàõ ðàçìåðàK = 2k .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
