Диссертация (1103424), страница 10
Текст из файла (страница 10)
Ïóñòü ÷èñëà dè q òàêîâû, ÷òî ïðè ëþáîì l 6 k ñóùåñòâóåò (l, 0.25)-ýêñòðàêòîð48Extl : {0, 1}n × {0, 1}d → {0, 1}l , âû÷èñëèìûé íà ïàìÿòè q (äëÿ íåêîòîðîéçàðàíåå ôèêñèðîâàííîé óíèâåðñàëüíîé ìíîãîëåíòî÷íîé ìàøèíû Òüþðèíãà). Òîãäà ñóùåñòâóåò òàêîå ñëîâî p, ÷òî:2• CO(s+q+n ) (a|p, b) 6 d + O(log n);• |p| 6 k + O(log n);• CO(q) (p|a) 6 d + O(log n).Äîêàçàòåëüñòâî. Îñíîâíûå øàãè ïîâòîðÿþò äîêàçàòåëüñòâî òåîðåìûÌó÷íèêà, ïðåäñòàâëåííîå â ðàçäåëå 3.2, îäíàêî ïîòðåáóþòñÿ è äîïîëíèòåëüíûå ðàññóæäåíèÿ. Ñíà÷àëà ìû äîêàæåì îñëàáëåííóþ âåðñèþ òåîðåìû,â êîòîðîé ÷èñëî s äîáàâëåíî â ñëîæíîñòü èç ïåðâîãî íåðàâåíñòâà â êà÷å2ñòâå óñëîâèÿ: CO(s+q+n ) (a|p, b, s) 6 d + O(log n).
Çàòåì ìû ïîêàæåì, êàêèçáàâèòüñÿ îò ýòîãî äîïîëíèòåëüíîãî óñëîâèÿ.Ðàññìîòðèì ýêñòðàêòîð Extk , ñóùåñòâóþùèé ïî óñëîâèþ òåîðåìû. Íàïîìíèì, ÷òî ýëåìåíò åãî ïðàâîé äîëè íàçûâàåòñÿ ïëîõèì äëÿ ïîäìíîæåñòâàS ëåâîé äîëè, åñëè îí èìååò áîëüøå, ÷åì 2DK/M ñîñåäåé â S . (Ðàçìåð Síå áîëüøå K ). Ýëåìåíò x ∈ S íàçûâàåòñÿ îïàñíûì â S , åñëè âñå åãî ñîñåäèïëîõèå äëÿ S . Êàê è â èñõîäíîì äîêàçàòåëüñòâå, ðàçáåð¼ì äâà ñëó÷àÿ: êîãäàa ÿâëÿåòñÿ èëè íå ÿâëÿåòñÿ îïàñíûì â ìíîæåñòâå Sb,s = {x | Cs (x|b) < k}. îòëè÷èå îò èñõîäíîãî äîêàçàòåëüñòâà, îïàñíîñòü a íå ïðèâîäèò ê ïðîòèâîðå÷èþ, à òðåáóåò äîïîëíèòåëüíîé êîíñòðóêöèè.Ïåðâûé ñëó÷àé.
Ñëîâî a íå ÿâëÿåòñÿ îïàñíûì. Òîãäà ó íåãî åñòü ñîñåäp, íå ÿâëÿþùèéñÿ ïëîõèì. Ïîêàæåì, ÷òî îí èñêîìûé. Äåéñòâèòåëüíî, åãîäëèíà ñîîòâåòñòâóåò óñëîâèþ ïî ïîñòðîåíèþ. Äàëåå, äëÿ åãî îïèñàíèÿ ïðèèçâåñòíîì a íóæíî çàäàòü n è k , äîñòàòî÷íûå äëÿ îïèñàíèÿ Extk , è åãîíîìåð ñðåäè âñåõ ñîñåäåé a â ýòîì ãðàôå.
Äëÿ ïåðâîãî íóæíî íå áîëüøå3 log n áèòîâ, äëÿ âòîðîãî d áèòîâ. Ïîñêîëüêó ýêñòðàêòîð âû÷èñëèì íàïàìÿòè q , òî è âû÷èñëåíèå p ïðè ïîìîùè Extk ïîòðåáóåò òàêîé ïàìÿòè. Çàñ÷¼ò ïåðåõîäà ê îïòèìàëüíîìó ñïîñîáó îïèñàíèÿ ïàìÿòü âûðàñòåò íå áîëåå,÷åì â êîíñòàíòó ðàç, ÷òî è äàñò íóæíóþ â òðåòüåì íåðàâåíñòâå îöåíêó.Íàêîíåö, ïîêàæåì âûïîëíåíèå ïåðâîãî íåðàâåíñòâà. Êàê è ïðåæäå, ïðèèçâåñòíûõ b è s ìîæíî ïåðå÷èñëÿòü ìíîæåñòâî Sb,s , çàïóñêàÿ îïòèìàëüíûéñïîñîá îïèñàíèÿ íà âñåõ ïðîãðàììàõ äëèíû íå áîëüøå k (è b â êà÷åñòâå âòîðîãî àðãóìåíòà) è îãðàíè÷èâàÿ èñïîëüçóåìóþ èì ïàìÿòü âåëè÷èíîé s. Êàêòîëüêî î÷åðåäíîå ñëîâî ïîëó÷åíî, íóæíî ïðîâåðèòü, íå ÿâëÿåòñÿ ëè p îäíèì èç ñîñåäåé ýòîãî ñëîâà â ýêñòðàêòîðå Extk . Ïîñêîëüêó p õîðîøåå, ó íåãî49íå áîëüøå 2D ñîñåäåé â Sb,s , ïîýòîìó a ìîæíî çàäàòü íîìåðîì â îïèñàííîìïåðåáîðå.
Òàêèì îáðàçîì, ïîìèìî ïàðàìåòðîâ ýêñòðàêòîðà, çàíèìàþùèõ3 log n áèòîâ, ïîòðåáóåòñÿ d + O(1) áèòîâ èíôîðìàöèè, ÷òî ñîîòâåòñòâóåòçàÿâëåííîé îöåíêå. Ïðîâåðèì, ÷òî âûïîëíåíû òðåáîâàíèÿ ïî çàíèìàåìîéïàìÿòè. Äåéñòâèòåëüíî, äëÿ ñèìóëÿöèè âû÷èñëåíèé íà ïàìÿòè s òðåáóåòñÿ O(s + n) ÿ÷ååê: äîïîëíèòåëüíàÿ ïàìÿòü íóæíà äëÿ êîíòðîëÿ íåâûõîäàçà ïðåäåëû çîíû s (log s ÿ÷ååê), äëÿ êîíòðîëÿ îòñóòñòâèÿ çàöèêëèâàíèÿ(s ÿ÷ååê: íóæíî ñ÷èòàòü êîëè÷åñòâî øàãîâ è êîíòðîëèðîâàòü, ÷òî îíî íåïðåâûøàåò 2s , ïðåâûøåíèå ãîâîðèò î çàöèêëèâàíèè) è õðàíåíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ (O(n) ÿ÷ååê).
Òàêæå íóæíà ïàìÿòü q äëÿ âû÷èñëåíèÿçíà÷åíèÿ Extk . Ïðè ýòîì âû÷èñëåíèÿ, çàíèìàþùèå s ÿ÷ååê, ïðîâîäÿòñÿïîñëåäîâàòåëüíî, ïîýòîìó ìîæíî èñïîëüçîâàòü îäíó è òó æå çîíó. Òî æåâåðíî äëÿ âû÷èñëåíèé, çàíèìàþùèõ ïàìÿòü q . Ïåðåõîä ê îïòèìàëüíîìóñïîñîáó îïèñàíèÿ ìîæåò óâåëè÷èòü èñïîëüçîâàííóþ ïàìÿòü â êîíñòàíòíîå÷èñëî ðàç, îòêóäà è ïîëó÷àåòñÿ îáùàÿ îöåíêà O(s + q + n).1Âòîðîé ñëó÷àé. Ñëîâî a ÿâëÿåòñÿ îïàñíûì.
Âíà÷àëå ïîïðîáóåì ïðîâåñòè ðàññóæäåíèå àíàëîãè÷íî îñíîâíîé òåîðåìå è ïîêàæåì, ïî÷åìó ïîëó÷èòü ïðîòèâîðå÷èå àíàëîãè÷íûì îáðàçîì íå ïîëó÷èòñÿ. Çàìåòèì, ÷òîïëîõèå äëÿ Sb,s ñëîâà ìîæíî ïåðå÷èñëÿòü íà ïàìÿòè O(s + q + n), ïîëó÷èâ íà âõîä n, k , b è s. Äåéñòâèòåëüíî, äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåìíà ïàìÿòü ïåðå÷èñëåíèå ýêâèâàëåíòíî ðàñïîçíàâàíèþ, à ðàñïîçíàòü, ÿâëÿåòñÿ ëè y ïëîõèì, ìîæíî, ïåðå÷èñëÿÿ ýëåìåíòû Sb,s , çàòåì çàïóñêàÿ Extkíà ïîëó÷åííûõ ñëîâàõ ñî âñåìè âîçìîæíûìè âòîðûìè àðãóìåíòàìè è ñ÷èòàÿ, ñêîëüêî ðàç y âñòðåòèëîñü ñðåäè îáðàçîâ.
Îöåíêà íà èñïîëüçîâàííóþïàìÿòü ïðîâîäèòñÿ àíàëîãè÷íî ïåðâîìó ñëó÷àþ.Äàëåå, îïàñíûå â Sb,s ýëåìåíòû òàêæå ìîæíî ïåðå÷èñëÿòü íà ïàìÿòèO(s + q + n). Äåéñòâèòåëüíî, òàêîé ïàìÿòè õâàòèò äëÿ ïåðå÷èñëåíèÿ ñàìîãî Sb,s , âû÷èñëåíèÿ âñåõ ñîñåäåé êàæäîãî ñëîâà â Extk è âûÿñíåíèÿ ïðîêàæäîãî ñîñåäà, ÿâëÿåòñÿ ëè îí ïëîõèì. Ïîñêîëüêó îïàñíûõ ñëîâ íå áîëüøå 2εK , êàæäîå èç íèõ èìååò ñëîæíîñòü (óñëîâíî íà n, k , b, s) íå áîëüøåk + log ε + O(1).
Ê ñîæàëåíèþ, ïðîòèâîðå÷èÿ òóò íå ïîëó÷èòñÿ, äàæå åñëèâçÿòü ε = 1/n3 , êàê â èñõîäíîé òåîðåìå, âìåñòî 0.25 â òåêóùåé. Âåäü ìûäîêàçàëè ëèøü òî, ÷òî îïàñíûå ñëîâà èìåþò ìåíüøóþ ñëîæíîñòü ïðè áîëååìÿãêîì îãðàíè÷åíèè íà èñïîëüçîâàííóþ ïàìÿòü, à çäåñü íåò ïðîòèâîðå÷èÿ.Âîçìîæíî, áîëåå åñòåñòâåííî íàïèñàòüêîíñòàíòû â O(·)-îáîçíà÷åíèè1O(max{s, q, n})50, ÷òî äà¼ò òó æå îöåíêó ñ òî÷íîñòüþ äîSb,s = {x | Cs (x|b) < k}{0, 1}k<n{0, 1} îïàñíàÿ äëÿ Sb,s ,0íî íå äëÿ Sb,sâåðøèíàpa0Sb,sÏëîõèå âåðøèíû äëÿ Sb,s0Ïëîõèå âåðøèíû äëÿ Sb,s0 õîðîøèé äëÿ Sb,sñîñåä a ìíîæåñòâî îïàñíûõ âåðøèí äëÿ Sb,sÐèñ.
4.1: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà c îãðàíè÷åíèåì íà ïàìÿòü: âûáîð p äëÿîïàñíîãî a.Âìåñòî ýòîãî ìû âîñïîëüçóåìñÿ òåì, ÷òî îïàñíûõ ñëîâ íåìíîãî, è ïîñòðîèì äëÿ íèõ îòäåëüíóþ èòåðàòèâíóþ êîíñòðóêöèþ. Ìû âíà÷àëå ïîäðîáíî îïèøåì ïåðâûå øàãè, à ïîòîì âñþ êîíñòðóêöèþ. Îáîçíà÷èì ÷åðåç0ìíîæåñòâî îïàñíûõ ñëîâ äëÿ Sb,s . Åãî ðàçìåð íå áîëüøå 2εK = K/2.Sb,sÂâåä¼ì îáîçíà÷åíèÿ K1 = 2εK è k1 = log K1 . Çàìåòèì, ÷òî k1 < k , èðàññìîòðèì ýêñòðàêòîð Extk1 , ñóùåñòâóþùèé ïî óñëîâèþ òåîðåìû. Äàëåå,ðàññìîòðèì îïàñíûå ñëîâà âòîðîãî ïîðÿäêà, ò.å. îïàñíûå ñëîâà â ýêñ0.
Ïî ëåììå 3.2 îïàñíûõ ñëîâ âòîðîãî ïîòðàêòîðå Extk1 â ìíîæåñòâå Sb,s0ðÿäêà íå áîëüøå 2εK1 . Åñëè ñëîâî a (ëåæàùåå â Sb,s) íå ÿâëÿåòñÿ îïàñíûìâòîðîãî ïîðÿäêà, òî ó íåãî åñòü õîðîøèé ñîñåä â Extk1 , êîòîðûé ìîæíîâçÿòü â êà÷åñòâå èñêîìîãî p. (Äîêàçàòåëüñòâî ïîëíîñòüþ ïîâòîðÿåò ïåðâûé ñëó÷àé). Åñëè æå ñëîâî a ÿâëÿåòñÿ îïàñíûì âòîðîãî ïîðÿäêà, òî íóæíî00ïðèìåíèòü åù¼ îäíó èòåðàöèþ. Îáîçíà÷èì ÷åðåç Sb,sìíîæåñòâî îïàñíûõñëîâ âòîðîãî ïîðÿäêà.
Åãî ðàçìåð íå áîëüøå K2 = 2εK1 = K1 /2, ïîýòîìók2 = log K2 < k1 . Ðàññìîòðèì ýêñòðàêòîð Extk2 , ñóùåñòâóþùèé ïî óñëîâèþòåîðåìû.  í¼ì åñòü îïàñíûå ñëîâà òðåòüåãî ïîðÿäêà, ò.å. îïàñíûå ñëîâà00â ýêñòðàêòîðå Extk2 â ìíîæåñòâå Sb,s.
Ïî ëåììå 3.2 îïàñíûõ ñëîâ òðåòüåãî ïîðÿäêà íå áîëüøå 2εK2 . Åñëè ñëîâî a íå ÿâëÿåòñÿ îïàñíûì òðåòüåãîïîðÿäêà, òî ó íåãî åñòü õîðîøèé ñîñåä â Extk2 , êîòîðûé ìîæíî âçÿòü âêà÷åñòâå èñêîìîãî. Èíà÷å íóæíî ñäåëàòü åù¼ îäíó èòåðàöèþ, è òàê äàëåå.51Âûáîð äëÿ ïåðâîé èòåðàöèè ïðîèëëþñòðèðîâàí íà ðèñ. 4.1.Îïèøåì òåïåðü âñþ êîíñòðóêöèþ öåëèêîì. Ïóñòü ki = k − i, à Ki =(0)2ki = K/2i , ãäå i = 0, 1, . . . , k .
Îáîçíà÷èì ÷åðåç Sb,s ìíîæåñòâî Sb,s , à ÷å(i+1)(i)ðåç Sb,s ìíîæåñòâî îïàñíûõ ñëîâ â ìíîæåñòâå Sb,s â ýêñòðàêòîðå Extki ,ñóùåñòâóþùåì ïî óñëîâèþ òåîðåìû. Ïðèìåíÿÿ èíäóêòèâíî ëåììó 3.2, ïî(i)ëó÷àåì, ÷òî ìíîæåñòâî Sb,s ñîäåðæèò ìåíüøå 2ki ýëåìåíòîâ. Ïîñêîëüêó(k)kk = 0, ìíîæåñòâî Sb,s ïóñòî. Çíà÷èò, äëÿ íåêîòîðîãî i ñëîâî a ëåæèò(i)(i+1)â Sb,s , íî íå ëåæèò â Sb,s . Çíà÷èò, â ýêñòðàêòîðå Extki ó a åñòü õîðîøèéñîñåä p.
Äîêàæåì, ÷òî îí óäîâëåòâîðÿåò âñåì óñëîâèÿì òåîðåìû.Äåéñòâèòåëüíî, äëèíà ñëîâà p óäîâëåòâîðÿåò óñëîâèþ ïî ïîñòðîåíèþ.Ñëîæíîñòü p ïðè èçâåñòíîì a ìàëà: íóæíî çàäàòü n è ki äëÿ ïîñòðîåíèÿýêñòðàêòîðà (O(log n) áèòîâ), à òàêæå íîìåð p ñðåäè ñîñåäåé a (d áèòîâ),â ñóììå d + O(log n) áèòîâ. Íàêîíåö, ñëîæíîñòü a ïðè èçâåñòíûõ b, p è s(i)òàêæå ìàëà: íóæíî çàäàòü n, ki è íîìåð a ñðåäè ñîñåäåé p â ìíîæåñòâå Sb,s .(i+1)Ïîñêîëüêó a 6∈ Sb,s , ïîñëåäíèé íîìåð òðåáóåò íå áîëüøå d + O(1) áèòîâ,÷òî äà¼ò çàÿâëåííóþ îöåíêó.
Îäíàêî äëÿ ïîëó÷åíèÿ îöåíêè íà èñïîëüçî(i)âàííóþ ïàìÿòü íóæíî äîêàçàòü, ÷òî ìíîæåñòâî Sb,s ìîæíî ïåðå÷èñëèòü íàïàìÿòè O(s + q + n2 ).Äîêàæåì ïî èíäóêöèè, ÷òî âåðíî áîëåå ñèëüíîå óòâåðæäåíèå: ìíîæå(i)ñòâî Sb,s ìîæíî ïåðå÷èñëèòü íà ïàìÿòè O(s + q + n(i + 1)). Áàçà (äëÿi = 0) áûëà äîêàçàíà ïðè ðàññìîòðåíèè ïåðâîãî ñëó÷àÿ. Òàì æå, â íà÷àëåðàññìîòðåíèÿ âòîðîãî óòâåðæäåíèÿ ìû ôàêòè÷åñêè äîêàçàëè ñëåäóþùåå:åñëè ìíîæåñòâî S ïåðå÷èñëèìî íà ïàìÿòè r = O(s + q + n), òî è ìíîæåñòâî îïàñíûõ ýëåìåíòîâ â S â äàííîì ýêñòðàêòîðå ïåðå÷èñëèìî íà ïàìÿòèr + O(n). Èç ýòîãî óòâåðæäåíèÿ íåïîñðåäñòâåííî ñëåäóåò ïåðåõîä, ïîñêîëü(i+1)(i)êó Sb,s åñòü ìíîæåñòâî îïàñíûõ ýëåìåíòîâ ìíîæåñòâà Sb,s â ýêñòðàêòîðåExtki . Òàêèì îáðàçîì, èíäóêòèâíîå óòâåðæäåíèå äîêàçàíî, çíà÷èò ìíîæå(i)ñòâî Sb,s äåéñòâèòåëüíî ìîæíî ïåðå÷èñëèòü íà ïàìÿòè O(s + q + n2 ), èòåîðåìà â îñëàáëåííîé ôîðìóëèðîâêå äîêàçàíà.Èçáàâëåíèå îò äîïîëíèòåëüíîãî óñëîâèÿ òåîðåìû.
Òåïåðü ïîêàæåì, êàê äîêàçàòü òåîðåìó â èñõîäíîé ôîðìóëèðîâêå, ò.å. áåç äîáàâëåíèÿ sâ ïåðâóþ óñëîâíóþ ñëîæíîñòü. Çíàíèå s èñïîëüçîâàëîñü ïðè ïåðå÷èñëåíèèìíîæåñòâà Sb,s äëÿ îãðàíè÷åíèÿ çîíû ðàáîòû ïðîãðàìì. Õîòÿ ïðè íåèçâåñòíîì s ïåðå÷èñëèòü Sb,s íà ïàìÿòè O(s + n) â îáùåì ñëó÷àå íåâîçìîæíî, ìûïîêàæåì, êàê îáîéòèñü áåç òàêîãî ïåðå÷èñëåíèÿ.
Çàìåòèì, ÷òî Sb ÿâëÿåòñÿ52îáúåäèíåíèåì ìíîæåñòâ Sb,s ïî âñåì s = 1, 2, 3, . . . . Ïîýòîìó ìíîæåñòâî Sbìîæíî ïåðå÷èñëÿòü, ïåðå÷èñëÿÿ ïîñëåäîâàòåëüíî Sb,1 , Sb,2 , Sb,3 , è òàê äàëåå.Ìîæíî äîáèòüñÿ, ÷òîáû êàæäîå ñëîâî èç Sb âñòðåòèëîñü â ýòîì ïåðå÷èñëåíèè ðîâíî îäèí ðàç. Ýòî íóæíî äåëàòü òàê: çàïóñòèòü ïåðå÷èñëåíèå Sb,s ,çàïóñêàÿ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå âñå ïðîãðàììû äëèíû íå áîëüøåk íà âõîäå b íà ïàìÿòè s ñ êîíòðîëåì çàöèêëèâàíèÿ. Êàê òîëüêî íåêîòîðàÿïðîãðàììà z âûäàëà ðåçóëüòàò x, íóæíî ïðîâåðèòü, ÷òî îí íå âñòðå÷àëñÿðàíåå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
