Диссертация (1103424), страница 13
Текст из файла (страница 13)
À èìåííî, ïóñòü ñëîâîx íàõîäèòñÿ àëãîðèòìîì 4.4, ïîëó÷èâøèì íà âõîä n, k è q = s, ò.å. Gn (x)áóäåò êîäèðîâàòü èñêîìóþ ôóíêöèþ F . Ñëîæíîñòü x, òàêèì îáðàçîì, áóäåò íå áîëüøå ñëîæíîñòè òðîéêè (n, k, s), êîòîðàÿ ðàâíà O(log n + log s).62Ïîñêîëüêó àëãîðèòì íàõîæäåíèÿ x òðåáóåò ïàìÿòè O(s) + poly(n), ñëîæíîñòü x îñòàíåòñÿ òàêîé æå è ïðè äîáàâëåíèè òàêîãî îãðàíè÷åíèÿ íà ïàìÿòü. Íàêîíåö, åñëè x èçâåñòíî, òî âû÷èñëèòü çíà÷åíèå ïîðîæä¼ííîé èìôóíêöèè íà àðãóìåíòå a ìîæíî íà ïàìÿòè poly(n) â ñèëó òåîðåìû 2.36.Îáúåäèíèâ âñ¼ âìåñòå, ïîëó÷àåì îñëàáëåííîå òðåòüå óñëîâèå òåîðåìû:CO(s)+poly(n) (p|a) 6 O(log s) + O(log n). Âòîðîå óñëîâèå òàêæå âûïîëíåíîïî ïîñòðîåíèþ.
Îñòàëîñü äîêàçàòü ïåðâîå.Äëÿ äîêàçàòåëüñòâà ïåðâîãî óñëîâèÿ íàäî âîñïîëüçîâàòüñÿ òåì, ÷òîôóíêöèÿ F , çàêîäèðîâàííàÿ Gn (x), èìååò ìàëî êîëëèçèé. Ïðè èçâåñòíûõn, k è s ìîæíî íàéòè x, èñïîëüçîâàâ ïàìÿòü O(s) + poly(n). Ïðè èçâåñòíûõ b è s ìîæíî ïåðå÷èñëÿòü Sb,s , èñïîëüçóÿ ïàìÿòü O(s + n). Ïî óñëîâèþa ∈ Sb,s , à ïî ïîñòðîåíèþ F (a) = p è íå áîëåå 3n ýëåìåíòîâ Sb,s ïåðåõîäÿòâ p ïîä äåéñòâèåì F . Ïîýòîìó a ïðè èçâåñòíîì p ìîæíî çàäàòü åãî ïîðÿäêîâûì íîìåðîì â ïåðå÷èñëåíèè âñåõ ïðîîáðàçîâ p â ìíîæåñòâå Sb,s .  ñèëóìàëîãî ÷èñëà êîëëèçèé ýòîò íîìåð íå áîëüøå 3n, ïîýòîìó äëÿ çàäàíèÿ ïîðÿäêîâîãî íîìåðà äîñòàòî÷íî O(log n) áèòîâ.
Ñëîæèâ ïîëó÷åííûå îöåíêè,ïîëó÷èì, ÷òî C(a|p, b) 6 O(log n) + O(log s). Îãðàíè÷åíèå íà ïàìÿòü òàêæå áóäåò ðàâíî çàÿâëåííîìó, ïîñêîëüêó ïðè èçâåñòíîì z ïðîâåðêà òîãî, ÷òîF (z) = p, òðåáóåò ïîëèíîìèàëüíîé ïàìÿòè. Òàêèì îáðàçîì, ïåðâîå óñëîâèåòàêæå äîêàçàíî â îñëàáëåííîì âèäå.×òîáû ïîëó÷èòü òåîðåìó â èñõîäíîé ôîðìóëèðîâêå, äîñòàòî÷íî çàìåòèòü, ÷òî â êà÷åñòâå q âìåñòî s ìîæíî âçÿòü 2dlog se , ò.å.
ìèíèìàëüíóþ ñòåïåíü äâîéêè, íå ìåíüøóþ s. Äåéñòâèòåëüíî, àðãóìåíò x, íàéäåííûé äëÿòàêîãî îãðàíè÷åíèÿ q , ïîäõîäèò è äëÿ s, à ïàìÿòü, íåîáõîäèìàÿ äëÿ ïîèñêàx, âîçðàñòàåò íå áîëåå ÷åì âäâîå. Òåì ñàìûì, îöåíêà O(s) + poly(n) íà ýòóïàìÿòü îñòà¼òñÿ â ñèëå. Ñ äðóãîé ñòîðîíû, ñëîæíîñòü òàêîãî q ñíèæàåòñÿñ O(log s) äî O(log log s). Ñîîòâåòñòâóþùóþ çàìåíó ìîæíî ïðîâåñòè â ïåðâîì è òðåòüåì óñëîâèè, òåì ñàìûì çàâåðøèâ äîêàçàòåëüñòâî òåîðåìû. çàêëþ÷åíèå ïîêàæåì, ÷òî â ôîðìóëèðîâêå òåîðåìû 4.9 ìîæíî âîîáùåèçáàâèòüñÿ îò ñëàãàåìîãî O(log log s), ò.å.
âåðíà ñëåäóþùàÿ òåîðåìà:Òåîðåìà 4.10. Ïóñòü äàíû äâîè÷íûå ñëîâà 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 n);• |p| 6 k + O(log n);63• CO(s)+poly(n) (p|a) 6 O(log n).Äîêàçàòåëüñòâî. Ïðè s < 2poly(n) ýòà ôîðìóëèðîâêà ñëåäóåò èç òåîðåìû 4.9.
Ïîêàæåì, ÷òî ïðè áîëüøèõ s, à èìåííî ïðè s = 2Ω(n) , ìîæíîïðèìåíèòü òåîðåìó 4.1. Äåéñòâèòåëüíî, ïî òåîðåìå 2.19 ïðè âñåõ l < näëÿ d = O(log n) ñóùåñòâóåò (l, 0.25)-ýêñòðàêòîð Extl : {0, 1}n × {0, 1}d →{0, 1}l . Ýòîò ýêñòðàêòîð ìîæíî îïèñàòü äâîè÷íûì ñëîâîì èç l2n+d = 2O(n)áèòîâ. Åñëè òàêîå ñëîâî çàäàíî, ìîæíî ïðîâåðèòü, îïèñûâàåò ëè îíî ýêñòðàêòîð, èñïîëüçóÿ òàêóþ æå ïàìÿòü.
Äåéñòâèòåëüíî, äëÿ ïåðåáîðà ìíîæåñòâ S ⊂ {0, 1}n ðàçìåðà íå áîëüøå 2l äîñòàòî÷íî çîíû 2n+l , äëÿ ïåðåáîðàìíîæåñòâ Y ⊂ {0, 1}l äîñòàòî÷íî çîíû 2l , à äëÿ ïîäñ÷¼òà ð¼áåð ìåæäó Sè Y è ñðàâíåíèÿ ýòîãî ÷èñëà ñ |Y |D äîñòàòî÷íî äàæå ïîëèíîìèàëüíîé çîíû. Òàêèì îáðàçîì, ñâîéñòâî ýêñòðàêòîðà ìîæíî ðàñïîçíàòü, èñïîëüçóÿïàìÿòü 2O(n) = O(s). Çíà÷èò, íóæíûé ýêñòðàêòîð ìîæíî íàéòè, èñïîëüçóÿòàêîå êîëè÷åñòâî ïàìÿòè, à çíà÷èò, åãî çíà÷åíèå ìîæíî âû÷èñëèòü. Òåïåðüóòâåðæäåíèå òåîðåìû íåïîñðåäñòâåííî ñëåäóåò èç òåîðåìû 4.1.4.3Òåîðåìà ñ îãðàíè÷åíèåì íà ïàìÿòü äëÿ íåñêîëüêèõ óñëîâèé ýòîì ðàçäåëå ìû äîêàæåì âàðèàíò òåîðåìû Ìó÷íèêà ñ íåñêîëüêèìèóñëîâèÿìè äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü. À èìåííî, âíà÷àëå ìûäîêàæåì àíàëîãè òåîðåì 4.1 è 4.9 äëÿ äâóõ óñëîâèé, çàòåì âûâåäåì àíàëîãòåîðåìû 4.10 è â êîíöå ñôîðìóëèðóåì òåîðåìó äëÿ ïîëèíîìèàëüíîãî ÷èñëàóñëîâèé.4.3.1Äîêàçàòåëüñòâî ïðè ïîìîùè ÿâíîãî ýêñòðàêòîðàÌû áóäåì äîêàçûâàòü òåîðåìó â ñëåäóþùåé ôîðìóëèðîâêå:Òåîðåìà 4.11.
Ïóñòü äàíû äâîè÷íûå ñëîâà a, b è c, à òàêæå ÷èñëà n, k ,l è s, äëÿ êîòîðûõ âûïîëíåíî Cs (a) < n, Cs (a|b) < k è Cs (a|c) < l. Ïóñòü÷èñëà d è r òàêîâû, ÷òî ñóùåñòâóåò ïðåôèêñíûé (max{k, l}, 0.125)ýêñòðàêòîð Extmax{k,l} : {0, 1}n × {0, 1}d → {0, 1}max{k,l} , âû÷èñëèìûé íàïàìÿòè r. Òîãäà ñóùåñòâóþò ñëîâà p è q , îäíî èç êîòîðûõ ÿâëÿåòñÿíà÷àëîì äðóãîãî, äëÿ êîòîðûõ âûïîëíåíû íåðàâåíñòâà:2• CO(s+r+n ) (a|p, b) 6 d + O(log n);64•••••2CO(s+r+n ) (a|q, c) 6 d + O(log n);|p| 6 k + O(log n);|q| 6 l + O(log n);CO(r) (p|a) 6 d + O(log n);CO(r) (q|a) 6 d + O(log n).Äîêàçàòåëüñòâî.
Êàê è â òåîðåìå 4.1, áóäåì ñíà÷àëà äîêàçûâàòü îñëàáëåííîå óòâåðæäåíèå, ãäå â ïåðâûå äâå óñëîâíûå ñëîæíîñòè äîáàâëåíî s âêà÷åñòâå óñëîâèÿ.Íàïîìíèì, ÷òî ñëîâî x íàçûâàåòñÿ ñëàáî îïàñíûì äëÿ ìíîæåñòâà S ,ëåæàùåãî â ëåâîé äîëå äâóäîëüíîãî ãðàôà òèïà (n, m, d), åñëè õîòÿ áû ïîëîâèíà ñîñåäåé x èìåþò áîëüøå 2D ñîñåäåé âíóòðè S . Ïî ëåììå 3.6 åñëèãðàô ÿâëÿåòñÿ (k , ε)-ýêñòðàêòîðîì è |S| 6 K , òî êîëè÷åñòâî ñëàáî îïàñíûõ ñëîâ â S ìåíüøå 4εK . Ìû áóäåì ïðèìåíÿòü ýòó ëåììó ê ìíîæåñòâàìSb,s = {x | Cs (x|b) < k} è Tc,s = {x | Cs (x|c) < l}.
Êàê è â òåîðåìå 4.1,íåëüçÿ äîêàçàòü, ÷òî a íå ÿâëÿåòñÿ ñëàáî îïàñíûì â ìíîæåñòâàõ Sb,s è Tc,s ,ïîýòîìó ìû èñïîëüçóåì îòäåëüíóþ èòåðàòèâíóþ êîíñòðóêöèþ äëÿ ñëàáîîïàñíûõ ñëîâ. Òðóäíîñòü ñîñòîèò â òîì, ÷òî ñëîâî a äîëæíî íå áûòü ñëàáî îïàñíûì îäíîâðåìåííî äëÿ äâóõ ðàçíûõ ìíîæåñòâ, ïðè÷¼ì îïàñíîñòüèçìåðÿåòñÿ îòíîñèòåëüíî äâóõ ðàçíûõ ýêñòðàêòîðîâ, îäèí èç êîòîðûõ ÿâëÿåòñÿ ïðåôèêñîì äðóãîãî. Êîíñòðóêöèÿ áóäåò ïîõîæà íà êîíñòðóêöèþ èçòåîðåìû 4.1, ñî ñëåäóþùèì îòëè÷èåì: â êà÷åñòâå ýêñòðàêòîðà ñ ìåíüøèìk ìû âñåãäà áóäåì áðàòü ïðåôèêñ èñõîäíîãî. Îïèøåì ïðîöåññ íàõîæäåíèÿýòèõ äâóõ ìíîæåñòâ ôîðìàëüíî.Îáîçíà÷èì ÷åðåç ki è lj ÷èñëà k − i è l − j ñîîòâåòñòâåííî.
Äëÿ κ <max{k, l} îáîçíà÷èì ÷åðåç Extκ ïðåôèêñ ýêñòðàêòîðà Extmax{k,l} äëèíû κ.Çàìåòèì, ÷òî ýòîò ïðåôèêñ âû÷èñëÿåòñÿ íà ïàìÿòè r ïðè ëþáîì çàäàííîì κ. (Äåéñòâèòåëüíî, íà òàêîé ïàìÿòè ìîæíî âû÷èñëèòü çíà÷åíèå âñåãîýêñòðàêòîðà, à âçÿòèå ïðåôèêñà òðåáóåò ñîâñåì íåáîëüøîé ïàìÿòè). Äà(0)(0)ëåå, ââåä¼ì îáîçíà÷åíèÿ Sb,s = Sb,s è Tc,s = Tc,s . Ïî èíäóêöèè îïðåäåëèì(i+1)Sb,s(i)êàê ìíîæåñòâî ñëàáî îïàñíûõ ñëîâ äëÿ ìíîæåñòâà Sb,s â ýêñòðàêòî(j+1)(j)ðå Extki è Tc,sêàê ìíîæåñòâî ñëàáî îïàñíûõ ñëîâ äëÿ ìíîæåñòâà Tc,s âýêñòðàêòîðå Ext lj .
 ñèëó ëåììû 3.6 è âûáîðà ε ìîæíî ïî èíäóêöèè äîêà (i) (j) çàòü, ÷òî Sb,s < K/2i = 2ki è Tc,s < L/2j = 2lj . Ïîñêîëüêó ïðè i = k(k)(l)è j = l âåëè÷èíû ki è lj ðàâíû íóëþ, ïîëó÷àåì, ÷òî ìíîæåñòâà Sb,s è Tc,s650Sb,s ìíîæåñòâî îïàñíûõ âåðøèí äëÿ Sb,sSb,s = {x | Cs (x|b) < k}{0, 1}k{0, 1}<n îïàñíàÿ äëÿ Sb,s ,0íî íå äëÿ Sb,sâåðøèíàaÏëîõèå âåðøèíû äëÿ Sb,s0Ïëîõèå âåðøèíû äëÿ Sb,s0p õîðîøèé äëÿ Sb,sñîñåä aq ïðåôèêñ p, õîðîøèé äëÿ Tc,sÏëîõèå âåðøèíû äëÿ Tc,sTc,s = {x | Cs (x|c) < l}Ðèñ. 4.3: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà c îãðàíè÷åíèåì íà ïàìÿòü: âûáîð p è q äëÿîïàñíîãî a.(i)(j)(i+1)(j+1)ïóñòû.
