Диссертация (1103424), страница 9
Текст из файла (страница 9)
Áóäåì ãîâîðèòü, ÷òî (k , ε)-ýêñòðàêòîð Ext : {0, 1}n ×{0, 1}d → {0, 1}m , ãäå m > k , ÿâëÿåòñÿ ïðåôèêñíûì, åñëè äëÿ ëþáîãî i 6 kåãî ïðåôèêñ äëèíû m − i ÿâëÿåòñÿ (k − i, ε)-ýêñòðàêòîðîì. Ïîä ïðåôèêñîìïîíèìàåòñÿ ôóíêöèÿ Exti : {0, 1}n × {0, 1}d → {0, 1}m−i , ïîëó÷åííàÿ èçèñõîäíîé îòðåçàíèåì ïîñëåäíèõ i áèòîâ.Ñ èñïîëüçîâàíèåì âåðîÿòíîñòíîãî ìåòîäà ìîæíî ïîëó÷èòü ñëåäóþùóþòåîðåìó ñóùåñòâîâàíèÿ:Òåîðåìà 3.5. Äëÿ âñåõ n, k è ε, äëÿ êîòîðûõ 1 < k 6 n è ε > 0, ñóùåñòâóåò ïðåôèêñíûé (k , ε)-ýêñòðàêòîð ñ ïàðàìåòðàìè d = log n + 2 log(1/ε) +O(1) è m = k + d − 2 log(1/ε) − O(1).42Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ýòîé òåîðåìû ïîõîæå íà ñòàíäàðòíîå äîêàçàòåëüñòâî òåîðåìû 2.19.
À èìåííî, èñïîëüçóåòñÿ âåðîÿòíîñòíûé ìåòîä:äëÿ ñëó÷àéíîãî ãðàôà ñ çàäàííûìè ïàðàìåòðàìè äîêàçûâàåòñÿ, ÷òî îí îáëàäàåò íóæíûì ñâîéñòâîì ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ.  îòëè÷èå îòñòàíäàðòíîãî äîêàçàòåëüñòâà, çäåñü íóæíî ïðîâåðÿòü âûïîëíåíèå ñðàçóìíîãèõ óñëîâèé: ëþáîé ïðåôèêñ äîëæåí ÿâëÿòüñÿ ýêñòðàêòîðîì. Ìû ïîêàæåì, ÷òî âåðîÿòíîñòü êàæäîãî èç óñëîâèé íå ïðîñòî ïîëîæèòåëüíà, àáëèçêà ê åäèíèöå, òàê ÷òî âñå óñëîâèÿ îäíîâðåìåííî âûïîëíåíû òàêæå ñïîëîæèòåëüíîé âåðîÿòíîñòüþ.Çàìåòèì, ÷òî â îïðåäåëåíèè 2.17 äîñòàòî÷íî ïîòðåáîâàòü èñòèííîñòèíåðàâåíñòâà (2.1) òîëüêî äëÿ ìíîæåñòâ ðàçìåðà â òî÷íîñòè K .
Äåéñòâèòåëüíî, åñëè íåðàâåíñòâî íàðóøåíî äëÿ ìíîæåñòâà S 0 ðàçìåðà áîëüøå K èíåêîòîðîãî ìíîæåñòâà Y , òî îíî áóäåò íàðóøåíî è äëÿ ìíîæåñòâà S ⊂ S 0òî÷åê èç S 0 , èìåþùèõ íàèáîëüøåå (èëè íàèìåíüøåå) ÷èñëî ñîñåäåé â Y .Áîëåå òîãî, ìîäóëü â íåðàâåíñòâå (2.1) ìîæíî ðàñêðûòü. Íàïðèìåð, äîñòàòî÷íî ïðîâåðèòü, ÷òî|E(S, Y )| |Y |<+ε|E(S, R)||R|äëÿ âñåõ S ðàçìåðà K è âñåõ Y ⊂ R. Äåéñòâèòåëüíî, íåðàâåíñòâî|E(S, Y )| |Y |>−ε|E(S, R)||R|ñëåäóåò èç ïðåäûäóùåãî, ïðèìåí¼ííîãî ê äîïîëíåíèþ Y . Èíà÷å ãîâîðÿ,åñëè èç S â Y âåä¼ò ñëèøêîì ìàëî ð¼áåð, òî èç S â äîïîëíåíèå Y âåä¼òñëèøêîì ìíîãî ð¼áåð.Âåðîÿòíîñòíîå ðàñïðåäåëåíèå íà ãðàôàõ îïðåäåëèì ñëåäóþùèì îáðàçîì. Äëÿ ëþáîé âåðøèíû ëåâîé äîëè (ñëîâà äëèíû n) âûáåðåì ðàâíîìåðíî è íåçàâèñèìî D = 2d ñîñåäåé â ïðàâîé ÷àñòè (ñëîâ äëèíû m).
Îöåíèìñâåðõó âåðîÿòíîñòü ñîáûòèÿ ñëó÷àéíûé ãðàô íå ÿâëÿåòñÿ ïðåôèêñíûì ýêñòðàêòîðîì.Åñëè ñâîéñòâî ýêñòðàêòîðà íàðóøåíî äëÿ êàêîãî-òî ïðåôèêñà äëèíûm − i, òî ñóùåñòâóþò ìíîæåñòâî S ⊂ {0.1}n èç K/2i ýëåìåíòîâ è ìíîæåñòâî Y ⊂ {0, 1}m−i ðàçìåðà α2m−i (äëÿ íåêîòîðîãî ïîëîæèòåëüíîãî α),êîëè÷åñòâî ð¼áåð ìåæäó êîòîðûìè ïðåâûøàåò (α + ε)KD/2i . Çäåñü ìûñ÷èòàåì, ÷òî ðåáðî èä¼ò â Y , åñëè îíî èä¼ò â ñëîâî, ïðîäîëæàþùåå íåêîòîðîå ñëîâî èç Y . Èç íåðàâåíñòâà Õ¼ôäèíãà (òåîðåìà 2.39) ñëåäóåò, ÷òî43âåðîÿòíîñòü ýòîãî ñîáûòèÿ íå ïðåâûøàåò exp −2ε2 KD/2i . Çíà÷èò, âåðîÿòíîñòü ñîáûòèÿ ñëó÷àéíûé ãðàô íå ÿâëÿåòñÿ ïðåôèêñíûì ýêñòðàêòîðîìîãðàíè÷åíà ñâåðõó ñóììîé ýòèõ îöåíîê ïî âñåì i, S è Y :kXK/2iCNi· 2M/2 exp −2ε2 KD/2i .(3.1)i=0(Çäåñü ìû ïðîèãíîðèðîâàëè, ÷òî |Y | = α2m−i , è ïðîâåëè ñóììèðîâàíèå ïîâñåì Y ⊂ {0, 1}m−i ).
 ñèëó íåðàâåíñòâà (2.5) âûïîëíåíî Cuv 6 (ue/v)v ,ïîýòîìó ñóììà (3.1) íå ïðåâîñõîäèò ik XeN K/2 M/2i2exp(−2ε2 KD/2i ) =iK/2i=0=k XK/2i (1+ln(2i N/K))e·e−ε2 KD/2i M ln 2/2i−ε2 KD/2i· e·e.i=0Èç óñëîâèÿ òåîðåìû ñëåäóåò, ÷òî d = m − k + 2 log(1/ε) + O(1), îòêóäàln 2D > MK · ε2 , åñëè êîíñòàíòà â O(1) âçÿòà äîñòàòî÷íî áîëüøîé. Çíà÷èò,âòîðîé ìíîæèòåëü â êàæäîì ñëàãàåìîì íå áîëüøå 1.  òî æå âðåìÿ, ïåðâûéìíîæèòåëü i-ãî ñëàãàåìîãî ðàâåíiieK/2 (1+ln(2 N/K)−ε÷òî ìåíüøå2D)i6 eK/2 (1+ln N −ε2D), i1 K/2,2ïîñêîëüêó d − 2 log(1/ε) = log n + O(1), îòêóäà Dε2 >1 + ln 2 + ln N ïðè äîñòàòî÷íî áîëüøîé êîíñòàíòå â O(1). Ïîñêîëüêó ñóììàýòèõ îöåíîê ïî âñåì i ñòðîãî ìåíüøå åäèíèöû, ïîëó÷àåì, ÷òî âåðîÿòíîñòüñîáûòèÿ ñëó÷àéíûé ãðàô íå ÿâëÿåòñÿ ïðåôèêñíûì ýêñòðàêòîðîì ïîëîæèòåëüíà.
