Диссертация (1103424), страница 12
Текст из файла (страница 12)
Ñõåìà áóäåò ïðåäñòàâëÿòü ñîáîé êîíúþíêöèþ ïîõîæèõ ñõåì, êàæäàÿ èç êîòîðûõ áóäåò ïðîâåðÿòü, ÷òî êîëëèçèé äëÿ îòäåëüíîãî S ìàëî. Äëÿ êàæäîãî S íà âõîä ñîîòâåòñòâóþùåé êîïèè áóäóò ïîäàíû57F (x1 )≡≡F (x2 )......F (x3 )≡≡Ïîðîãîâàÿ ñõåìà:1, åñëè < 3n åäèíèö0, èíà÷å...F (x|S| )≡Ïîðîãîâàÿ ñõåìà:1, åñëè < 3n åäèíèö0, èíà÷å.........∧∧SÐèñ. 4.2: Ýñêèç ñõåìû, ïðîâåðÿþùåé ìàëîå ÷èñëî êîëëèçèé ó õåø-ôóíêöèè.çíà÷åíèÿ F íà âñåõ ýëåìåíòàõ èç S .
Ñõåìà äîëæíà ðàñïîçíàòü, íàéäóòñÿëè ñðåäè íèõ 3n + 1 îäèíàêîâûõ.Ýòî äåëàåòñÿ òàê: âíà÷àëå äëÿ êàæäîé ïàðû çíà÷åíèé âû÷èñëÿåòñÿ, ñîâïàäàþò îíè èëè íåò. Ýòî äåëàåòñÿ ñîâñåì ïðîñòîé ñõåìîé: áåðóòñÿ ýêâèâàëåíöèè îò ñîîòâåòñòâóþùèõ äðóã äðóãó áèòîâ, à çàòåì êîíúþíêöèÿ ðåçóëüòàòîâ.Çàòåì äëÿ êàæäîãî ýëåìåíòà x ∈ S áåðóòñÿ ðåçóëüòàòû ñðàâíåíèÿ F (x)ñî âñåìè îñòàëüíûìè çíà÷åíèÿìè F (y), y ∈ S . Ê íèì ïðèìåíÿåòñÿ ïîðîãîâàÿ ñõåìà, ñóùåñòâóþùàÿ ïî òåîðåìå 2.33: îíà âûäà¼ò 1, åñëè ñðåäè âõîäîâìåíüøå 3n åäèíèö, è 0 â ïðîòèâíîì ñëó÷àå.3Íàêîíåö, íóæíî âçÿòü êîíúþíêöèþ ïî âñåì x ∈ S , à çàòåì ïî âñåìS ∈ S .
Ïîñòðîåííàÿ ñõåìà (ñì. ðèñ. 4.2) óäîâëåòâîðÿåò âñåì óñëîâèÿì.Äåéñòâèòåëüíî, îíà èìååò êîíñòàíòíóþ ãëóáèíó êàê êîìïîçèöèÿ òð¼õ ñõåìêîíñòàíòíîé ãëóáèíû. Îíà èìååò ðàçìåð 2O(n) : ñõåìà äëÿ êîíêðåòíîãî Sèìååò ðàçìåð O(k22k ) + 2k · poly(2k ) = 2O(n) , à âñåãî ðàçëè÷íûõ S íå áîëüøå2n+k = 2O(n) øòóê, â ïðîèçâåäåíèè âñ¼ ðàâíî ïîëó÷èòñÿ 2O(n) . Ôîðìóëàäëÿ ðàçìåðà ñõåìû äëÿ îäíîãî S îáúÿñíÿåòñÿ òàê: íà ïåðâîì ýòàïå íóæíî3 Åñëè k ñóùåñòâåííî ìåíüøå n, òàê ÷òî 3n íå áóäåò ïîëèëîãàðèôìè÷åñêîé ôóíêöèåé îò 2k , òî âñõåìó íóæíî äîáàâèòü íåäîñòàþùåå ÷èñëî ôèêòèâíûõ áèòîâ âõîäà, ðàâíûõ íóëþ.58|S|(|S|−1)= O(22k ) ïàð çíà÷åíèé ôóíêöèè F , íà îäíî ñðàâíåíèåñðàâíèòü2íóæíî O(k) ýëåìåíòîâ. Íà âòîðîì øàãå íóæíî äëÿ êàæäîãî èç 2k ñëîâ xïðèìåíèòü ñõåìó èç òåîðåìû 2.33.
Ýòà ñõåìà èìååò ïîëèíîìèàëüíûé ðàçìåðîò ÷èñëà ñâîèõ âõîäîâ, ò.å. å¼ ðàçìåð åñòü poly(2k ) = 2O(k) . Êîíúþíêöèÿäîáàâëÿåò åù¼ îäèí ýëåìåíò.Íàêîíåö, ïîñòðîåííàÿ ñõåìà âîçâðàùàåò çàÿâëåííûé ðåçóëüòàò. Åñëè Fèìååò íå áîëüøå 3n êîëëèçèé, òî äëÿ ëþáîãî S è ëþáîãî x ∈ S çíà÷åíèåF (x) ñîâïàäàåò ìåíåå, ÷åì ñ 3n çíà÷åíèÿìè F (y) äëÿ äðóãèõ y ∈ S .
Âòàêîì ñëó÷àå âñåõ ñõåìû âòîðîãî óðîâíÿ âîçâðàòÿò 1, è êîíúþíêöèÿ âñåõýòèõ çíà÷åíèé òàêæå áóäåò ðàâíà 1. Åñëè æå â êàêîì-òî S åñòü 3n + 1êîëëèçèÿ, òî ñîîòâåòñòâóþùàÿ ñõåìà âîçâðàòèò 0, à çíà÷èò, è êîíúþíêöèÿâîçâðàòèò 0.Òåïåðü, ïðèìåíÿÿ áàçîâûé ïðèíöèï 2.37, òåîðåìó ñóùåñòâîâàíèÿ 4.4 èòåîðåìó î ðàñïîçíàþùåé ñõåìå 4.5, ìîæíî çàêëþ÷èòü ñëåäóþùåå:Ñëåäñòâèå 4.6. Ïóñòü Gn : {0, 1}l → {0, 1}N ãåíåðàòîð ÍèñàíàÂèãäåðñîíà, ãäå N = k2n , l = O(n2d+6 ), à d ãëóáèíà ñõåìû, ïîñòðîåííîéâ òåîðåìå 4.4. Òîãäà äëÿ ëþáîãî ñåìåéñòâà S èç íå áîëåå 2n+k ïîäìíîæåñòâ {0, 1}n ðàçìåðà íå áîëüøå 2k ñðåäè îáðàçîâ Gn (x) ñóùåñòâóåò êîäôóíêöèè F : {0, 1}n → {0, 1}k , èìåþùåé íå áîëüøå 3n êîëëèçèé.4.2.3Ïîèñê àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà, ïîðîæäàþùåãî ôóíêöèþ ñ ìàëûì ÷èñëîì êîëëèçèéÄî ñèõ ïîð èçëîæåíèå íå îïèðàëîñü íà êîíêðåòíûé âèä ñèñòåìû ìíîæåñòâ S .
 ýòîì ðàçäåëå ìû îïèøåì, êàêóþ ñèñòåìó íóæíî ðàññìîòðåòüäëÿ äîêàçàòåëüñòâà âàðèàíòà òåîðåìû Ìó÷íèêà, à òàêæå äîêàæåì, ÷òî àðãóìåíò x, îáðàç êîòîðîãî Gn (x) îïèñûâàåò ôóíêöèþ ñ ìàëûì ÷èñëîì êîëëèçèé, ìîæíî íàéòè àëãîðèòìè÷åñêè, èñïîëüçîâàâ íåáîëüøóþ ïàìÿòü.Óòâåðæäåíèå 4.7. Çàôèêñèðóåì íåêîòîðîå ÷èñëî q . Ïóñòü S = S |∃b ∃q < q |b| < n ∧ S = {x | Cq (x) < n ∧ Cq (x|b) < k} . Òîãäà S ñîñòîèòèç íå áîëåå ÷åì 2n+k ìíîæåñòâ, êàæäîå èç êîòîðûõ èìååò ðàçìåð íåáîëüøå 2k .Äîêàçàòåëüñòâî.