Çíà÷èò, íàéäóòñÿ òàêèå i è j , ÷òî a ∈ Sb,s \ Sb,s è a ∈ Tc,s \ Tc,s .Çàôèêñèðóåì ýòè i è j äëÿ äàëüíåéøåãî.(i)Ïîñêîëüêó ñëîâî a íå ÿâëÿåòñÿ ñëàáî îïàñíûì äëÿ ìíîæåñòâà Sb,s â ýêñòðàêòîðå Extki , òî áîëüøå ïîëîâèíû ñîñåäåé a â ýòîì ýêñòðàêòîðå èìåþò(i)ìåíüøå 2D ñîñåäåé âíóòðè ìíîæåñòâà Sb,s . À ïîñêîëüêó a íå ÿâëÿåòñÿ ñëà(j)áî îïàñíûì è äëÿ ìíîæåñòâà Tc,s â ýêñòðàêòîðå Extlj , òî áîëüøå ïîëîâèíûñîñåäåé a â ýòîì ýêñòðàêòîðå èìåþò ìåíüøå 2D ñîñåäåé âíóòðè ìíîæåñòâà(j)Tc,s . Ïîñêîëüêó ýêñòðàêòîðû Extki è Extlj ÿâëÿþòñÿ ïðåôèêñàìè ýêñòðàêòîðà Extmax{ki ,lj } , ìîæíî çàêëþ÷èòü, ÷òî ñóùåñòâóåò ñîñåä a â ïîñëåäíåìýêñòðàêòîðå ñî ñëåäóþùèìè ñâîéñòâàìè: åãî ïðåôèêñ äëèíû ki èìååò ìåíü(i)øå 2D ñîñåäåé âíóòðè ìíîæåñòâà Sb,s â ýêñòðàêòîðå Extki , à åãî ïðåôèêñ(j)äëèíû lj èìååò ìåíüøå 2D ñîñåäåé âíóòðè ìíîæåñòâà Tc,s â ýêñòðàêòîðåExtlj .
Îáîçíà÷èì ïðåôèêñ ýòîãî ñîñåäà äëèíû ki ÷åðåç p, à ïðåôèêñ äëèíûlj ÷åðåç q . ßñíî, ÷òî îäíî èç ñëîâ p è q áóäåò ïðåôèêñîì äðóãîãî, à áîëååäëèííîå èç íèõ áóäåò ïðåôèêñîì èñõîäíîãî ñîñåäà. Ïîêàæåì, ÷òî ýòè p èq èñêîìûå.Äåéñòâèòåëüíî, óñëîâèå íà äëèíû p è q ïîëó÷àþòñÿ ïî ïîñòðîåíèþ: |p| =k − i 6 k è |q| = l − j 6 l. Îöåíêà íà óñëîâíûå ñëîæíîñòè p è q ïðèèçâåñòíîì a òàêæå ïðîñòà: íóæíî çàäàòü n è ki (ñîîòâåòñòâåííî, n è lj ), íà66÷òî íóæíî O(log n) áèòîâ, è íîìåð p (ñîîòâåòñòâåííî, q ) ñðåäè ñîñåäåé a âýêñòðàêòîðå Extki (ñîîòâåòñòâåííî, Extlj ), íà ÷òî íóæíî d áèòîâ.
Ïîñêîëüêóýòè ýêñòðàêòîðû âû÷èñëÿþòñÿ íà ïàìÿòè r, ïîëó÷àåì íóæíîå îãðàíè÷åíèåíà ïàìÿòü. Ñóììèðóÿ, ïîëó÷àåì CO(r) (p|a) 6 d + O(log n) è CO(r) (q|a) 6d + O(log n), ÷òî è òðåáîâàëîñü.Òåïåðü ïîñòðîèì îöåíêè íà ñëîæíîñòè a ïðè óñëîâèÿõ p, b è s è ïðèóñëîâèÿõ q , c è s. Îöåíêè ïîëó÷àþòñÿ îäèíàêîâûì ñïîñîáîì, ïîýòîìó îïèøåì ïîäðîáíî òîëüêî ïåðâóþ. Çàìåòèì, ÷òî ïðè èçâåñòíûõ îãðàíè÷åíèè(i)íà çîíó s, ñëîâå b è èíäåêñå i ìîæíî ïåðå÷èñëÿòü Sb,s , èñïîëüçóÿ ïàìÿòüO(s+r+n2 ). Ýòîò ôàêò äîêàçûâàåòñÿ òî÷íî òàê æå, êàê àíàëîãè÷íîå óòâåðæäåíèå â òåîðåìå 4.1.
Äàëåå, äëÿ îïèñàíèÿ a íåîáõîäèìî óêàçàòü n, k , i è(i)íîìåð a ñðåäè ñîñåäåé p â ìíîæåñòâå Sb,s äëÿ ýêñòðàêòîðà Extki .  ñèëóòîãî, ÷òî p íå ÿâëÿåòñÿ ñëàáî îïàñíûì äëÿ a, îïèñàíèå óêàçàííîãî íîìåðàòðåáóåò íå áîëåå d+1 áèòà, à äëÿ çàäàíèÿ îñòàëüíûõ ïàðàìåòðîâ äîñòàòî÷íî(i)O(log n) áèòîâ. Íà ïàìÿòè O(s + r + n2 ) ìîæíî ïåðå÷èñëÿòü ìíîæåñòâî Sb,sè äëÿ êàæäîãî ïîëó÷åííîãî ñëîâà w âû÷èñëÿòü âñå çíà÷åíèÿ ýêñòðàêòîðà(íà ïàìÿòè r, ïðè÷¼ì ìîæíî èñïîëüçîâàòü òîò æå ó÷àñòîê ïàìÿòè), çàòåìïðîâåðÿòü, âñòðå÷àåòñÿ ëè p ñðåäè íèõ, è âêëþ÷àòü w â ïåðå÷èñëåíèå, åñëèâñòðå÷àåòñÿ.
Ñëîâî a áóäåò çàäàíî ñâîèì íîìåðîì â ýòîì ïåðå÷èñëåíèè,2ïîýòîìó CO(s+r+n ) (a|p, b, s) 6 d + O(log n), êàê è áûëî çàÿâëåíî.Èçáàâèòüñÿ îò ïàðàìåòðà s â ïîñëåäíåé ñëîæíîñòè, ìîæíî òàê æå, êàê(i)(i)â òåîðåìå 4.1: íóæíî ïåðå÷èñëÿòü ìíîæåñòâî Sb = ∪∞s=1 Sb,s ïðè ïîìîùèàëãîðèòìà 4.2. Òîãäà êàæäîå ñëîâî â ïåðå÷èñëåíèè âñòðåòèòñÿ ðîâíî îäèí(i)ðàç è ê ìîìåíòó ïåðå÷èñëåíèÿ âñåõ ñëîâ èç Sb,s áóäåò èñïîëüçîâàíà ïàìÿòüO(s + r + n2 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
