Диссертация (1103424), страница 18
Текст из файла (страница 18)
Ýòî êîëè÷åñòâî ñëèøêîììàëî, ÷òîáû ñëîâî v ïåðåñòàëî áûòü õîðîøåé àïïðîêñèìàöèåé äëÿ ñëîâ zj .À ïðè äîñòàòî÷íî áîëüøîé âûáîðêå v áóäåò õîðîøåé àïïðîêñèìàöèåé è äëÿâñåõ ñëîâ z (r) .Ôîðìàëüíî ìû îöåíèì âåðîÿòíîñòü íåâûïîëíåíèÿ òðåòüãî óñëîâèÿ, ò.å.1ñèòóàöèè, êîãäà íåêîòîðîå êîäîâîå ñëîâî v îäíîâðåìåííî ÿâëÿåòñÿ ( 21 + 4m)11sàïïðîêñèìàöèåé õîòÿ áû äëÿ 16m ñëîâ z̃1 , .
. . , z̃s è íå ÿâëÿåòñÿ ( 2 + 8m )m−iàïïðîêñèìàöèåé íè äëÿ êàêèõ 232m ñëîâ z (r) ïðè r ∈ {0, 1}m−i . Ïîñêîëüêóñëîâà z̃1 , . . . , z̃s îòëè÷àþòñÿ îò z1 , . . . , zs ñóììàðíî íå áîëåå ÷åì â 2sγ ïîçèn̄söèÿõ, òî ïðè γ 6 1024m2 íå ìîæåò áûòü òàê, ÷òîáû ó 64m ñëîâ zj äîëÿ ñîâ1ïàäàþùèõ ñ v áèòîâ ñíèçèëàñü íà 8mïî ñðàâíåíèþ ñ z̃j .
Çíà÷èò, v ÿâëÿåòñÿ13s( 21 + 8m)-àïïðîêñèìàöèåé õîòÿ áû äëÿ 64mñëîâ zj . Îöåíèì âåðîÿòíîñòü, ÷òî111ïðè ýòîì v íå ÿâëÿåòñÿ ( 2 + 8m )-àïïðîêñèìàöèåé õîòÿ áû äëÿ äîëè 32mñëîâ11(r)z . Ïóñòü ζj ñëó÷àéíàÿ âåëè÷èíà, ðàâíàÿ 1, åñëè zj ÿâëÿåòñÿ ( 2 + 8m)1àïïðîêñèìàöèåé v , è 0 â ïðîòèâíîì ñëó÷àå, à β < 32m âåðîÿòíîñòü òîãî,13s÷òî ζj = 1. Åñëè v ÿâëÿåòñÿ ( 21 + 8m)-àïïðîêñèìàöèåé õîòÿ áû äëÿ 64mñëîâPs1zj , òî j=1 ζj > s(β + 64m ). Ïî íåðàâåíñòâó Õ¼ôôäèíãà âåðîÿòíîñòü ýòî1sãî ôàêòà íå ïðåâûøàåò exp −2 4096m2 s = exp − 2048m2 . Ñóììèðîâàíèå ïîâñåì êîäîâûì ñëîâàì äîáàâëÿåò ìíîæèòåëü 2n .Òàêèì îáðàçîì, îáùàÿ âåðîÿòíîñòü òîãî, ÷òî õîòÿ áû îäíî èç óñëîâèéíå âûïîëíåíî, íå ïðåâîñõîäèò2γ 2 ss s n+ exp −+ 2 exp −.(5.9)2 exp − 222n̄32m2048mn̄Êðîìå òîãî, ìû ïîòðåáîâàëè, ÷òîáû γ 6 1024m2 (îòêóäà ñëåäóåò è òðåáîâàn̄n̄íèå γ 6 32m ).
Åñëè ïîëîæèòü γ = 1024m2 è s = n5 , òî âûðàæåíèå (5.9) áóäåòìåíüøå 31 , ÷òî è òðåáîâàëîñü äîêàçàòü â ëåììå.Âåðí¼ìñÿ ê AM-ïðîòîêîëó. Íàïîìíèì, ÷òî Àðòóð âû÷èñëèë ñëîâàz̃1 , . . . , z̃s ∈ {0, 1}n̄ . Äëÿ êàæäîãî èç ñëîâ z̃i Àðòóð ïðèìåíÿåò àëãîðèòìäåêîäèðîâàíèÿ ñïèñêîì è ïîëó÷àåò ñïèñîê Vi âñåõ ñëîâ x ∈ {0, 1}n , êîäû881êîòîðûõ ÿâëÿþòñÿ 12 + 8m-àïïðîêñèìàöèÿìè z̃i . Çàòåì Àðòóð îáúåäèíÿåòñïèñêè è îñòàâëÿåò òîëüêî òå ñëîâà, êîòîðûå âñòðåòèëèñü õîòÿ áû s/16mðàç. Ïî ëåììå 5.7 ñ âåðîÿòíîñòüþ õîòÿ áû 2/3 â íîâîì ñïèñêå åñòü ñëîâîa = LDC−1n,δ (û) (îá ýòîì ãîâîðèò âòîðîå óñëîâèå ëåììû), à âñå ñëîâà ÿâëÿþòñÿ ïðîîáðàçàìè êàíäèäàòîâ (îá ýòîì ãîâîðèò òðåòüå óñëîâèå ëåììû).Çíà÷èò, ïðîãðàììîé p0 (ñóùåñòâóþùåé ïî ñëåäñòâèþ 2.12 è èìåþùåé ëîãàðèôìè÷åñêóþ äëèíó) ìîæíî îòäåëèòü ñëîâî a îò âñåõ îñòàëüíûõ, ýòîéïðîãðàììîé âîñïîëüçóåòñÿ Àðòóð è òàêèì îáðàçîì íàéä¼ò a.Ïðîâåðèì, ÷òî îáú¼ì äîïîëíèòåëüíîé èíôîðìàöèè, íóæíûé äëÿ âîññòàíîâëåíèÿ a, íå ïðåâûøàåò O(log3 n).
Äåéñòâèòåëüíî, ïîìèìî ñëîâ b è pÀðòóðó íóæíî ïîëó÷èòü ñëåäóþùóþ èíôîðìàöèþ:• Ïàðàìåòðû n, k , d, i, ïî êîòîðûì ìîæíî âîññòàíîâèòü âñå îñòàëüíûåïàðàìåòðû, â òîì ÷èñëå s è γ ;• Áèò ri , ïðè êîòîðîì íåðàâåíñòâî (5.6) îñòà¼òñÿ âåðíûì;• Ïðèáëèæåíèå ê ÷èñëó ḡ , äîñòàòî÷íîå äëÿ âû÷èñëåíèÿ öåëîé ÷àñòè s ·(ḡ − γ);• Ïðîãðàììó p0 , ïîçâîëÿþùóþ îòëè÷èòü û îò îñòàëüíûõ êàíäèäàòîâ.Âñÿ ýòà èíôîðìàöèÿ çàíèìàåò äàæå O(log n), à íå O(log3 n), òàê ÷òî óñëîâèåâûïîëíåíî ñ çàïàñîì.3Îïèøåì åù¼ ðàç AM-àëãîðèòì è äîêàæåì åãî êîððåêòíîñòü:1.
Àðòóð âû÷èñëÿåò çíà÷åíèÿ ïàðàìåòðîâ m, δ , n̄, l, s, γ ïî èçâåñòíûìåìó n, k , d, i;2. Àðòóð âûáèðàåò ñëó÷àéíî è íåçàâèñèìî ñëîâà r(1) , . . . , r(s) ∈ {0, 1}m−i ;3. Ìåðëèí ïîñûëàåò s · (ḡ − γ) ñåðòèôèêàòîâ òîãî, ÷òî G(x, r(j) ) = 1 äëÿðàçëè÷íûõ ïàð (x, r(j) ) (ñ óêàçàíèåì, êàêîé ñåðòèôèêàò îòíîñèòñÿ êêàêîé ïàðå);4. Àðòóð ïðîâåðÿåò, ÷òî ñåðòèôèêàòîâ èìåííî ñòîëüêî (èñïîëüçóÿ ïðèáëèæåíèÿ ê ḡ ), ÷òî âñå îíè ñîîòâåòñòâóþò ðàçëè÷íûì ïàðàì è ÷òî îíèâñå ïîäõîäÿò (èñïîëüçóÿ b, p è ri ). Åñëè õîòÿ áû îäèí ñåðòèôèêàò íåïîäîø¼ë, Àðòóð îñòàíàâëèâàåò âû÷èñëåíèÿ è âîçâðàùàåò ⊥;3Íàïîìíèì, ÷òî O(log3 n) áèòîâ ïîëó÷èòñÿ, åñëè ïîòðåáîâàòü |p| < k âìåñòî |p| < k + O(log3 n).895.
Àðòóð âû÷èñëÿåò ñëîâà z̃1 , . . . , z̃s ∈ {0, 1}n̄ íà îñíîâå ïðèñëàííûõ åìóñåðòèôèêàòîâ: z̃j (x) = 1, åñëè áûë ïðèñëàí ñåðòèôèêàò òîãî, ÷òîG(x, r(j) ) = 1;6. Àðòóð äåêîäèðóåò ñëîâà z̃1 , . . . , z̃s ñïèñêàìè è âûáèðàåò òå ñëîâà èçñïèñêîâ, êîòîðûå âñòðå÷àþòñÿ õîòÿ áû s/16m ðàç;7. Êî âñåì âûáðàííûì ñëîâàì Àðòóð ïðèìåíÿåò ïðîãðàììó p0 . Åñëè p0íå ïðèíÿëà íè îäíîãî ñëîâà èëè ïðèíÿëà áîëåå îäíîãî ñëîâà, Àðòóðîñòàíàâëèâàåò âû÷èñëåíèÿ è âîçâðàùàåò ⊥. Åñëè p0 ïðèíÿëà ðîâíîîäíî ñëîâî, òî Àðòóð âîçâðàùàåò åãî â êà÷åñòâå a.Êàê íåòðóäíî çàìåòèòü, âñå øàãè ðàáîòàþò ïîëèíîìèàëüíîå âðåìÿ, îáùàÿ äëèíà ñåðòèôèêàòîâ òàêæå ïîëèíîìèàëüíà. Ïðîâåðèì, ÷òî Àðòóð äåéñòâèòåëüíî âû÷èñëÿåò a ñ âåðîÿòíîñòüþ õîòÿ áû 32 .
Ýòî ñëåäóåò èç ëåììû 5.7: ñ âåðîÿòíîñòüþ õîòÿ áû 23 îäíîâðåìåííî ñóùåñòâóåò íàáîð ñåðòèôèêàòîâ, ïðè êîòîðûõ Àðòóð âîññòàíàâëèâàåò a, è íå ñóùåñòâóåò íàáîðà ñåðòèôèêàòîâ, ïîçâîëÿþùåãî îáìàíóòü Àðòóðà. À èìåííî, ïî ïåðâîìóóñëîâèþ ëåììû ñóùåñòâóåò íàáîð ñåðòèôèêàòîâ, êîòîðûé Àðòóð ïðèíèìàåò íà ñòàäèè 4, à ïî âòîðîìó è òðåòüåìó óñëîâèþ ëþáîé íàáîð ñåðòèôèêàòîâ, ïðèíèìàåìûé íà ýòîé ñòàäèè, ïðèâîäèò ê ïîñòðîåíèþ ñïèñêà ñëîâ,ñîñòîÿùåãî òîëüêî èç ïðîîáðàçîâ êàíäèäàòîâ è ñîäåðæàùåìó a, íà ñòàäèè 6. Ïîñëå ýòîãî íà ñòàäèè 7 èç ýòîãî ñïèñêà áóäåò îòîáðàíî a, ÷òî èòðåáîâàëîñü.Òàêèì îáðàçîì, óñëîâèå CAMt2 (n) (a|b, p) = O(log3 n) äîêàçàíî.5.4Î òåîðåìå äëÿ íåñêîëüêèõ óñëîâèéÂîçíèêàåò âîïðîñ, ìîæíî ëè ðàñïðîñòðàíèòü òåîðåìó Ìó÷íèêà äëÿCAM-ñëîæíîñòè íà äâà èëè áîëüøåå êîëè÷åñòâî óñëîâèé. Ñ îäíîé ñòîðîíû, ôóíêöèÿ Òðåâèñàíà ÿâëÿåòñÿ ïðåôèêñíûì ýêñòðàêòîðîì (åñëè âçÿòüâìåñòî ñëàáîãî äèçàéíà ðàâíîìåðíî ñëàáûé, ñì. íèæå), ïîýòîìó åñòü ïîòåíöèàëüíàÿ âîçìîæíîñòü èñïîëüçîâàòü å¼ äëÿ òåîðåìû ñ íåñêîëüêèìè óñëîâèÿìè.
Ñ äðóãîé ñòîðîíû, â êîíñòðóêöèè ìû íå ïîëüçîâàëèñü ñâîéñòâîìýêñòðàêòîðà íåïîñðåäñòâåííî, à âìåñòî ýòîãî ñòðîèëè êîä ñïåöèàëüíûì îáðàçîì. Çàðàíåå íåïîíÿòíî, ìîæíî ëè ðàñïðîñòðàíèòü ýòîò ñïîñîá íà äâàóñëîâèÿ ñðàçó.90Ìû ïðèâåä¼ì íåêîòîðûå àðãóìåíòû â ïîëüçó òîãî, ÷òî íåïîñðåäñòâåííî íàø ìåòîä íà äâà óñëîâèÿ íå ðàñïðîñòðàíÿåòñÿ. À èìåííî, ìû áóäåìàíàëèçèðîâàòü ñëåäóþùåå óòâåðæäåíèå:Ãèïîòåçà 5.8. Äëÿ ëþáîãî ïîëèíîìà t1 (n) ñóùåñòâóåò ïîëèíîì t2 (n),äëÿ êîòîðîãî âûïîëíåíî ñëåäóþùåå ñâîéñòâî. Ïóñòü äàíû ÷èñëà n, k èk 0 , ñëîâî a äëèíû ìåíüøå n è ñëîâà b è c, òàêèå ÷òî Ct1 (n) (a|b) < k èCt1 (n) (a|c) < k 0 .
Òîãäà ñóùåñòâóåò ñëîâà p è q , îäíî èç êîòîðûõ ÿâëÿåòñÿíà÷àëîì äðóãîãî, óäîâëåòâîðÿþùåå ñëåäóþùèì óñëîâèÿì:• CAMt2 (n) (a|b, p) = O(log3 n);• CAMt2 (n) (a|c, q) = O(log3 n);• |p| 6 k + O(log3 n);• |q| 6 k 0 + O(log3 n);• Ct2 (n) (p|a) = O(log3 n).• Ct2 (n) (q|a) = O(log3 n).Êàê è â òåîðåìå ñ îäíèì óñëîâèåì, åñëè ãèïîòåçà âåðíà, òî íåêîòîðûå èçñëàãàåìûõ O(log3 n) ìîãóò áûòü óìåíüøåíû äî O(1) èëè O(log n), íî ìûîñòàâëÿåì èõ â èñõîäíîì âèäå äëÿ åäèíîîáðàçèÿ. îñíîâíîé òåîðåìå äëèíà p, ò.å. ñóììà äëèí çàïèñåé òàáëèö èñòèííîñòèôóíêöèé fj îöåíèâàëàñü êàê m − 1 íåçàâèñèìî îò i.
Òåïåðü íóæíî, ÷òîáû÷àñòü ýòèõ òàáëèö ìîæíî áûëî âçÿòü â êà÷åñòâå q , êîòîðîå äîëæíî áûòüìåíüøåé äëèíû, ïîýòîìó íóæíà áîëåå òî÷íàÿ îöåíêà. Åñòåñòâåííûì ñïîñîáîì ïðåäñòàâëÿåòñÿ ðàññìîòðåíèå ðàâíîìåðíî ñëàáûõ äèçàéíîâ âìåñòîñëàáûõ:Îïðåäåëåíèå 5.9. Ïóñòü l è d ñóòü íàòóðàëüíûå ÷èñëà, ρ > 1, à Si ⊂{1, . .
. , d} äëÿ i = 1, . . . , m. Ñèñòåìà ìíîæåñòâ {S1 , . . . , Sm } íàçûâàåòñÿ (l,d, ρ)-ðàâíîìåðíî ñëàáûì äèçàéíîì, åñëè êàæäîå Si ñîñòîèò èç l ýëåìåíòîâi−1P |Si ∩Sj |è äëÿ êàæäîãî i > 1 ñóììà2íå ïðåâîñõîäèò ρ(i − 1).j=1Íåïîñðåäñòâåííî èç îïðåäåëåíèÿ âèäíî, ÷òî åñëè ñèñòåìà {S1 , . . . , Sm }ÿâëÿåòñÿ (l, d, ρ)-ðàâíîìåðíî ñëàáûì äèçàéíîì, òî è ëþáàÿ ñèñòåìà{S1 , . . . , Sm0 } ïðè m0 6 m òàêæå ÿâëÿåòñÿ (l, d, ρ)-ðàâíîìåðíî ñëàáûì äèçàéíîì.
Ýòî êëþ÷åâîå ñâîéñòâî, áëàãîäàðÿ êîòîðîìó ýêñòðàêòîð ñòàíîâèòñÿïðåôèêñíûì. Äàëåå, âåðíà ñëåäóþùàÿ òåîðåìà ñóùåñòâîâàíèÿ:91Òåîðåìà 5.10 ( [37]). Ñóùåñòâóåò àëãîðèòì, ðàáîòàþùèé ïîëèíîìèàëüíîå îò l + m âðåìÿ è ãåíåðèðóþùèé (l, d, ρ)-ñëàáûé äèçàéí äëÿd = O(l2 / log ρ).Ïðè íåïîñðåäñòâåííîì ïðèìåíåíèè ìåòîäà íóæíî çàôèêñèðîâàòü íåêîòîðûé ðàâíîìåðíî ñëàáûé äèçàéí, ïîðîæä¼ííûé ýòèì àëãîðèòìîì, è ðàññìîòðåòü ôóíêöèþ Òðåâèñàíà, ïîñòðîåííóþ íà îñíîâå ýòîãî ðàâíîìåðíîñëàáîãî äèçàéíà.
Ïîñêîëüêó îïðåäåëåíèå ôóíêöèè òî÷íî òàêîå æå, òî ìûñîõðàíèì äëÿ íå¼ îáîçíà÷åíèå TRδ . Òàêàÿ ôóíêöèÿ áóäåò ÿâëÿòüñÿ ïðåôèêñíûì ýêñòðàêòîðîì, íî êàê ýòîò ôàêò èñïîëüçîâàòü íåïîñðåäñòâåííî,íåÿñíî.Ïî ñðàâíåíèþ ñ èñõîäíîé òåîðåìîé ïîÿâèëñÿ äîïîëíèòåëüíûé ïàðàìåòði−1P |Si ∩Sj |ρ.  ñèëó öåëî÷èñëåííîñòè2íåâàæíî, ðàâåí ëè ρ åäèíèöå, èëèj=1æå ρ = 1 +À âî âòîðîì ñëó÷àå ïî òåîðåìå 5.10 ñóùåñòâóåò ðàâíîìåðíî ñëàáûé äèçàéí ñ d = O(log3 n).
Îñòàëüíûå ïàðàìåòðû ìîæíî âûáðàòüàíàëîãè÷íî òåîðåìå ñ îäíèì óñëîâèåì.Ê ñîæàëåíèþ, äàëüíåéøåå ðàññóæäåíèå íå îáîáùàåòñÿ íà ñëó÷àé äâóõóñëîâèé. Åñëè àíàëîã ïðåäèêàòà B áóäåò çàâèñåòü è îò óñëîâèÿ b, è îòóñëîâèÿ c, òî ïðè âîññòàíîâëåíèè a Àðòóð íå ñìîæåò âû÷èñëÿòü åãî, çíàÿòîëüêî îäíî èç óñëîâèé. Åñëè æå ðàññìîòðåòü äâà ðàçíûõ ïðåäèêàòà, ïîñòðîåííûõ ïî óñëîâèÿì b è c, òî äëÿ íèõ ìîãóò ïîëó÷èòüñÿ ðàçíûå ìåñòà i,ïî êîòîðûì ñòðîÿòñÿ ôóíêöèè f1 , . . . , fi−1 , ò.å. êîäû p è q .  òàêîì ñëó÷àåíå ïîëó÷èòñÿ, ÷òî îäíî èç p è q áóäåò íà÷àëîì äðóãîãî. Áîëåå òîãî, ïðè èñïîëüçîâàíèè ðàâíîìåðíî ñëàáîãî äèçàéíà ñ âûñîêîé âåðîÿòíîñòüþ ÷èñëî iáóäåò ïðèìåðíî ðàâíî m, èíà÷å ñëîæíîñòü CAMt2 (n) (a|b) áóäåò ñóùåñòâåííî ìåíüøå Ct1 (n) (a|b), ÷òî íåâîçìîæíî ïðè Ct1 (n) (a|b) ≈ C(a|b).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
