Диссертация (1103424), страница 14
Текст из файла (страница 14)
Ïðè èñïîëüçîâàíèè òàêîãî ïåðå÷èñëåíèÿ áîëüøå íåò íåîáõîäèìîñòè äîáàâëÿòü s â îïèñàíèå a, òàêèì îáðàçîì òåîðåìà äîêàçûâàåòñÿ âèñõîäíîé ôîðìóëèðîâêå.Çàâåðøèì ïîäðàçäåë ñëåäñòâèåì èç òåîðåìû 4.3, ïîëó÷åííûì ñ èñïîëüçîâàíèåì èçâåñòíûõ êîíñòðóêöèé ýêñòðàêòîðîâ:Ñëåäñòâèå 4.12.
Ïóñòü äàíû äâîè÷íûå ñëîâà a, b è c, à òàêæå ÷èñëà n,k , l è s, äëÿ êîòîðûõ âûïîëíåíî Cs (a) < n, Cs (a|b) < k è Cs (a|c) < l. Òîãäàñóùåñòâóþò ñëîâà p è q , îäíî èç êîòîðûõ ÿâëÿåòñÿ íà÷àëîì äðóãîãî, äëÿêîòîðûõ âûïîëíåíû íåðàâåíñòâà:• CO(s+poly(n)) (a|p, b) 6 O(log3 n);• CO(s+poly(n)) (a|q, c) 6 O(log3 n);67••••|p| 6 k + O(log n);|q| 6 l + O(log n);Cpoly(n) (p|a) 6 O(log3 n);Cpoly(n) (q|a) 6 O(log3 n).Äîêàçàòåëüñòâî. Óòâåðæäåíèå ïîëó÷àåòñÿ íåïîñðåäñòâåííîé ïîäñòàíîâêîé ýêñòðàêòîðà, ñóùåñòâóþùåãî ïî ñëåäñòâèþ 2.22, â òåîðåìó 4.3.Çàìå÷àíèå 4.13. Àíàëîãè÷íî òåîðåìàì ñ îäíèì óñëîâèåì, ìîæíî äîáèòüñÿ, ÷òîáû p áûëî äëèíû ðîâíî k , à q áûëî äëèíû ðîâíî l, ëèáî ÷òîáû CO(s+poly(n)) (a|p, b) 6 O(1) è CO(s+poly(n)) (a|q, c) 6 O(1), íî ïðè ýòîì|p| 6 k + O(log3 n) è |q| 6 l + O(log3 n).  îáîèõ ñëó÷àÿõ ðàñòóò Cpoly(n) (p|a)è Cpoly(n) (q|a), îñòàâàÿñü ïîðÿäêà log3 n.4.3.2ÄîêàçàòåëüñòâîÂèãäåðñîíàïðèïîìîùèãåíåðàòîðàÍèñàíàÇäåñü ìû äîêàæåì òåîðåìó Ìó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íàïàìÿòü è äâóõ óñëîâèé ïðè ïîìîùè ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà.
Îáùèé õîä ðàññóæäåíèé áóäåò ïîâòîðÿòü èçëîæåíèå ðàçäåëà 4.2, ïîýòîìóìû îïóñòèì íåêîòîðûå ïîäðîáíîñòè. Íàì âíîâü áóäåò äîñòàòî÷íî îäíîéõåø-ôóíêöèè: ìû ñôîðìóëèðóåì íóæíîå ñâîéñòâî ýòîé ôóíêöèè, çàòåìäîêàæåì, ÷òî îíî ðàñïîçíà¼òñÿ ñõåìàìè êîíñòàíòíîé ãëóáèíû è ïîëèíîìèàëüíîãî ðàçìåðà, èç ÷åãî ñäåëàåì âûâîä, ÷òî îáúåêò ñ íóæíûì ñâîéñòâîìâñòðå÷àåòñÿ ñðåäè çíà÷åíèé ãåíåðàòîðà.Ïóñòü çàäàíû íåêîòîðàÿ ôóíêöèÿ F : {0, 1}n → {0, 1}k è ÷èñëî l 6 k .Ïóñòü òàêæå çàäàíû ñèñòåìà ìíîæåñòâ S , ñîñòîÿùàÿ èç íå áîëåå ÷åì 2n+kïîäìíîæåñòâ {0, 1}n ðàçìåðà íå áîëåå 2k , è ñèñòåìà ìíîæåñòâ T , ñîñòîÿùàÿ èç íå áîëåå ÷åì 2n+l ïîäìíîæåñòâ {0, 1}n ðàçìåðà íå áîëåå 2l . Áóäåìãîâîðèòü, ÷òî F èìååò ìåíüøå m êîëëèçèé îòíîñèòåëüíî S è T , åñëè äëÿëþáîãî x ∈ {0, 1}k è ëþáîãî S ∈ S ýëåìåíò x èìååò ìåíåå m ïðîîáðàçîâ âíóòðè S , à òàêæå äëÿ ëþáîãî y ∈ {0, 1}l è ëþáîãî T ∈ T ìíîæåñòâîy · {0, 1}k−l èìååò ìåíåå m ïðîîáðàçîâ âíóòðè T .Äîêàæåì ñëåäóþùóþ òåîðåìó ñóùåñòâîâàíèÿ, àíàëîãè÷íóþ òåîðåìå 4.4:Òåîðåìà 4.14.
Ñóùåñòâóåò ïîëèíîì p(n), òàêîé ÷òî äëÿ ëþáûõ l 6 k 6n è ëþáûõ ñèñòåì S è T , ñîñòîÿùèõ èç íå áîëåå ÷åì 2n+k (ñîîòâ., 2n+l )ïîäìíîæåñòâ {0, 1}n , êàæäîå èç êîòîðûõ èìååò ðàçìåð íå áîëüøå 2k68(ñîîòâ., 2l ), õîòÿ áû ïîëîâèíà âñåõ ôóíêöèé F : {0, 1}n → {0, 1}k èìåþòìåíüøå p(n) êîëëèçèé îòíîñèòåëüíî S è T .Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà âíîâü èñïîëüçóåì âåðîÿòíîñòíûéìåòîä. À èìåííî, äîêàæåì, ÷òî ñëó÷àéíàÿ ôóíêöèÿ, çíà÷åíèÿ êîòîðîé âûáðàíû ðàâíîìåðíî è íåçàâèñèìî, îáëàäàåò íóæíûì ñâîéñòâîì ñ âåðîÿòíîñòüþ íå ìåíüøå 1/2. Äëÿ ýòîãî îöåíèì ñâåðõó âåðîÿòíîñòü îáðàòíîãîñîáûòèÿ.Åñëè ôóíêöèÿ F íå ñîîòâåòñòâóåò óñëîâèþ äëÿ S è T , òî äëÿ íåêîòîðîãîS ∈ S èëè äëÿ íåêîòîðîãî T ∈ T îíà èìååò õîòÿ áû m êîëëèçèé. Âåðîÿòíîñòü òîãî, ÷òî êîëëèçèé õîòÿ áû m äëÿ ôèêñèðîâàííîãî S ∈ S , íå ïðåâûmøàåò 2k C2mk 21k : çäåñü 2k êîëè÷åñòâî âñåâîçìîæíûõ x, C2mk âåðõíÿÿmîöåíêà êîëè÷åñòâà âñåâîçìîæíûõ m-ýëåìåíòûõ ïîäìíîæåñòâ S , 21kâåðîÿòíîñòü òîãî, ÷òî íà âñåõ m ýëåìåíòàõïîäìíîæåñòâà ôóíêöèÿ ðàâíàmk2( )x.
Èñïîëüçóÿ íåðàâåíñòâî C2mk 6 m! , ïîëó÷åííóþ âåðîÿòíîñòü ìîæíî îöå2kíèòü âåëè÷èíîé m!. Àíàëîãè÷íî, âåðîÿòíîñòü òîãî, ÷òî êîëëèçèé õîòÿ áû k−l mmm äëÿ ôèêñèðîâàííîãî T ∈ T , íå ïðåâûøàåò 2l C2ml 22k= 2l C2ml 21l .2k−l2k k−lâåðîÿòíîñòü òîãî, ÷òî çíà÷åíèå ôóíêöèè ïîïàä¼ò â ìíîæåñòâîy · {0, 1} äëÿ ôèêñèðîâàííîãî y . Ïðèìåíèâ àíàëîãè÷íîå íåðàâåíñòâî äëÿ2l÷èñëà ñî÷åòàíèé, îöåíèì ýòó âåðîÿòíîñòü âåëè÷èíîé m!. Ïðîñóììèðîâàâkln+2k+122òåïåðü ïî âñåì S è T , ïîëó÷àåì îöåíêó 2n+k m! + 2n+l m! 6 2 m! .
Åñëèâçÿòü m = 4n, òî ýòà âåëè÷èíà ìåíüøå îäíîé âòîðîé (ïðè n > 1), çíà÷èò âåðîÿòíîñòü òîãî, ÷òî F íå ïîäõîäèò, ìåíüøå îäíîé âòîðîé, à çíà÷èò,áîëüøå ïîëîâèíû ôóíêöèé F ïîäõîäÿò, ÷òî è òðåáîâàëîñü.ÇäåñüÄàëåå, äîêàæåì, ÷òî ñâîéñòâî ìàëîãî ÷èñëà êîëëèçèé ðàñïîçíà¼òñÿ ñõåìîé êîíñòàíòíîé ãëóáèíû è ïîëèíîìèàëüíîãî ðàçìåðà. Ýòà ñõåìà ïðàêòè÷åñêè ïîëíîñòüþ ïîâòîðÿåò ñõåìó, îïèñàííóþ â äîêàçàòåëüñòâå òåîðåìû 4.5,ïîýòîìó ìû íå áóäåì ïðèâîäèòü å¼ ïîëíîñòüþ, à îïèøåì êðàòêî. Ìàëîå÷èñëî êîëëèçèé â êàæäîì S ∈ S ïðîâåðÿåòñÿ òî÷íî òàê æå, êàê è â òåîðåìå 4.5 (ñì. ðèñ.
4.2). Ìàëîå ÷èñëî êîëëèçèé â êàæäîì T ∈ T ïðîâåðÿåòñÿ ñíåáîëüøèì îòëè÷èåì: â ñàìîì íà÷àëå âìåñòî ñîâïàäåíèÿ çíà÷åíèé F (xi ) èF (xj ) ïðîâåðÿåòñÿ, ÷òî ñîâïàäàþò èõ ïðåôèêñû äëèíû l. Äëÿ ýòîãî íóæíîáðàòü êîíúþíêöèþ ýêâèâàëåíöèé íå ïî âñåì áèòàì, à òîëüêî ïî ïåðâûìl. Íà ñëåäóþùèõ ýòàïàõ ñõåìà âûãëÿäèò òî÷íî òàê æå, êàê è ðàíüøå.
Ïîëèíîìèàëüíûé ðàçìåð, êîíñòàíòíàÿ ãëóáèíà è êîððåêòíîñòü ðàáîòû ñõåìû69òàêæå äîêàçûâàþòñÿ àíàëîãè÷íî.Êàê ñëåäñòâèå, ïî ëåììå 2.37 ïîëó÷èì, ÷òî õåø-ôóíêöèè ñ ìàëûì ÷èñëîì êîëëèçèé îòíîñèòåëüíî S è T íå òîëüêî ñóùåñòâóþò, íî è âñòðå÷àþòñÿñðåäè çíà÷åíèé ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà.Òåïåðü â êà÷åñòâå ñèñòåì S è T ìû âîçüì¼ì ñèñòåìûnqS | ∃b∃q < q |b| < n ∧ S = {x ∈ {0, 1} | C (x|b) < k}èT | ∃c∃q < q |c| < n ∧ T = {x ∈ {0, 1}n | Cq (x|c) < l}ñîîòâåòñòâåííî. Àíàëîãè÷íî óòâåðæäåíèþ 4.7 ëåãêî ïîêàçàòü, ÷òî ýòè ñèñòåìû óäîâëåòâîðÿþò íóæíûì îãðàíè÷åíèÿì íà ðàçìåðû.Àíàëîãè÷íî òåîðåìå 4.8 ìîæíî äîêàçàòü, ÷òî àðãóìåíò x, ïðè êîòîðîìçíà÷åíèå ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà Gn (x) êîäèðóåò ôóíêöèþ, ó êîòîðîé ìåíüøå 4n êîëëèçèé îòíîñèòåëüíî S è T , ìîæíî íàéòè íà ïàìÿòèO(q) + poly(n). Àëãîðèòì áóäåò ïî÷òè ïîëíîñòüþ ïîâòîðÿòü àëãîðèòì 4.4ñ îäíèì îòëè÷èåì: ñ÷èòàÿ êîëëèçèè âíóòðè ìíîæåñòâà T ∈ T , â ñòðîêå 14íóæíî ñðàâíèâàòü íå çíà÷åíèÿ F öåëèêîì, à èõ ïðåôèêñû äëèíû l.Íàêîíåö, äîêàæåì òåîðåìó Ìó÷íèêà äëÿ äâóõ óñëîâèé â ñëåäóþùåéôîðìóëèðîâêå:Òåîðåìà 4.15.
Ïóñòü äàíû äâîè÷íûå ñëîâà 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 log s) + O(log n);CO(s)+poly(n) (a|q, c) 6 O(log log s) + O(log n);|p| 6 k + O(log n);|q| 6 l + O(log n);CO(s)+poly(n) (p|a) 6 O(log log s) + O(log n);CO(s)+poly(n) (q|a) 6 O(log log s) + O(log n).Äîêàçàòåëüñòâî. Îáùèé õîä ðàññóæäåíèé ïîâòîðÿåò äîêàçàòåëüñòâî òåîðåìû 4.9. Áåç îãðàíè÷åíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî l 6 k .
ÈñïîëüçóÿO(log n)+O(log s) áèòîâ, ìîæíî îïèñàòü àðãóìåíò x, íà êîòîðîì ãåíåðàòîðâîçâðàùàåò ôóíêöèþ ñ ìàëûì ÷èñëîì êîëëèçèé. Ñëîâî p áóäåò çíà÷åíèåìýòîé ôóíêöèè íà ñëîâå a, à ñëîâî q ïðåôèêñîì ñëîâà p äëèíû l. Ïðè ýòîì70ïàìÿòè O(s) + poly(n) äîñòàòî÷íî, ÷òîáû íàéòè è íóæíûé àðãóìåíò ãåíåðàòîðà, è çíà÷åíèå ñãåíåðèðîâàííîé ôóíêöèè íà ñëîâå a. Òàêèì îáðàçîì,äîêàçàíû óñëîâèÿ 36 (ñ çàìåíîé O(log log s) íà O(log s)). Ïåðâîå óñëîâèåñëåäóåò èç òîãî, ÷òî ñëîâî p èìååò ìàëî ïðîîáðàçîâ âíóòðè Sb,s , ïîýòîìóïðè èçâåñòíûõ b, s è çàäàííîé õåø-ôóíêöèè ìîæíî çàäàòü a åãî íîìåðîìâ ïåðå÷èñëåíèè ýòèõ ïðîîáðàçîâ.
Âòîðîå óñëîâèå ñëåäóåò èç òîãî, ÷òî ìíîæåñòâî âñåõ ïðîäîëæåíèé q èìååò ìàëî ïðîîáðàçîâ âíóòðè Tc,s , ïîýòîìóïðè èçâåñòíûõ c, s è õåø-ôóíêöèè ñëîâî a âíîâü ìîæíî çàäàòü åãî íîìåðîì ñðåäè ýòèõ ïðîîáðàçîâ. Òàêèì îáðàçîì, óñëîâèÿ 12 òàêæå äîêàçàíû ñçàìåíîé O(log log s) íà O(log s).Íàêîíåö, ìîæíî çàìåíèòü O(log s) íà O(log log s), åñëè â êà÷åñòâå îãðàíè÷åíèÿ íà ïàìÿòü âìåñòî s áðàòü ìèíèìàëüíóþ ñòåïåíü äâîéêè, íå ìåíüøóþ s.4.3.3Êîìïèëÿöèÿ äâóõ ïîäõîäîâ è òåîðåìà äëÿ ïîëèíîìèàëüíîãî ÷èñëà óñëîâèéÊàê è ðàíüøå, ìîæíî îáúåäèíèòü äâà ïîäõîäà è äîêàçàòü òàêîé àíàëîãòåîðåìû 4.10.Òåîðåìà 4.16.
Ïóñòü äàíû äâîè÷íûå ñëîâà 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).Äîêàçàòåëüñòâî. Äëÿ îãðàíè÷åíèé íà çîíó, ìåíüøèõ 2poly(n) , ìîæíî ïðèìåíèòü òåîðåìó 4.15: â ýòîì ñëó÷àå O(log log s) = O(log n). Äëÿ áîëüøèõîãðàíè÷åíèé íà çîíó ìîæíî ïðèìåíèòü òåîðåìó 4.11: èñïîëüçóÿ ïàìÿòü2poly(n) , ìîæíî âû÷èñëèòü îïòèìàëüíûé ïðåôèêñíûé ýêñòðàêòîð.71Íàêîíåö, ìîæíî ðàñïðîñòðàíèòü òåîðåìó íà ïîëèíîìèàëüíîå ÷èñëîóñëîâèé.
 ýòîì ñëó÷àå ðàáîòàþò îáà ïîäõîäà: è èñïîëüçîâàíèå ÿâíîãî ïðåôèêñíîãî ýêñòðàêòîðà, è èñïîëüçîâàíèå ãåíåðàòîðà ïñåâäîñëó÷àéíûõ ÷èñåë.  ïåðâîì ñëó÷àå èòåðàòèâíàÿ êîíñòðóêöèÿ ïðîâîäèòñÿ îòäåëüíî äëÿêàæäîãî óñëîâèÿ, âî âòîðîì ñëó÷àå ó õåø-ôóíêöèè äîëæíî áûòü ìàëî êîëëèçèé äëÿ êàæäîãî èç ìíîæåñòâ ïðîñòûõ ñëîâ. Áîëåå òîãî, ïðè èñïîëüçîâàíèè ãåíåðàòîðà ìîæíî äîêàçàòü àíàëîã òåîðåìû íå òîëüêî äëÿ ïîëèíîìèàëüíîãî, íî è äëÿ ýêñïîíåíöèàëüíîãî ÷èñëà óñëîâèé. Ïîñêîëüêó ïîñëåäíèéðåçóëüòàò äîñòàòî÷íî íåîæèäàííûé, òî ìû åãî îïèøåì ïîäðîáíî, à ïåðâûéïîäõîä ðàçáåð¼ì êðàòêî.Èòàê, ïðè ïîìîùè ÿâíûõ ýêñòðàêòîðîâ ìîæíî äîêàçàòü ñëåäóþùèé àíàëîã òåîðåìû 3.7:Òåîðåìà 4.17. Ïóñòü äàíû ÷èñëà n, s, r = poly(n) è k1 , .
