Диссертация (1103424), страница 17
Текст из файла (страница 17)
. rm )] >83òàêæå îáðàòèòü ôóíêöèþ Òðåâèñàíà. Çàòî, åñëè çíà÷åíèå ïðåäèêàòà B ðàâíî 1, òî ýòîò ôàêò ìîæíî óäîñòîâåðèòü ñåðòèôèêàòîì, äëÿ ÷åãî è íóæåíÌåðëèí.Îïèøåì ïðîöåäóðó áîëåå ïîäðîáíî. Íàïîìíèì, ÷òî ñëîâî v 0 ∈ {0, 1}n̄ÿâëÿåòñÿ α-àïïðîêñèìàöèåé ñëîâà v ∈ {0, 1}n̄ , åñëè v è v 0 ñîâïàäàþò õîòÿáû íà αn̄ áèòàõ. Äëÿ ôèêñèðîâàííîãî àðãóìåíòà r ôóíêöèÿ G(x, r) îïðåäåëÿåò íåêîòîðóþ áóëåâó ôóíêöèþ G(r) : {0, 1}l → {0, 1}. Äëèíà òàáëèöûèñòèííîñòè ýòîé ôóíêöèè ðàâíà 2l = n̄. Äëÿ ôèêñèðîâàííîãî r çàïèøåìýòó òàáëèöó ñëîâîì z (r) ∈ {0, 1}n̄ . Òàêèì îáðàçîì, áèòû ñëîâà z (r) ïðîíóìåðîâàíû ñëîâàìè x ∈ {0, 1}l , è x-ûé áèò z (r) ðàâåí åäèíèöå òîãäà è òîëüêîòîãäà, êîãäà G(x, r) = 1. Ñëåäîâàòåëüíî, êîëè÷åñòâî åäèíèö â ñëîâå z (r)ðàâíî ÷èñëó ñëîâ x, äëÿ êîòîðûõ âûïîëíåíî B(f1 (x) .
. . fi−1 (x)1r) = 1.Íàçîâ¼ì ñëîâî v ∈ {0, 1}n̄ êàíäèäàòîì, åñëè îíî ÿâëÿåòñÿ êîäîâûì (ò.å.1ëåæèò â îáðàçå LDCn,δ ) è õîòÿ áû äëÿ äîëè 32mâñåõ r ∈ {0, 1}m−i ñîîòâåòñòâóþùàÿ ñòðîêà z (r) ÿâëÿåòñÿ 12 + δ -àïïðîêñèìàöèåé v .1 Íåòðóäíî çàìåòèòü, ÷òî ñëîâî û ïðè u ∈ Lb ÿâëÿåòñÿ êàíäèäàòîì. Äåéñòâèòåëüíî, ïðåäïîëîæèâ îáðàòíîå, îáîçíà÷èì ñîáûòèå z (r) ÿâëÿåòñÿ 12 + δ -àïïðîêñèìàöèåéû ÷åðåç A è ðàñïèøåì Prx,r [G(x, r) = û(x)] ïî ôîðìóëå ïîëíîé âåðîÿòíîñòè:Prx,r [G(x, r) = û(x)] =hihi = Prr A Prx,r G(x, r) = û(x)|A + Prr A Prx,r G(x, r) = û(x)|AÝòî âûðàæåíèå áóäåò îãðàíè÷åíî ñâåðõó âåëè÷èíîé1·1+1·32m11+2 8m<11+,2 4m(5.8)÷òî ïðîòèâîðå÷èò íåðàâåíñòâó (5.7).2  ëåâîé ÷àñòè íåðàâåíñòâà (5.8) èñ 1ïîëüçîâàíî, ÷òî âñå âåðîÿòíîñòè íå áîëüøå 1, Prr A 6 32mïî ïðåäïîëîæåíèþ,à ïðè iëîæíîì A äëÿ ëþáîãî ôèêñèðîâàííîãî r âåðîÿòíîñòüh1Prx G(x, r) = û(x) ìåíüøå 21 + δ = 12 + 8mïî îïðåäåëåíèþ A.
Ïðèýòîì â ñèëó òåîðåìû 5.5 êàíäèäàòîâ íå ìîæåò áûòü áîëüøå ÷åì 32mq ,ãäå q = poly(n/δ) = poly(n) ðàçìåð ñïèñêà ïðè äåêîäèðîâàíèè. Äåéñòâèòåëüíî, äëÿ êàæäîãî r íàéä¼òñÿ íå áîëüøå q êîäîâûõ ñëîâ, êîòîðûåÍåÿâíî îïðåäåëåíèå êàíäèäàòà çàâèñèò îò èñõîäíîãî ñëîâà u: âåäü ÷åðåç íåãî îïðåäåëÿþòñÿ ôóíêöèè fj , à çàòåì ïðåäèêàò G.2 Ýòî ðàññóæäåíèå îñòàëîñü áû â ñèëå, äàæå åñëè çàìåíèòü 1 íà 1 â îïðåäåëåíèè êàíäèäàòà, íî32m8mâ äàëüíåéøåì íàì ïîíàäîáèòñÿ èìåííî òàêàÿ îöåíêà.184+ δ -àïïðîêñèìèðóþò z (r) . Çíà÷èò, îáùåå êîëè÷åñòâî ïàð âèäà (êîäîâîåñëîâî, 12 + δ -àïïðîêñèìèðóþùåå åãî z (r) ), íå ïðåâûøàåò q2m−i .
Ïîñêîëü1êó êàæäûé êàíäèäàò 21 + δ -àïïðîêñèìèðóåò õîòÿ áû 32m2m−i ñëîâ âèäàz (r) , òî îáùåå êîëè÷åñòâî êàíäèäàòîâ ïî ïðèíöèïó Äèðèõëå íå ïðåâûøàåò1q2m−i /( 32m2m−i ) = 32mq = poly(n). Ñëåäîâàòåëüíî, ÷èñëî ñëîâ, êîäû êîòîðûõ ÿâëÿþòñÿ êàíäèäàòàìè, òàêæå ïîëèíîìèàëüíî, ïðè òîì ÷òî êîä aÿâëÿåòñÿ êàíäèäàòîì. Ïî ñëåäñòâèþ 2.12 ñóùåñòâóåò ïðîãðàììà p0 , ðàáîòàþùàÿ ïîëèíîìèàëüíàÿ âðåìÿ è èìåþùàÿ äëèíó O(log n), ïðèíèìàþùàÿa è îòâåðãàþùàÿ âñå îñòàëüíûå ñëîâà, êîäû êîòîðûõ ÿâëÿþòñÿ êàíäèäàòàìè. Îñòàëîñü ñîñòàâèòü ñïèñîê ýòèõ ñëîâ, äëÿ ÷åãî ïîíàäîáÿòñÿ ñëó÷àéíûåáèòû è ìàãèÿ Ìåðëèíà.PÎáîçíà÷èì ÷åðåç ḡ ÷èñëî x,r G(x, r)/2m−i , ò.å. ñðåäíåå ïî r êîëè÷åñòâîåäèíèö â z (r) .
Çàìåòèì, ÷òî ëþáîé ôàêò G(x, r) = 1 ìîæíî óäîñòîâåðèòüñåðòèôèêàòîì ïîëèíîìèàëüíîé äëèíû, ñîñòîÿùèì èç ñëîâ u ∈ {0, 1}n , y ∈{0, 1}d è ïðîãðàììû π äëèíû íå áîëåå k ñî ñëåäóþùèìè ñâîéñòâàìè:12• TRδ (u, y) = f1 (x) . . . fi−1 (x)1r;• π(b) = u, ïðè ýòîì π(b) ðàáîòàåò íå áîëüøå t1 (n) øàãîâ.Èç âòîðîãî óñëîâèÿ ñëåäóåò, ÷òî Ct1 (n) (u|b) 6 k , ò.å. u ∈ Lb . Òîãäà èç ïåðâîãîóñëîâèÿ ñëåäóåò, ÷òî f1 (x) . . . fi−1 (x)1r ëåæèò â îáðàçå Lb × {0, 1}d ïîä äåéñòâèåì TRδ .
Ýòî îçíà÷àåò, ÷òî B(f1 (x) . . . fi−1 (x)1r) = 1, ò.å. G(x, r) = 1,÷òî è òðåáîâàëîñü. ßñíî òàêæå, ÷òî îáà óñëîâèÿ (ïðè èçâåñòíûõ b è p)ìîæíî ïðîâåðèòü çà ïîëèíîìèàëüíîå âðåìÿ.Íà÷í¼ì îïèñàíèå AM-ïðîòîêîëà, ãåíåðèðóþùåãî a. Íàïîìíèì, ÷òî ìûèñïîëüçóåì ñëåäóþùóþ ìåòàôîðó: ñíà÷àëà Àðòóð ïîëó÷àåò ñëó÷àéíûå áèòû, çàòåì Ìåðëèí óçíà¼ò ýòè ñëó÷àéíûå áèòû è ïîñûëàåò Àðòóðó íåêîòîðîå ñîîáùåíèå. Çàòåì Àðòóð ïðîâîäèò íåêîòîðûå âû÷èñëåíèÿ è âûäà¼òëèáî ñèìâîë îøèáêè ⊥, ëèáî íåêîòîðîå ñëîâî u. Òðåáóåòñÿ, ÷òîáû ñ âåðîÿòíîñòüþ íå ìåíüøå 32 Àðòóð âîçâðàùàë a äëÿ êàêîãî-òî ñîîáùåíèÿ Ìåðëèíà,ïðè ýòîì äëÿ ëþáîãî äðóãîãî ñîîáùåíèÿ âîçâðàùàë áû ëèáî òî æå a, ëèáîñèìâîë îøèáêè. Ïåðåéä¼ì ê ñîáñòâåííî ïðîòîêîëó. Ïåðâûì äåëîì Àðòóðâûáèðàåò ðàâíîìåðíî è íåçàâèñèìî ñëó÷àéíûå ñëîâà r(1) , . .
. , r(s) äëèíû(m − i), ãäå s = s(n) ïîëèíîì, êîòîðûé áóäåò îïðåäåë¼í ïîçæå. Çàòåì îíçàïðàøèâàåò ó Ìåðëèíà s(ḡ − γ) ñåðòèôèêàòîâ òîãî, ÷òî ðàçëè÷íûå ïàðû(x, r(j) ) óäîâëåòâîðÿþò ñîîòíîøåíèþ G(x, r(j) ) = 1, ãäå âåëè÷èíà γ = γ(n)85òàêæå áóäåò îïðåäåëåíà ïîçæå. Àðòóð ïðîâåðÿåò, ÷òî âñå ïàðû äåéñòâèòåëüíî ðàçíûå è ÷òî âñå ñåðòèôèêàòû ïîäõîäÿò.
Åñëè õîòÿ áû îäèí èç íèõíåäåéñòâèòåëåí, Àðòóð îñòàíàâëèâàåòñÿ ñ âîçâðàùåíèåì ñèìâîëà îøèáêè.Åñëè æå âñå ñåðòèôèêàòû ïðîõîäÿò ïðîâåðêó, òî Àðòóð âû÷èñëÿåò ñëîâàz̃1 , . . . , z̃s ∈ {0, 1}n̄ ñîãëàñíî ñëåäóþùåìó ïðàâèëó: x-ûé áèò ñëîâà z̃j ðàâåí 1 òîãäà è òîëüêî òîãäà, êîãäà Ìåðëèí ïðåäîñòàâèë ñåðòèôèêàò òîãî,÷òî G(x, r(j) ) = 1. Äëÿ äàëüíåéøåãî íàì ïîíàäîáèòñÿ ñëåäóþùàÿ ëåììà,äîêàçàííàÿ â [13]. Ïîìèìî ïðî÷åãî, îíà ñïåöèôèöèðóåò ïàðàìåòðû s è γ .Ëåììà 5.7 ( [13]).
Ïóñòü ôóíêöèè û : {0, 1}l → {0, 1} è G : {0, 1}l ×{0, 1}m−i → {0, 1} óäîâëåòâîðÿþò íåðàâåíñòâó (5.7), à ḡ =Pm−i. Òîãäà äëÿ íåêîòîðîãî ðàöèîíàëüíîãî γ = n̄/ poly(m)x,r G(x, r)/2è öåëîãî s = poly(n) äëÿ ðàâíîìåðíî è íåçàâèñèìî âûáðàííûõ ñëîâr(1) , . .
. , r(s) äëèíû (m − i) ñ âåðîÿòíîñòüþ áîëüøå 23 âûïîëíåíû îäíîâðåìåííî ñëåäóþùèå óñëîâèÿ:• Õîòÿ áû äëÿ s · (ḡ − γ) ïàð (x, r(j) ) ∈ {0, 1}l × {r(1) , . . . , r(s) } âûïîëíåíîóñëîâèå G(x, r(j) ) = 1;• Ïðè ëþáîì âûáîðå s · (ḡ − γ) ïàð (x, r(j) ) ∈ {0, 1}l × {r(1) , . . . , r(s) }, óäîsâëåòâîðÿþùèõ óñëîâèþ G(x, r(j) ) = 1, õîòÿ áû 16mèç s ñëîâ z̃1 , . . . , z̃s11ÿâëÿþòñÿ ( 2 + 4m )-àïððîêñèìàöèÿìè û (ãäå x-ûé áèò ñëîâà z̃j ðàâåíåäèíèöå, åñëè ïàðà (x, r(j) ) íàõîäèòñÿ â ÷èñëå âûáðàííûõ);• Ïðè ëþáîì âûáîðå s · (ḡ − γ) ïàð (x, r(j) ) ∈ {0, 1}l × {r(1) , .
. . , r(s) },óäîâëåòâîðÿþùèõ óñëîâèþ G(x, r(j) ) = 1, ëþáîå êîäîâîå ñëîâî v äëÿ1sLDCn,δ , ÿâëÿþùååñÿ ( 12 + 4m)-àïððîêñèìàöèåé õîòÿ áû äëÿ 16mñëîâz̃1 , . . . , z̃s , ÿâëÿåòñÿ êàíäèäàòîì.Äîêàçàòåëüñòâî. Çíà÷åíèÿ s è γ ìû âûáåðåì â êîíöå äîêàçàòåëüñòâà.Çàìåòèì, ÷òî ÷èñëî ḡ ðàâíÿåòñÿ ñðåäíåìó ïî r ÷èñëó åäèíèö â íàáîðå{G(x, r)}x∈{0,1}l . Åñëè ðàññìîòðåòü s òàêèõ íàáîðîâ, òî ñðåäíåå ñóììàðíîå÷èñëî åäèíèö ñîñòàâèò sḡ . Ïåðâîå óñëîâèå ãîâîðèò î òîì, ÷òî ñ âûñîêîé âåðîÿòíîñòüþ ôàêòè÷åñêîå ñóììàðíîå ÷èñëî åäèíèö ïðåâûñèò s(ḡ − γ).
Ôîðìàëüíî ýòî óñëîâèå ñëåäóåò èç íåðàâåíñòâà Õ¼ôôäèíãà. Ââåä¼ì ñëó÷àéíóþâåëè÷èíó ξi , ðàâíóþ äîëå ñëîâ x, äëÿ êîòîðûõ G(x, r(i) ) = 1. Òîãäà ìàòåìàòè÷åñêîå îæèäàíèå ξi ðàâíî ḡ/n̄ (ìû ïîäåëèëè ñðåäíåå êîëè÷åñòâî íóæíûõñëîâ ḡ íà îáùåå êîëè÷åñòâî n̄ = 2l ). Ïî òåîðåìå 2.39 âåðîÿòíîñòü òîãî, ÷òîPsḡγ22ξ<s·−ii=1n̄n̄ , íå ïðåâîñõîäèò exp(−2γ s/n̄ ). Ïðè ýòîì âåëè÷èíà86Pn̄ · si=1 ξi êàê ðàç è ðàâíÿåòñÿ ÷èñëó ïàð (x, r(j) ) ∈ {0, 1}l × {r(1) , . . .
, r(s) },óäîâëåòâîðÿþùèõ óñëîâèþ G(x, r(j) ) = 1, ïîýòîìó ÷èñëî òàêèõ ïàð íå ìåíüøå s(ḡ − γ) ñ âåðîÿòíîñòüþ õîòÿ áû exp(−2γ 2 s/n̄2 ). Ìû òàêæå áóäåì ñ÷èòàòü, ÷òî êîëè÷åñòâî ïàð (x, r(j) ), óäîâëåòâîðÿþùèõ óñëîâèþ G(x, r(i) ) = 1,íå ïðåâûøàåò s · (ḡ + γ). Âåðîÿòíîñòü îáðàòíîãî òàêæå íå ïðåâîñõîäèòexp(−2γ 2 s/n̄2 ). Ìû âûáåðåì s è γ òàê, ÷òîáû îáå âåðîÿòíîñòè áûëè ìàëû.Âòîðîå óñëîâèå íåôîðìàëüíî îáîñíîâûâàåòñÿ òàê: åñëè âìåñòî z̃j âçÿòü(j)ñëîâà zj = z (r ) , ïîñòðîåííûå èç áèòîâ G(x, r(j) ), òî îáùåå êîëè÷åñòâîåäèíèö âî âñåõ ñëîâàõ ñîñòàâèò â ñðåäíåì sḡ , è ïðè ýòîì êàæäîå èç ýòèõ1ñëîâ â ñèëó íåðàâåíñòâà (5.7) áóäåò â ñðåäíåì 12 + 2m-àïïðîêñèìàöèåéû. Îòñþäà ìîæíî çàêëþ÷èòü àíàëîãè÷íî âûêëàäêå (5.8), ÷òî ñ âûñîêîés1âåðîÿòíîñòüþ õîòÿ áû 4mýòèõ ñëîâ áóäóò 12 + 4m-àïïðîêñèìàöèÿìè û.Óñëîâèå ãîâîðèò î òîì, ÷òî åñëè îñòàâèòü èç åäèíèö â ñëîâàõ zj òîëüêî s(ḡ−γ) øòóê, ò.å.
ïåðåéòè ê ñëîâàì z̃j , òî âñ¼ ðàâíî ñ âûñîêîé âåðîÿòíîñòüþ õîòÿs1áû 16mñëîâ îñòàíóòñÿ 12 + 4m-àïïðîêñèìàöèÿìè û. Èäåÿ çàêëþ÷àåòñÿ âòîì, ÷òî γ äîñòàòî÷íî ìàëî, ÷òîáû èçìåíåíèå â ñðåäíåì sγ áèòîâ ñ åäèíèöûíà íîëü íå ìîãëî èñïîðòèòü ñëèøêîì ìíîãî ñëîâ zj . Äàëåå ìû èçëîæèìýòó èäåþ ôîðìàëüíî.Îöåíèì âåðîÿòíîñòü íåâûïîëíåíèÿ âòîðîãî óñëîâèÿ, ò.å. ñèòóàöèè, êîs1ãäà ìåíüøå 16mñëîâ z̃1 , . . . , z̃s ÿâëÿþòñÿ 12 + 4m-àïïðîêñèìàöèÿìè û.(j) ýòîì ñëó÷àå îáùåå êîëè÷åñòâî ïàð (x, r ), äëÿ êîòîðûõ âûïîëíåíîs15z̃j (x) = û(x), ìåíüøå, ÷åì 16m· n̄ + s · ( 21 + 4m)n̄ = sn̄ · ( 21 + 16m).
Ïîñêîëüêó (êàê ìû äîãîâîðèëèñü) îáùåå êîëè÷åñòâî ïàð (x, r(j) ), äëÿ êîòîðûõ G(x, r(j) ) = 1, íå ïðåâîñõîäèò s(ḡ + γ), à îáùåå êîëè÷åñòâî åäèíèöâî âñåõ ñëîâàõ z̃j íå ìåíüøå s(ḡ − γ), òî îáùåå êîëè÷åñòâî òàêèõ ïàð, ÷òîG(x, r(j) ) íå ñîâïàäàåò ñ z̃j (x), è ïîòîìó ìîæåò ñîâïàäàòü ñ û(x), íå ïðåâûøàåò 2γs. Çíà÷èò, êîëè÷åñòâî ïàð, äëÿ êîòîðûõ G(x, r(j) ) = û(x), íå áîëüøå55n̄sn̄ · ( 21 + 16m) + 2γs = sn̄ · ( 12 + 16m+ 2 n̄γ ). Åñëè γ < 32m, òî ýòà âåëè÷èíà13ìåíüøå sn̄·( 2 + 8m ). Îäíàêî â ñèëó íåðàâåíñòâà (5.7) óñðåäí¼ííîå ïî ñëó÷àéíîìó âûáîðó r êîëè÷åñòâî x, äëÿ êîòîðûõ âûïîëíåíî G(x, r) = û(x), ðàâíî1n̄( 21 + 2m). Ïîýòîìó êîëè÷åñòâî ïàð (x, r(j) ), äëÿ êîòîðûõ G(x, r(j) ) = û(x),åñòü ñóììà s ñëó÷àéíûõ âåëè÷èí, êàæäàÿ èç êîòîðûõ èìååò ìàòåìàòè÷å1ñêîå îæèäàíèå íå ìåíüøå n̄( 12 + 2m).
Âíîâü ïðèìåíèâ íåðàâåíñòâî Õ¼ôô3äèíãà, ïîëó÷àåì, ÷òî âåðîÿòíîñòü òîãî, ÷òî ýòà ñóììà ìåíüøå sn̄ · ( 12 + 8m),1síå ïðåâîñõîäèò exp −2 64m2 s = exp − 32m2 . Ýòà âåðîÿòíîñòü ìàëà, åñëè sñóùåñòâåííî áîëüøå m.87Òðåòüå óñëîâèå çàêëþ÷àåòñÿ â ñëåäóþùåì: ìû çíàåì, ÷òî êîäîâîå ñëî1s-àïïðîêñèìàöèåé õîòÿ áû äëÿ 16mñëîâ z̃1 , . . . , z̃s .âî v ÿâëÿåòñÿ 12 + 4mÍàì íóæíî äîêàçàòü, ÷òî ïðè ðàññìîòðåíèè ìíîæåñòâà âñåõ ñëîâ z (r) âìå1ñòî îãðàíè÷åííîé è çàøóìëåííîé âûáîðêè z̃j ñëîâî v îñòàíåòñÿ 21 + 8m1(r)àïïðîêñèìàöèåé õîòÿ áû äëÿ äîëè 32m ñëîâ z . Èäåÿ äîêàçàòåëüñòâà âíîâüçàêëþ÷àåòñÿ â òîì, ÷òî ïðè ïåðåõîäå îò ñëîâ z̃j ê ñëîâàì zj íå áîëüøå 2sγáèòîâ ñìåíÿò ñâî¼ çíà÷åíèå ñ íóëÿ íà åäèíèöó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