Îãðàíè÷åíèå íà ðàçìåð êàæäîãî ìíîæåñòâà Sb,q = {x |Cq (x|b) < k} ïîëó÷àåòñÿ ñòàíäàðòíûì ðàññóæäåíèåì: ñóùåñòâóåò ìåíüøå592k óñëîâíûõ îïèñàíèé äëèíû ìåíüøå k , çíà÷èò è îïèñûâàåìûõ ñëîâ ìåíüøå, ÷åì 2k . Îãðàíè÷åíèå íà ðàçìåð ñèñòåìû S ïîëó÷àåòñÿ èç ñëåäóþùèõñîîáðàæåíèé: ðàçíûõ ñëîâ b äëèíû ìåíüøå n ñóùåñòâóåò 2n −1 øòóêà, à ïðèôèêñèðîâàííîì b ðàçíûå Sb,q âêëàäûâàþòñÿ îäíî â äðóãîå ïðè óâåëè÷åíèèq .
Çíà÷èò, ðàçíûõ ìíîæåñòâ íå áîëüøå, ÷åì ýëåìåíòîâ â ñàìîì áîëüøîìèç íèõ. À ïîñëåäíåå ÷èñëî ìåíüøå 2k . Ïåðåìíîæàÿ îöåíêè, ïîëó÷àåì 2n+k ,÷òî è òðåáîâàëîñü.Òåîðåìà 4.8. Ïóñòü Gn ãåíåðàòîð ÍèñàíàÂèãäåðñîíà èç ñëåäñòâèÿ 4.6, à S ñèñòåìà ìíîæåñòâ èç óòâåðæäåíèÿ 4.7. Òîãäà ñóùåñòâóåò àëãîðèòì, ïîëó÷àþùèé íà âõîä n, k è q è, èñïîëüçóÿ ïàìÿòü O(q) + poly(n), íàõîäèò x, òàêîé ÷òî Gn (x) êîäèðóåò ôóíêöèþF : {0, 1}n → {0, 1}k , èìåþùóþ íå áîëüøå 3n êîëëèçèé äëÿ ñèñòåìû S .Äîêàçàòåëüñòâî. Äëÿ âû÷èñëåíèé ñ îãðàíè÷åíèåì íà ïàìÿòü çàäà÷à ïîñòðîåíèÿ ýêâèâàëåíòíà çàäà÷å ðàñïîçíàâàíèÿ, ïîýòîìó ìû äîêàæåì, ÷òîïî ñëîâó x ìîæíî ïðîâåðèòü, ÿâëÿåòñÿ ëè Gn (x) êîäîì ôóíêöèè ñ ìàëûì÷èñëîì êîëëèçèé. îòëè÷èå îò îáû÷íîé êîëìîãîðîâñêîé ñëîæíîñòè, ñëîæíîñòü ñ îãðàíè÷åíèåì íà ïàìÿòü ÿâëÿåòñÿ âû÷èñëèìîé ôóíêöèåé, ïðè÷¼ì äëÿ âû÷èñëåíèÿ ñëîæíîñòè Cq , â òîì ÷èñëå óñëîâíîé, ñëîâà äëèíû n äîñòàòî÷íî ïàìÿòèO(q + n): íóæíî ïåðåáèðàòü âñå îïèñàíèÿ ïî âîçðàñòàíèþ äëèíû è çàïóñêàòü íà íèõ îïòèìàëüíûé ñïîñîá îïèñàíèÿ, îãðàíè÷èâàÿ èñïîëüçîâàííóþèì ïàìÿòü âåëè÷èíîé q è êîíòðîëèðóÿ çàöèêëèâàíèÿ.
Åñëè ïîëó÷èëñÿ x,òî åãî ñëîæíîñòü âû÷èñëåíà, åñëè ïîëó÷èëîñü äðóãîå ñëîâî, àëãîðèòì âûøåë çà ïðåäåëû çîíû èëè çàöèêëèëñÿ, òî íóæíî ïåðåéòè ê ñëåäóþùåìóîïèñàíèþ. Äëÿ êîíòðîëÿ çàöèêëèâàíèÿ íóæíà óäâîåííàÿ ïàìÿòü, äëÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ ëèíåéíàÿ îò n, ïîýòîìó â ñóììå ïîëó÷èòñÿO(q + n), êàê çàÿâëåíî. Ïðèâåä¼ì òàêæå âñåâäîêîä:Âõîä: Ñëîâà x, b è ÷èñëî qÂûõîä: Ñëîæíîñòü Cq (x|b)1 äëÿ êàæäîãî z ∈ {0, 1}∗ âûïîëíèòü2Çàïóñòèòü U (z, b) íà çîíå q ñ êîíòðîëåì çàöèêëèâàíèÿ;3åñëè U (z, b) êîððåêòíî âû÷èñëåíî è ðàâíî x òî âîçâðàòèòü |z|;4êîíåö öèêëàÀëãîðèòì 4.3:Âû÷èñëåíèå óñëîâíîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü.Äàëåå, çàìåòèì, ÷òî ÷èñëî êîëëèçèé ìîíîòîííî íå óáûâàåò ïðè ðàñøè60Âõîä:1234567891011121314×èñëà n, k è qÂûõîä: Ñëîâî x, òàêîå ÷òî Gn (x) êîäèðóåò ôóíêöèþ, èìåþùóþ íå áîëüøå 3nêîëëèçèé äëÿ Sl := O(n2d+6 ) ;/* Òî÷íîå çíà÷åíèå êàê â ñëåäñòâèè 4.6 */läëÿ êàæäîãî x ∈ {0, 1} âûïîëíèòü<näëÿ êàæäîãî b ∈ {0, 1}âûïîëíèòü<näëÿ êàæäîãî v ∈ {0, 1}âûïîëíèòüÇàïóñòèòü U (v, ε) íà çîíå q ñ êîíòðîëåì çàöèêëèâàíèÿ;åñëè U (v, ε) êîððåêòíî âû÷èñëåíî òîy := U (v, ε);qåñëè C (y|b) < k òîcount := 1;<näëÿ êàæäîãî w ∈ {0, 1}âûïîëíèòüÇàïóñòèòü U (w, ε) íà çîíå q ñ êîíòðîëåì çàöèêëèâàíèÿ;åñëè U (w, ε) êîððåêòíî âû÷èñëåíî òîz := U (w, ε);qåñëè C (z|b) < k è F(z)=F(y) òî count ++;/* Äëÿ âû÷èñëåíèÿ F áåðóòñÿ íóæíûå áèòû Gn (x)*/15êîíåö óñëîâèÿ1617181920212223êîíåö öèêëàåñëècount > 3nòî ïðîäîëæèòü öèêëïî x;êîíåö óñëîâèÿêîíåö óñëîâèÿêîíåö öèêëàêîíåö öèêëàx;count 6 3n */âîçâðàòèòü/* Âûïîëíÿåòñÿ, òîëüêî åñëè äëÿ âñåõ b è y âûïîëíåíîêîíåö öèêëàÀëãîðèòì 4.4:Ïîèñê õîðîøåãî àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà.ðåíèè ìíîæåñòâà, ïîýòîìó êîëëèçèè äîñòàòî÷íî ïîñ÷èòàòü äëÿ ìíîæåñòââèäà Sb,q ïðè ðàçëè÷íûõ b.
Áîëåå òîãî, èõ ìîæíî ïîñëåäîâàòåëüíî ïîñ÷èòàòü äëÿ âñåõ b, èñïîëüçóÿ îäíó è òó æå ïàìÿòü: äîïîëíèòåëüíûå çàòðàòûíà õðàíåíèå b ñîñòàâÿò O(n). Ïîýòîìó äîñòàòî÷íî îïèñàòü ïðîöåäóðó ïîäñ÷¼òà ÷èñëà êîëëèçèé äëÿ êîíêðåòíîãî Sb,q .Áóäåì ïîñëåäîâàòåëüíî ïåðå÷èñëÿòü âñå ýëåìåíòû Sb,q è äëÿ êàæäîãî èçíèõ ñ÷èòàòü ÷èñëî êîëëèçèé. Ïåðå÷èñëÿòü èõ ìîæíî î÷åíü ïðîñòî: íóæíîïåðåáèðàòü âñå îïèñàíèÿ äëèíû ìåíüøå n è äëÿ êàæäîãî îïèñàííîãî (íàçîíå q ) ñëîâà ñ÷èòàòü òàêæå ñëîæíîñòü Cq óñëîâíî íà b. Åñëè ðåçóëüòàòìåíüøå k , ñîîòâåòñòâóþùåå ñëîâî íóæíî âêëþ÷èòü â ïåðå÷èñëåíèå, èíà÷åïðîïóñòèòü.
Ïðè ýòîì èñïîëüçîâàííàÿ ðàáî÷àÿ ïàìÿòü áóäåò ðàâíà O(q+n).Íàêîíåö, äëÿ êàæäîãî ñëîâà z , ïîëó÷åííîãî â ïåðå÷èñëåíèè, íóæíî ïî61ñ÷èòàòü ÷èñëî êîëëèçèé. Âíà÷àëå íóæíî âû÷èñëèòü F (z). Ýòî ìîæíî ñäåëàòü, ïîñêîëüêó F (z) ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòüþ êîíêðåòíûõ k áèòîâçíà÷åíèÿ ãåíåðàòîðà Gn (x). Ïî ñâîéñòâó ãåíåðàòîðà (ñì. ñëåäñòâèå 2.36) ýòèáèòû ìîæíî âû÷èñëèòü íà ïàìÿòè poly(n). Äàëåå, íóæíî çàâåñòè ñ÷¼ò÷èêêîëëèçèé, èñõîäíî ðàâíûé åäèíèöå, è âíîâü çàïóñòèòü ïåðå÷èñëèòåëü ìíîæåñòâà Sb,q . Äëÿ êàæäîãî ïîëó÷åííîãî ñëîâà w íóæíî ïîñ÷èòàòü çíà÷åíèåF (w) è ñðàâíèòü åãî ñ F (z).  ñëó÷àå ñîâïàäåíèÿ íóæíî óâåëè÷èòü ñ÷¼ò÷èê êîëëèçèé íà 1. Åñëè ê êîíöó ïåðå÷èñëåíèÿ ñ÷¼ò÷èê ïðåâûñèë 3n + 1,òî êîëëèçèé ñëèøêîì ìíîãî, è ïðîîáðàç x íå ãîäèòñÿ.
Åñëè æå íè äëÿ êàêèõ b è z ñ÷¼ò÷èê íå áûë ïðåâûøåí, òî ïðîîáðàç x ãîäèòñÿ. Àëãîðèòì 4.4ïîêàçûâàåò ïñåâäîêîä.Îïèñàííûé àëãîðèòì âñåãäà âîçâðàùàåò âåðíîå çíà÷åíèå. Ïîñêîëüêóâû÷èñëåíèÿ, òðåáóþùèå ïàìÿòè O(q) èëè poly(n), íå ïðîâîäÿòñÿ îäíîâðåìåííî, à äëÿ õðàíåíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ è îñóùåñòâëåíèÿïåðåáîðîâ äîñòàòî÷íî ïàìÿòè O(n), îáùàÿ èñïîëüçîâàííàÿ ïàìÿòü ðàâíàO(q) + poly(n), êàê è òðåáîâàëîñü.4.2.4Ôîðìóëèðîâêà è äîêàçàòåëüñòâî âàðèàíòà òåîðåìû Ìó÷íèêà ýòîì ïîäðàçäåëå ìû äîêàæåì ñëåäóþùèé âàðèàíò òåîðåìû Ìó÷íèêà:Òåîðåìà 4.9.
Ïóñòü äàíû äâîè÷íûå ñëîâà 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);• CO(s)+poly(n) (p|a) 6 O(log log s) + O(log n).Äîêàçàòåëüñòâî. Âíà÷àëå ìû äîêàæåì òåîðåìó â ôîðìóëèðîâêå, ãäå âìåñòî O(log log s) ñòîÿò O(log s), à ïîòîì ïîêàæåì, êàê å¼ óñèëèòü.Èäåÿ äîêàçàòåëüñòâà ñîñòîèò â ñëåäóþùåì: â êà÷åñòâå p íóæíî âçÿòüçíà÷åíèå õåø-ôóíêöèè îò a.  êà÷åñòâå õåø-ôóíêöèè íóæíî âçÿòü ïñåâäîñëó÷àéíóþ ôóíêöèþ, ïîñòðîåííóþ â òåîðåìå 4.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