Çíà÷èò, ïðåôèêñíûå ýêñòðàêòîðû ñóùåñòâóþò, ÷òî è òðåáîâàëîñüäîêàçàòü.Îäíàêî ïðîñòî èñïîëüçîâàòü ïðåôèêñíûé ýêñòðàêòîð íåäîñòàòî÷íî.Íåîáõîäèìî ìîäèôèöèðîâàòü ðàññóæäåíèå, ïîñêîëüêó òåïåðü äëÿ a íóæíîíàéòè äâà ñîñåäà â äâóõ ðàçíûõ ãðàôàõ. Ìû èçìåíèì îïðåäåëåíèå îïàñíîéâåðøèíû è äîêàæåì ñëåäóþùèé àíàëîã ëåììû 3.2:Ëåììà 3.6. Íàçîâ¼ì âåðøèíó ëåâîé äîëè ñëàáî îïàñíîé â ìíîæåñòâåS , åñëè õîòÿ áû ïîëîâèíà å¼ ñîñåäåé ïëîõè äëÿ S (ñì. ðèñ.
3.9). Òîãäàâ ñëó÷àå, êîãäà ãðàô ÿâëÿåòñÿ ýêñòðàêòîðîì, êîëè÷åñòâî ñëàáî îïàñíûõâåðøèí â S íå ïðåâûøàåò 4εK .44,S |S| < 2kÏëîõèå âåðøèíû{0, 1}<nÓ êàæäîé âåðøèíû D ñîñåäåé{0, 1}kÑëàáî îïàñíàÿ âåðøèíàÐèñ. 3.9: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà äëÿ äâóõ óñëîâèé: ñëàáî îïàñíûå âåðøèíûâ ëåâîé äîëå ãðàôà.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïî÷òè äîñëîâíî ïîâòîðÿåò äîêàçàòåëüñòâî ëåììû 3.2. Îòëè÷èå ñîñòîèò â òîì, ÷òî òåïåðü ëèøü ïîëîâèíà ð¼áåð èçìíîæåñòâà îïàñíûõ âåðøèí T âåä¼ò â ìíîæåñòâî ïëîõèõ âåðøèí Y , îòêóäà|E(T, Y )| > 12 |T | · D = 12 β|E(S, R)| è |E(S, Y )|/|E(S, R)| > 21 β . Äàëåå àíàëîãè÷íî äîêàçàòåëüñòâó ëåììû 3.2 ïîëó÷àåì 21 β < 2ε, îòêóäà |T | < 4εK ,÷òî è òðåáîâàëîñü.Òåïåðü äàäèì íîâîå äîêàçàòåëüñòâî òåîðåìû 3.3, îñíîâàííîå íà èñïîëüçîâàíèè ïðåôèêñíûõ ýêñòðàêòîðîâ.
Çàôèêñèðóåì ïðåôèêñíûé ýêñòðàêòîðE ñ ïàðàìåòðàìè n, k , d = O(log n), m = k è ε = 1/n3 . Êàê è ïðåæäå, ìû ìîæåì ñ÷èòàòü ñëîæíîñòü ýòîãî ýêñòðàêòîðà ðàâíîé 2 log n + O(1).Òàêæå ìîæíî áåç îãðàíè÷åíèÿ îáùíîñòè ïðåäïîëîæèòü, ÷òî |a| < n,C(a|b) = k − 1, C(a|c) = l − 1 è k > l.Îáîçíà÷èì ÷åðåç Sb è Sc ìíîæåñòâà ñëîâ äëèíû ìåíüøå n è ñëîæíîñòèìåíüøå k è l óñëîâíî íà b è c ñîîòâåòñòâåííî. Íàçûâàÿ ñëîâî ñëàáî îïàñíûìâ Sb , áóäåì èìåòü â âèäó ñëàáóþ îïàñíîñòü â èñõîäíîì ãðàôå, à íàçûâàÿåãî ñëàáî îïàñíûì â Sc , ñëàáóþ îïàñíîñòü â ãðàôå, ñîîòâåòñòâóþùåìl-áèòîâîìó ïðåôèêñó.
Ïîñêîëüêó ýòîò ïðåôèêñ Ek−l òàêæå ÿâëÿåòñÿ ýêñòðàêòîðîì, ëåììà 3.6 âåðíà è äëÿ íåãî. Ñëîâî a ëåæèò â ïåðåñå÷åíèè Sb èSc è íå ÿâëÿåòñÿ ñëàáî îïàñíûì íè â îäíîì èç ìíîæåñòâ, èíà÷å ñëîæíîñòüC(a|b) èëè ñëîæíîñòü C(a|c) áûëà áû ìåíüøå çàÿâëåííîé. (Çäåñü ðàññóæäåíèå ïîëíîñòüþ àíàëîãè÷íî ðàññóæäåíèþ ïðè äîêàçàòåëüñòâå èñõîäíîéòåîåðìû Ìó÷íèêà). Çíà÷èò, ìåíüøå ïîëîâèíû ñîñåäåé a â ãðàôå E ïëîõè45Sb = {x | C(x|b) < k}{0, 1}k{0, 1}Ïëîõèå âåðøèíû äëÿ SbÏëîõèå âåðøèíû äëÿ Sc<nÓ êàæäîé âåðøèíû D ñîñåäåéa íå ñëàáî îïàñíàÿ âåðøèíàpq õîðîøèé ñîñåä a ïðåôèêñ p äëèíû lSc = {x | C(x|c) < l}Ðèñ. 3.10: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà: âûáîð p.äëÿ Sb è ìåíüøå ïîëîâèíû ñîñåäåé a â ãðàôå Ek−l ïëîõè äëÿ Sc .
Ïîñëåäíååîçíà÷àåò, ÷òî ìåíüøå ïîëîâèíû ñîñåäåé a â ãðàôå E èìåþò l-áèòíûå ïðåôèêñû, êîòîðûå ïëîõè äëÿ Sc . Òàêèì îáðàçîì, íàéä¼òñÿ òàêîé ñîñåä p, ÷òîîí ñàì íå áóäåò ïëîõèì äëÿ Sb , à åãî l-áèòíûé ïðåôèêñ q íå áóäåò ïëîõèìäëÿ Sc . Ýòè p è q áóäóò èñêîìûìè (ñì. ðèñ. 3.10).Äåéñòâèòåëüíî, óñëîâíûå ñëîæíîñòè C(p|a) è C(q|a) ëîãàðèôìè÷åñêèå,ïîòîìó ÷òî p è q ìîæíî çàäàòü ýêñòðàêòîðîì è íîìåðàìè ýòèõ ñëîâ ñðåäè ñîñåäåé a. Äëèíû p è q ñîîòâåòñòâóþò òðåáîâàíèÿì. Íàêîíåö, ñëîâî aìîæíî ïîëó÷èòü èç p è b, çàäàâ ýêñòðàêòîð Ek è íîìåð a ñðåäè ñîñåäåép â ìíîæåñòâå Sb .
Ïîñêîëüêó p íå áóäåò ïëîõèì, ðàçìåð îïèñàíèÿ áóäåòëîãàðèôìè÷åñêèì. Àíàëîãè÷íî, a ìîæíî ïîëó÷èòü èç q è c, çàäàâ ýêñòðàêòîð Ek−l è íîìåð a ñðåäè ñîñåäåé q â ìíîæåñòâå Sc , ðàçìåð îïèñàíèÿ áóäåòòàêæå ëîãàðèôìè÷åñêèì.Òàêèì îáðàçîì, âñå óñëîâèÿ òåîðåìû Ìó÷íèêà äëÿ äâóõ óñëîâèé ïðîâåðåíû, à ñàìà òåîðåìà äîêàçàíà.Ñôîðìóëèðóåì òåïåðü òåîðåìó Ìó÷íèêà äëÿ ìíîãèõ óñëîâèé.Òåîðåìà 3.7. Ïóñòü äàíû ÷èñëà n, s = poly(n) è k1 6 .
. . 6 ks è äâîè÷íûåñëîâà a, b1 , . . . , bs , òàêèå ÷òî C(a) < n è C(a|bi ) < ki ïðè âñåõ i = 1, . . . , s.Òîãäà ñóùåñòâóþò ñëîâà p1 , . . . , ps , äëÿ êîòîðûõ âûïîëíåíû ñëåäóþùèåóñëîâèÿ:46••••pi ÿâëÿåòñÿ íà÷àëîì pj ïðè i < j ;C(a|pi , bi ) 6 O(log n) ïðè âñåõ i = 1, . . . , s;C(pi ) 6 ki + O(log n) ïðè âñåõ i = 1, . . . , s;C(pi |a) 6 O(log n) ïðè âñåõ i = 1, . . . , s (äîñòàòî÷íî C(ps |a) 6O(log n)).Äîêàçàòåëüñòâî ýòîé òåîðåìû îáîáùàåò äîêàçàòåëüñòâî òåîðåìû 3.3, íåïðèâíîñÿ â íåãî íèêàêèõ íîâûõ èäåé, ïîýòîìó ìû ëèøü êðàòêî îïèøåìåãî.
Âíà÷àëå íóæíî âçÿòü ïðåôèêñíûé ýêñòðàêòîð ñ m = ks , ε < sn1 3 èd = log s + O(log n) = O(log n). Òàêîé ýêñòðàêòîð ñóùåñòâóåò ïî òåîðåìå 3.5. Çàòåì íóæíî äîêàçàòü àíàëîã ëåììû 3.6, îïðåäåëèâ ñëàáî îïàñíóþâåðøèíó êàê òó, ó êîòîðîé õîòÿ áû äîëÿ 1/s ñîñåäåé (â ñîîòâåòñòâóþùåìýêñòðàêòîðå) ïëîõè äëÿ S . Êîëè÷åñòâî ñëàáî îïàñíûõ âåðøèí òîãäà íå ïðåâûñèò 2sεK = 2K/n3 . Íàêîíåö, âåðøèíà a âíîâü íå áóäåò ñëàáî îïàñíîé íèâ îäíîì èç ìíîæåñòâ Sbi , îòêóäà ñëåäóåò ñóùåñòâîâàíèå ó a ñîñåäà, õîðîøåãî äëÿ âñåõ ìíîæåñòâ Sbi . Ýòîò ñîñåä è áóäåò èñêîìûì ps , à âñå îñòàëüíûåpi åãî íà÷àëàìè ñîîòâåòñòâóþùåé äëèíû.47Ãëàâà 4Òåîðåìà Ìó÷íèêà äëÿ ñëîæíîñòè ñîãðàíè÷åíèåì íà ïàìÿòü ýòîé ãëàâå ìû äîêàæåì íåñêîëüêî âàðèàöèé òåîðåìû Ìó÷íèêà äëÿêîëìîãîðîâñêîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà èñïîëüçóåìóþ ïàìÿòü. Äëÿäîêàçàòåëüñòâà ïåðâîé âàðèàöèè ìîæíî èñïîëüçîâàòü ëþáîé ÿâíûé ýêñòðàêòîð.
Ôîðìóëèðîâêà è äîêàçàòåëüñòâî ñîîòâåòñòâóþùåé òåîðåìû ïðèâîäÿòñÿ â ðàçäåëå 4.1.  äîêàçàòåëüñòâå äðóãîé âàðèàöèè ìû ïðèìåíèìèäåþ äåðàíäîìèçàöèè: çàìåíèì ñëó÷àéíûé ãðàô, èñïîëüçîâàííûé â äîêàçàòåëüñòâå òåîðåìû Ìó÷íèêà, íà ïñåâäîñëó÷àéíûé, ïîëó÷åííûé ãåíåðàòîðîì ÍèñàíàÂèãäåðñîíà. Ïðè ýòîì ñâîéñòâî ýêñòðàêòîðà óæå íå ïîíàäîáèòñÿ: â äîêàçàòåëüñòâå áóäåò èñïîëüçîâàíî áîëåå ïðîñòîå ñâîéñòâî. Âðàçäåëå 4.2 ìû ñôîðìóëèðóåì ýòî ñâîéñòâî, äîêàæåì åãî ñîáëþäåíèå äëÿïñåâäîñëó÷àéíîãî ãðàôà è ïîäðîáíî îïèøåì ïðîöåññ äåðàíäîìèçàöèè.
Íàêîíåö, â ðàçäåëå 4.3 ìû èçëîæèì îáå âàðèàöèè äëÿ òåîðåìû ñ íåñêîëüêèìèóñëîâèÿìè.Ïîñêîëüêó â ýòîé ãëàâå èä¼ò ðå÷ü òîëüêî î ñëîæíîñòè ñ îãðàíè÷åíèåì íàïàìÿòü, âåðõíèé èíäåêñ â îáîçíà÷åíèÿõ ñëîæíîñòè áóäåò âñåãäà îáîçíà÷àòüîãðàíè÷åíèå íà èñïîëüçóåìóþ ïàìÿòü.4.1Äîêàçàòåëüñòâî ïðè ïîìîùè ÿâíîãî ýêñòðàêòîðàÄîêàæåì òåîðåìó Ìó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü âñëåäóþùåé ôîðìóëèðîâêå:Òåîðåìà 4.1. Ïóñòü äàíû äâîè÷íûå ñëîâà a è b, à òàêæå ÷èñëà n,k è s, äëÿ êîòîðûõ âåðíî Cs (a) < n è Cs (a|b) < k .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