. . , kr è äâîè÷íûå ñëîâà a, b1 , . . . , br , òàêèå ÷òî Cs (a) < n è Cs (a|bi ) < ki ïðè âñåõi = 1, . . . , r. Ïóñòü ÷èñëà d è q òàêîâû, ÷òî ñóùåñòâóåò ïðåôèêñíûé1(maxi {ki }, 4r)-ýêñòðàêòîð Extmaxi {ki } : {0, 1}n × {0, 1}d → {0, 1}maxi {ki } , âû÷èñëèìûé íà ïàìÿòè q . Òîãäà ñóùåñòâóþò ñëîâà p1 , . . . , pr , äëÿ êîòîðûõâûïîëíåíû ñëåäóþùèå óñëîâèÿ:••••Âñå pi ÿâëÿþòñÿ ïðåôèêñàìè îäíîãî è òîãî æå ñëîâà;2CO(s+q+n ) (a|pi , bi ) 6 d + O(log n) ïðè âñåõ i = 1, .
. . , r;|pi | 6 ki + O(log n) ïðè âñåõ i = 1, . . . , r;CO(q) (pi |a) 6 d + O(log n) ïðè âñåõ i = 1, . . . , r.Èäåÿ äîêàçàòåëüñòâà îñòà¼òñÿ ïðåæíåé. Äëÿ íà÷àëà íóæíî ïåðåîïðåäåëèòü ïîíÿòèå ñëàáî îïàñíîãî ñëîâà: ñëîâî áóäåò òàêîâûì, åñëè õîòÿ áû äîëÿ1r åãî ñîñåäåé ïëîõèå. Äàëåå, äëÿ êàæäîãî bi ñòðîèòñÿ èåðàðõèÿ ìíîæåñòâ(j)ñëàáî îïàñíûõ ñëîâ Sbi ,s è äîêàçûâàåòñÿ, ÷òî äëÿ êàæäîãî i íà êàêîé-òîèòåðàöèè ñëîâî a ïåðåñòà¼ò áûòü ñëàáî îïàñíûì. Çíà÷èò, ó a íàéä¼òñÿ ñîñåä, êîòîðûé áóäåò õîðîøèì äëÿ âñåõ bi íà ñîîòâåòñòâóþùåé èòåðàöèè. Åãîïðåôèêñû íóæíûõ äëèí è áóäóò îïèñàíèÿìè pi .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
