Автореферат (1103423), страница 3
Текст из файла (страница 3)
Ôîðìàëüíî òåîðåìà ôîðãðàìì, ïåðåâîäÿùèõìóëèðóåòñÿ òàê:Ïóñòü äàíû ñëîâà èç íóëåé è åäèíèö a è b è ÷èñëà n è k,òàêèå ÷òî C(a) < n è C(a|b) < k. Òîãäà ñóùåñòâóåò òàêîå ñëîâî p,÷òî:• C(a|p, b) 6 O(log n);• |p| 6 k + O(log n);• C(p|a) 6 O(log n),ãäå êîíñòàíòû â O(·)-îáîçíà÷åíèÿõ íå çàâèñÿò îò a, b, n, k, íî ìîãóòçàâèñåòü îò âûáðàííîé óíèâåðñàëüíîé ôóíêöèè â îïðåäåëåíèè C.Òåîðåìà 2.Èäåÿ äîêàçàòåëüñòâà ñîñòîèò â ñëåäóþùåì: çíà÷åíèåpâûáèðàåòñÿñðåäè çíà÷åíèé õåø-ôóíêöèé èç íåêîòîðîãî ñåìåéñòâà.
×òîáû áûëà ìàëàC(p|a), íóæíî ÷òîáû ñåìåéñòâî áûëî íåáîëüøèì. ×òîáû áûëàìàëà ñëîæíîñòü C(a|p, b), íóæíî ÷òîáû äëÿ õåø-ôóíêöèè áûëî íåìíîãîêîëëèçèé â ìíîæåñòâå Sb = {x | C(x|b) < k} ïðè ëþáîì b.  äèññåðòàöèèñëîæíîñòüïîêàçàíî, ÷òî â êà÷åñòâå òàêîãî ñåìåéñòâà ôóíêöèé ìîæíî âçÿòü ëþáîéýêñòðàêòîð. (Åñëè ðàññìîòðåòü ôóíêöèþ äâóõ àðãóìåíòîâ êàê ñåìåéñòâîôóíêöèé ïåðâîãî àðãóìåíòà, ïðîèíäåêñèðîâàííîå çíà÷åíèÿìè âòîðîãîàðãóìåíòà).Îïðåäåëåíèå 3. ÔóíêöèÿýêñòðàêòîðîìExt : {0, 1}n × {0, 1}d → {0, 1}míàçûâàåòñÿ(k, ε), åñëè äëÿ ëþáûõ íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ξnd−kíà {0, 1} è η íà {0, 1} , òàêèõ ÷òî Pr [ξ = x] 6 2ïðè ëþáîì ôèêñèðîmâàííîì x, à η ðàñïðåäåëåíà ðàâíîìåðíî, è ëþáîãî S ⊂ {0, 1} âûïîëíåíî|S| Pr [Ext(ξ, η)] − 2m < ε.Àí.À. Ìó÷íèê òàêæå äîêàçàë ðàñøèðåíèå òåîðåìû îá óñëîâíîì êîäèðîâàíèè íà ñëó÷àé íåñêîëüêèõ óñëîâèé:9Ïóñòü äàíû äâîè÷íûå ñëîâà a, b è c è ÷èñëà n, k è l, äëÿêîòîðûõ âûïîëíåíî C(a) < n, C(a|b) < k è C(a|c) < l.
Òîãäà ñóùåñòâóþò ñëîâà p äëèíû k + O(log n) è q äëèíû l + O(log n, îäíî èç êîòîðûõÿâëÿåòñÿ íà÷àëîì äðóãîãî, äëÿ êîòîðûõ âåëè÷íèû C(a|p, b), C(a|q, c),C(p|a) èC(q|a) èìåþò ïîðÿäîê O(log n).Òåîðåìà 4. äèññåðòàöèè ïîêàçàíî, ÷òî ýòîò ðåçóëüòàò òàêæå ìîæíî äîêàçàòüïðè ïîìîùè ýêñòðàêòîðîâ. Äëÿ ýòîãî ââîäèòñÿ íîâîå ïîíÿòèå ïðåôèêñ-27íîãî ýêñòðàêòîðà è âåðîÿòíîñòíûì ìåòîäîìäîêàçûâàåòñÿ ñóùåñòâîâà-íèå òàêèõ îáúåêòîâ.k ε)-ýêñòðàêòîð Ext : {0, 1}n ×Îïðåäåëåíèå 5. Áóäåì ãîâîðèòü, ÷òî ( ,ïðåôèêñíûì{0, 1}d → {0, 1}m , ãäå m > k , ÿâëÿåòñÿ, åñëè äëÿ ëþáîãîi 6 k åãî ïðåôèêñ äëèíû m − i ÿâëÿåòñÿ (k − i, ε)-ýêñòðàêòîðîì.
Ïîändm−iïðåôèêñîì ïîíèìàåòñÿ ôóíêöèÿ Exti : {0, 1} × {0, 1} → {0, 1}, ïîëó÷åííàÿ èç èñõîäíîé îòðåçàíèåì ïîñëåäíèõ i áèòîâ. ãëàâå 4 ôîðìóëèðóþòñÿ è äîêàçûâàþòñÿ ðàçëè÷íûå àíàëîãè òåîðåìû Ìó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü.Îïðåäåëåíèå 6. Êîëìîãîðîâñêîé ñëîæíîñòüþ ñëîâàñ îãðàíè÷åíèåì íà ïàìÿòüxîòíîñèòåëüíîys íàçûâàåòñÿ äëèíà êðàò÷àéøåãîñëîâà p, òàêîãî ÷òî U (p, y) = x è ïðè ýòîì U (p, y) èñïîëüçóåò íå áîëüøås ÿ÷ååê ïàìÿòè.
Ýòî ÷èñëî áóäåì îáîçíà÷àòü Cs (x|y).ñëîâàÁëàãîäàðÿ òîìó, ÷òî ñóùåñòâóþò ÿâíûå êîíñòðóêöèè ýêñòðàêòîðîâ,ñòàíîâèòñÿ âîçìîæíûì èñïîëüçîâàíèå ðàçðàáîòàííîé òåõíèêè äëÿ ðàñøèðåíèÿ òåîðåìû íà ñëó÷àé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü. Âäèññåðòàöèè äîêàçûâàåòñÿ ñëåäóþùàÿ òåîðåìà:Ïóñòü äàíû äâîè÷íûå ñëîâà a è b, à òàêæå ÷èñëà n, kè s, äëÿ êîòîðûõ âåðíî Cs(a) < n è Cs(a|b) < k.
Ïóñòü ÷èñëà dè q òàêîâû, ÷òî ïðè ëþáîì l 6 k ñóùåñòâóåò (l, 0.25)-ýêñòðàêòîðExtl : {0, 1}n × {0, 1}d → {0, 1}l , âû÷èñëèìûé íà ïàìÿòè q (äëÿ íåêîòîðîé çàðàíåå ôèêñèðîâàííîé óíèâåðñàëüíîé ìíîãîëåíòî÷íîé ìàøèíûÒüþðèíãà). Òîãäà ñóùåñòâóåò òàêîå ñëîâî p, ÷òî:• CO(s+q+n ) (a|p, b) 6 d + O(log n);Òåîðåìà 7.227 Í.Àëîí, Äæ. Ñïåíñåð. Âåðîÿòíîñòíûé ìåòîä â êîìáèíàòîðèêå.
Ì.: ÁÈÍÎÌ, 2011. 320 c.10;• |p| 6 k + O(log n)• CO(q) (p|a) 6 d + O(log n).Ñ èñïîëüçîâàíèåì íàèëó÷øèõ èçâåñòíûõ êîíñòðóêöèé ýêñòðàêòîðîâ28ìîæíî ïîëó÷èòü áåçóñëîâíîå ñëåäñòâèå, â êîòîðîì â ïðàâûõ ÷àñòÿõ íåðàâåíñòâ âìåñòîd + O(log n)ñòîÿòO(log3 n).Äàëåå, äëÿ óëó÷øåíèÿ ðåçóëüòàòà ïðèìåíÿåòñÿ òåõíèêàíàèâíîéäå-ðàíäîìèçàöèè. Èäåÿ ñîñòîèò â ñëåäóþùåì: íóæíî íàéòè õåø-ôóíêöèþ,èìåþùóþ ìàëî êîëëèçèé âíóòðè êàæäîãî ìíîæåñòâàCs (x|b) < k}.Sb,s = {x |Ìíîæåñòâ òàêîãî âèäà íåìíîãî îòíîñèòåëüíî ÷èñëà âñåõìíîæåñòâ ðàçìåðà2k :ýêñïîíåíòà âìåñòî äâîéíîé ýêñïîíåíòû.
 òî æåâðåìÿ êîíñòðóêöèÿ ñ ýêñòðàêòîðàìè ãàðàíòèðóåò ìàëîñòü ÷èñëà êîëëèçèé äëÿ âñåõ ìíîæåñòâ ðàçìåðà2k . ðàáîòå ïîêàçàíî, êàê ìîæíîîáîéòèñü ëèøü îäíîé ôóíêöèåé, ïîëó÷åííîé â ðåçóëüòàòå ðàáîòû ãåíåðàòîðà ïñåâäîñëó÷àéíûõ ÷èñåë ÍèñàíàÂèãäåðñîíà. Äëÿ ýòîãî íóæíîñîâåðøèòü òàêóþ ïîñëåäîâàòåëüíîñòü øàãîâ:1. Äîêàçàòü, ÷òî ñëó÷àéíàÿ ôóíêöèÿ óäîâëåòâîðÿåò óñëîâèþ ìàëîãî÷èñëà êîëëèçèé ñ îòäåë¼ííîé îò íóëÿ âåðîÿòíîñòüþ;2.
Äîêàçàòü, ÷òî ñâîéñòâî ìàëîñòè ÷èñëà êîëëèçèé ðàñïîçíà¼òñÿ ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ ïîëèíîìèàëüíîãî ðàçìåðà èêîíñòàíòíîé ãëóáèíû;3. Âîñïîëüçîâàòüñÿ ñâîéñòâîì ãåíåðàòîðà ÍèñàíàÂèãäåðñîíàîáìà-íûâàòü âñå òàêèå ñõåìû è ñäåëàòü âûâîä, ÷òî ñðåäè åãî çíà÷åíèéâñòðå÷àåòñÿ êîä íóæíîé ôóíêöèè;4. Ïîêàçàòü, ÷òî íóæíûé àðãóìåíò ãåíåðàòîðà ìîæíî íàéòè íà ïîëèíîìèàëüíîé ïàìÿòè. ðåçóëüòàòå äîêàçûâåòñÿ ñëåäóþùàÿ òåîðåìà:Ïóñòü äàíû äâîè÷íûå ñëîâà a è b, à òàêæå ÷èñëà n, k è s,äëÿ êîòîðûõ âåðíî |b| < n, Cs(a) < n è Cs(a|b) < k.
Òîãäà ñóùåñòâóåòòàêîå ñëîâî p, ÷òî:• CO(s)+poly(n) (a|p, b) 6 O(log log s) + O(log n);• |p| 6 k + O(log n);Òåîðåìà 8.28 R.Raz, O. Reingold, S. Vadhan. Extracting All the Randomness and Reducing the Error inTrevisan's Extractor // Proceedings of the 30th Annual ACM Symposium on the Theory of Computing.
1999. P. 149158.11.• CO(s)+poly(n) (p|a) 6 O(log log s) + O(log n)Êîìáèíàöèåé äâóõ ïîäõîäîâ ïîëó÷àåòñÿ áåçóñëîâíàÿ òåîðåìà, â êîòîðîé âñå íåâÿçêè ðàâíûO(log n).Òåîðåìà äëÿ äâóõ óñëîâèé òàêæå ðàñïðîñòðàíÿåòñÿ íà ñëîæíîñòü ñîãðàíè÷åíèåì íà ïàìÿòü. Êàê è äëÿ îäíîãî óñëîâèÿ, ìîæíî äåéñòâîâàòü äâóìÿ ñïîñîáàìè: èñïîëüçîâàòü ÿâíóþ êîíñòðóêöèþ ïðåôèêñíîãîýêñòðàêòîðà èëè èñïîëüçîâàòü ìåòîäíàèâíîéäåðàíäîìèçàöèè.
Êîì-áèíàöèåé äâóõ ïîäõîäîâ ïîëó÷åíà ñëåäóþùàÿ òåîðåìà.Ïóñòü äàíû äâîè÷íûå ñëîâà a, b è c, à òàêæå ÷èñëà n, k,l è s, äëÿ êîòîðûõ âûïîëíåíî |b| < n, |c| < n, Cs (a) < n, Cs (a|b) < k èCs (a|c) < l. Òîãäà ñóùåñòâóþò ñëîâà p è q , îäíî èç êîòîðûõ ÿâëÿåòñÿíà÷àëîì äðóãîãî, äëÿ êîòîðûõ âûïîëíåíû íåðàâåíñòâà:• CO(s)+poly(n) (a|p, b) 6 O(log n);• CO(s)+poly(n) (a|q, c) 6 O(log n);• |p| 6 k + O(log n);• |q| 6 l + O(log n);• CO(s)+poly(n) (p|a) 6 O(log n);• CO(s)+poly(n) (q|a) 6 O(log n).Òåîðåìà 9.Áîëåå òîãî, ìåòîä íàèâíîé äåðàíäîìèçàöèè ïîçâîëÿåò ðàñïðîñòðàíèòü òåîðåìó íå òîëüêî íà ïîëèíîìèàëüíîå, íî è íà ýêñïîíåíöèàëüíîå÷èñëî óñëîâèé.Ïóñòü äàíû ÷èñëà n, s, r è k1, .
. . , kr è äâîè÷íûå ñëîâàa, b1 , . . . , br , òàêèå ÷òî Cs (a) < n, |bi | < poly(n) è Cs (a|bi ) < ki ïðèâñåõ i = 1, . . . , r. Òîãäà ñóùåñòâóþò ñëîâà p1, . . . , pr , äëÿ êîòîðûõâûïîëíåíû ñëåäóþùèå óñëîâèÿ:• Âñå pi ÿâëÿþòñÿ ïðåôèêñàìè îäíîãî è òîãî æå ñëîâà;• CO(s)+poly(n) (a|pi , bi ) 6 O(log log s) + O(log n) ïðè âñåõ i = 1, . . . , r;• |pi | 6 ki + O(log n) ïðè âñåõ i = 1, . .
. , r;• CO(s)+poly(n) (pi |a) 6 O(log log s) + O(log n) ïðè âñåõ i = 1, . . . , r.Òåîðåìà 10.Âãëàâå5äîêàçûâàåòñÿâàðèàíòòåîðåìûÌó÷íèêàäëÿCAM-ñëîæíîñòè. Èäåÿ ñîñòîèò â òîì, ÷òîáû âìåñòî ïðîèçâîëüíîãî ÿâíîãî ýêñ-12òðàêòîðà âçÿòü ýêñòðàêòîð Òðåâèñàíà29, êîòîðûé ïîçâîëÿåò áûñòðî îñó-ùåñòâëÿòü è êîäèðîâàíèå, è äåêîäèðîâàíèå. Ïîõîæàÿ òåõíèêà èñïîëüçîâàëàñü â ðàáîòå Ã. Áþðìàíà, Ò. Ëè è Ä. âàí Ìåëêåáååêà î ñæàòèè30ÿçûêîâ.CAM-ñëîæíîñòüîïðåäåëÿåòñÿâìîäåëèâû÷èñëåíèéÀðòóðàÌåðëèíà, ñî÷åòàþùåé â ñåáå íåäåòåðìèíèçì è ñëó÷àéíîñòü. ÏîäWáó-äåì ïîíèìàòü óíèâåðñàëüíóþ ôóíêöèþ ÷åòûð¼õ àðãóìåíòîâ, èç êîòîðûõïåðâûé ïîíèìàåòñÿ êàê òåêñò ïðîãðàììû, âòîðîé êàê àðãóìåíò, òðåòèé êàê ñåðòèôèêàò è ÷åòâ¼ðòûé êàê ñëó÷àéíûå áèòû.
Ôóíêöèÿâîçâðàùàåò ëèáî äâîè÷íîå ñëîâî, ëèáî ñïåöèàëüíûé ñèìâîë îøèáêèÎïðåäåëåíèå 11.Ñëîæíîñòüþ Àðòóðà-ÌåðëèíàW⊥.x îòíîñèòåëüñëîâà p, òàêîãîñëîâày çà âðåìÿ t íàçûâàåòñÿ äëèíà êðàò÷àéøåãî2÷òî Prr [∃qW (p, y, q, r) = x è ∀qW (p, y, q, r) ∈ {x, ⊥}] > , ïðè ýòîì âðå3ìÿ ðàáîòû W (p, y, q, r) íå ïðåâîñõîäèò t ïðè âñåõ q è r . Ýòî ÷èñëî áóäåìtîáîçíà÷àòü ÷åðåç CAM (x|y).íî ñëîâà ðàáîòå äîêàçàíà ñëåäóþùàÿ òåîðåìà:Äëÿ ëþáîãî ïîëèíîìà t1(n) ñóùåñòâóåò ïîëèíîì t2(n),äëÿ êîòîðîãî âûïîëíåíî ñëåäóþùåå ñâîéñòâî. Ïóñòü äàíû ÷èñëà n èk , ñëîâî a äëèíû ìåíüøå n è ñëîâî b, òàêèå ÷òî Ct (n) (a|b) < k . Òîãäàñóùåñòâóåò ñëîâî p äëèíû k, òàêîå ÷òî ñëîæíîñòè CAMt (n)(a|b, p) èCt (n) (p|a) èìåþò ïîðÿäîê O(log3 n).Òåîðåìà 12.122Òàêæå â äèññåðòàöèè ôîðìóëèðóåòñÿ ãèïîòåçà îá àíàëîãè÷íîì óòâåðæäåíèè äëÿ íåñêîëüêèõ óñëîâèé è àíàëèçèðóþòñÿ ïðåïÿòñòâèÿ ê ðàñøèðåíèþ êîíñòðóêöèè íà ýòîò ñëó÷àé.Íàêîíåö, â ãëàâå 6 òåõíèêàíàèâíîéäåðàíäîìèçàöèè ïðèìåíÿåò-ñÿ ê òåîðèè êîëìîãîðîâñêèõ ýêñòðàêòîðîâ, â ðåçóëüòàòå äîêàçûâàåòñÿòåîðåìà î ñóùåñòâîâàíèè îïòèìàëüíûõ êîëìîãîðîâñêèõ ýêñòðàêòîðîâ ñîãðàíè÷åíèåì íà ïàìÿòü.Ñóùåñòâóåò ïîëèíîì p(n), òàêîé ÷òî äëÿ ëþáîé ôóíêöèè s(n) > p(n), êîíñòðóèðóåìîé ïî ïàìÿòè, è ëþáûõ ôóíêöèé 1 <k(n) < n è 1 < δ(n) < k(n) − O(log n), âû÷èñëèìûõ íà ïàìÿòèÒåîðåìà 13.29 L.Trevisan.
Construction of Extractors Using Pseudo-Random Generators // Journal of theACM. 2001. V. 48. 4. P. 860879.30 H. Buhrman, T. Lee, D. van Melkebeek. Language Compression...13, ñóùåñòâóåò âû÷èñëèìîå íà ïàìÿòèñåìåéñòâî ôóíêöèé, ãäå, òàêîå÷òî äëÿ íåêîòîðîé êîíñòàíòûäëÿ âñåõ è âñåõ ñëîâ èäëèíû èç óñëîâèé,èñëåäóåò, ÷òî.Òàêæå ñóùåñòâóåò àíàëîãè÷íîå ñåìåéñòâî ôóíêöèéäëÿ, òàêîå ÷òî ïðè òåõ æå óñëîâèÿõ íà è âûïîëíåíîè.Ôóíêöèÿíàçûâàåòñÿ êîëìîãîðîâñêèì ýêñòðàêòîðîì, à ôóíêöèÿ óñèëåííûì êîëìîãîðîâñêèì ýêñòðàêòîðîì.s(n)O(s(n))nnm(n)KExtn : {0, 1} × {0, 1} → {0, 1}m = 2k(n) − O(log n)µ > 1nx ynCs (x) > k(n) Cs (y) > k(n) Cµs (x, y) > Cs (x) +Cs (y) − δ(n)Cs (KExtn (x, y)) > m(n) − δ(n) − O(log n)SKExtnm=k(n) − O(log n)x yssC (SKExtn (x, y)|x) > m(n) − δ(n) − O(log n) C (SKExtn (x, y)|y) >m(n) − δ(n) − O(log n)KExtnSKExtnÑëåäóÿ ðàáîòàì Ì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
