Диссертация (1103424), страница 6
Текст из файла (страница 6)
äîëÿ åäèíèö ñðåäè àðãóìåíòîâ)áîëüøå α.Âìåñòå ñ òåì, ñóùåñòâóþò ñõåìû êîíñòàíòíîé ãëóáèíû äëÿ ïðèáëèæ¼ííîãî âû÷èñëåíèÿ ïîðîãîâûõ ôóíêöèé [8; 52]. Ìû áóäåì èñïîëüçîâàòü ñëåäóþùóþ òåîðåìó:Òåîðåìà 2.32 ( [52]). Äëÿ ëþáîãî öåëîãî d > 3 è ëþáîãî ε = Ω(1/ logd−3 n)ñóùåñòâóåò ñõåìà ðàçìåðà poly(n) è ãëóáèíû d, âîçâðàùàþùàÿ 1 íà âõîäàõ âåñà 1/2 + ε è 0 íà âõîäàõ âåñà 1/2 − ε.Åñëè æå ïîðîã α íå ôèêñèðîâàí, à äîñòàòî÷íî áûñòðî ñòðåìèòñÿ ê íóëþñ ðîñòîì n, òî ïîðîãîâóþ ôóíêöèþ ìîæíî âû÷èñëèòü òî÷íî:Òåîðåìà 2.33 ( [8]). Äëÿ ëþáûõ n è i ñóùåñòâóåò ñõåìà ãëóáèíû d èðàçìåðà poly(n), âîçâðàùàþùàÿ 1 íà âõîäàõ äëèíû n, ñîäåðæàùèõ ìåíüøålogi n åäèíèö, è âîçâðàùàþùàÿ 0 íà îñòàëüíûõ âõîäàõ. Ïðè ýòîì ãëóáèíàd íå çàâèñèò îò n, íî ìîæåò çàâèñåòü îò i.2.5Ãåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåëÃåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë åù¼ îäèí îáúåêò, ôîðìàëèçóþùèé èíòóèòèâíîå ïîíÿòèå ïðîöåäóðà, ïðîèçâîäÿùàÿ íîâóþ ñëó÷àéíîñòü.Èñòîðè÷åñêè ýòè îáúåêòû ñòàëè èçó÷àòüñÿ ïåðâûìè, íî ñóùåñòâîâàíèå ìíîãèõ âèäîâ ãåíåðàòîðîâ äîêàçàíî ëèøü ïðè óñëîâèè âåðíîñòè òåõ èëè èíûõòåîðåòèêî-ñëîæíîñòíûõ ïðåäïîëîæåíèé, íàïðèìåð, î ñóùåñòâîâàíèè îäíîñòîðîííåé ôóíêöèè [24].
Íèñàí è Âèãäåðñîí [34] äîêàçàëè ñóùåñòâîâàíèåãåíåðàòîðîâ îïðåäåë¼ííîãî âèäà, íå îïèðàÿñü íà êàêèå-ëèáî ïðåäïîëîæåíèÿ, è ìû âîñïîëüçóåìñÿ ýòîé êîíñòðóêöèåé ñðàçó â äâóõ ãëàâàõ: 5 è 6.Îïðåäåëåíèå 2.34. Ïóñòü äëÿ êàæäîãî n çàäàí êëàññ Dn ôóíêöèéîòëè÷èòåëåé,îòîáðàæàþùèõ {0, 1}n â {0, 1}. Ñåìåéñòâî ôóíêöèéGn : {0, 1}k(n) → {0, 1}n íàçûâàåòñÿ ãåíåðàòîðîì ïñåâäîñëó÷àéíûõ ÷èñåëäëÿ êëàññà îòëè÷èòåëåé Dn , åñëè äëÿ ëþáîãî ìíîãî÷ëåíà p(·) ïðè âñåõ äîñòàòî÷íî áîëüøèõ n äëÿ âñåõ ôóíêöèé Dn èç Dn âûïîëíåíîPrx∈{0,1}k(n) [Dn (Gn (x)) = 1] − Pry∈{0,1}n [Dn (y) = 1] < 1 .p(n)3Çíà÷åíèå ìîæåò áûòü ëþáûì ïðè ðàâåíñòâå êîëè÷åñòâ íóëåé è åäèíèö ñðåäè àðãóìåíòîâ.27Êàê ïðàâèëî, â êà÷åñòâå êëàññà Dn áåðóò ëèáî ïîëèíîìèàëüíî âû÷èñëèìûå ôóíêöèè, ëèáî ôóíêöèè, âû÷èñëèìûå ñõåìàìè ïîëèíîìèàëüíîãî ðàçìåðà.
Îäíàêî, â òàêîì ñëó÷àå ñóùåñòâîâàíèå ãåíåðàòîðîâ óäà¼òñÿ äîêàçàòüòîëüêî ñ îïîðîé íà ðàçëè÷íûå òåîðåòèêî-ñëîæíîñòíûå ãèïîòåçû. Áåçóñëîâíûé ðåçóëüòàò ïîëó÷àåòñÿ, åñëè ðàññìîòðåòü êëàññ ôóíêöèé, âû÷èñëèìûõñõåìàìè ïîëèíîìèàëüíîãî ðàçìåðà è êîíñòàíòíîé ãëóáèíû.Òåîðåìà 2.35 ( [32; 34]). Äëÿ ëþáîé êîíñòàíòû d è ëþáîãî ïîëîæèòåëüíîãî ïîëèíîìà q(n) ñóùåñòâóåò ñåìåéñòâî ôóíêöèé Gn : {0, 1}k →{0, 1}n , ãäå k = O(log2d+6 n), òàêîå ÷òî:• Ôóíêöèÿ Gn âû÷èñëèìà íà ïàìÿòè poly(k);4• Ôóíêöèÿ Gn ÿâëÿåòñÿ ãåíåðàòîðîì ïñåâäîñëó÷àéíûõ ÷èñåë äëÿ êëàññà âñåõ ôóíêöèé, âû÷èñëèìûõ ñõåìàìè ðàçìåðà q(n) è ãëóáèíû íåáîëüøå d.Çàìåíèâ ïåðåìåííûå, ìîæíî ïîëó÷èòü ñëåäóþùåå ñëåäñòâèå, èñïîëüçóåìîå â äàëüíåéøåì.
×òîáû èñêëþ÷èòü ðàçíî÷òåíèÿ, ìû çàïèøåì âñå óïîìÿíóòûå â í¼ì ïîëèíîìû ÿâíî.Ñëåäñòâèå 2.36. Äëÿ ëþáîé êîíñòàíòû d è ëþáûõ ïîëîæèòåëüíûõ ïîëèíîìîâ p(n) è q(n) ñóùåñòâóþò ïîëèíîìû r(n) è s(n) è ñåìåéñòâî ôóíêp(n)öèé Gn : {0, 1}r(n) → {0, 1}2 , òàêèå ÷òî:• Ôóíêöèÿ Gn âû÷èñëèìà íà ïàìÿòè s(n);• Ôóíêöèÿ Gn ÿâëÿåòñÿ ãåíåðàòîðîì ïñåâäîñëó÷àéíûõ ÷èñåë äëÿ êëàññàâñåõ ôóíêöèé, âû÷èñëèìûõ ñõåìàìè ðàçìåðà íå áîëüøå 2q(n) è ãëóáèíû íå áîëüøå d.Äîêàçàòåëüñòâî.
Íàïðÿìóþ ïðèìåíèòü òåîðåìó 2.35 íå ïîëó÷èòñÿ, èç-çàòîãî ÷òî ïðè q(n) > np(n) âåëè÷èíà 2q(n) íå áóäåò ïîëèíîìîì îò 2p(n) .Âìåñòî ýòîãî ìû çàìåòèì ñëåäóþùåå: âî-ïåðâûõ, ñëó÷àé q(n) < p(n) òðèâèàëåí, ïîñêîëüêó ìû ó÷èòûâàåì âõîäíûå ýëåìåíòû â ðàçìåðå ñõåìû, òàê÷òî íèêàêàÿ ñõåìà ðàçìåðà 2q(n) íå ñìîæåò ïîëó÷èòü íà âõîä ñëîâî äëèíû2p(n) . Âî-âòîðûõ, ïî òåîðåìå 2.35 ñóùåñòâóþò ïîëèíîìû r0 (n) è s0 (n) è ñå0q(n)ìåéñòâî ôóíêöèé G0n : {0, 1}r (n) → {0, 1}2 , òàêèå ÷òî G0n âû÷èñëèìà íàÍàïîìíèì, ÷òî ìû ñ÷èòàåì ïàìÿòü òîëüêî íà ðàáî÷èõ ëåíòàõ ìàøèíû Òüþðèíãà. Èíà÷å ãîâîðÿ,äëÿ ëþáîãî x ëþáîé êîíêðåòíûé áèò çíà÷åíèÿ Gn (x) ìîæíî âû÷èñëèòü íà ïàìÿòè poly(k), õîòÿ îáùàÿäëèíà Gn (x) ýêñïîíåíöèàëüíà îò k = |x|.428ïàìÿòè s0 (n) è ÿâëÿåòñÿ ãåíåðàòîðîì ïñåâäîñëó÷àéíûõ ÷èñåë äëÿ êëàññàâñåõ ôóíêöèé, âû÷èñëèìûõ ñõåìàìè ðàçìåðà íå áîëüøå 2q(n) è ãëóáèíûíå áîëüøå d.
Äåéñòâèòåëüíî, ïîòðåáóåòñÿ ñëó÷àéíîå çåðíî äëèíû ïîðÿäêà2d+6log(2q(n) )= q(n)2d+6 , ÷òî ÿâëÿåòñÿ ïîëèíîìîì.  ÷àñòíîñòè, ôóíêöèÿG0n áóäåò ãåíåðàòîðîì ïñåâäîñëó÷àéíûõ ÷èñåë äëÿ êëàññà âñåõ ôóíêöèé,âû÷èñëèìûõ òàêèìè ñõåìàìè è çàâèñÿùèõ òîëüêî îò ïåðâûõ 2p(n) áèòîâñëîâà (ýòî êîððåêòíî, ïîñêîëüêó p(n) 6 q(n)). Òàêèì îáðàçîì, â êà÷åñòâåGn ìîæíî âçÿòü ïðåôèêñ äëèíû 2p(n) ôóíêöèè G0n , à ïîëèíîìû âçÿòü òåæå: r(n) = r0 (n) = q(n)2d+6 , s(n) = s0 (n).Îòñþäà âûâîäèòñÿ ñëåäóþùèé áàçîâûé ïðèíöèï:Ëåììà 2.37. Ïóñòü Cn åñòü íåêîòîðîå ìíîæåñòâî êîìáèíàòîðíûõ îáúåêòîâ, çàêîäèðîâàííûõ ñòðîêàìè äëèíû 2poly(n) .
Ïóñòü Pn åñòü ñâîéñòâî,âûïîëíåííîå õîòÿ áû äëÿ (êîíñòàíòíîé) äîëè α > 0 îáúåêòîâ èç Cn , ãäåα > 0 åñòü íåêîòîðàÿ êîíñòàíòà, ïðè ýòîì ýòî ñâîéñòâî ìîæíî ðàñïîçíàòü ñõåìàìè ðàçìåðà 2poly(n) è êîíñòàíòíîé ãëóáèíû. Òîãäà ïðè âñåõäîñòàòî÷íî áîëüøèõ n ñâîéñòâî Pn âûïîëíåíî äëÿ äîëè íå ìåíüøå α/2çíà÷åíèé Gn , ãäå Gn ôóíêöèÿ èç ïðåäûäóùåãî ñëåäñòâèÿ.Äîêàçàòåëüñòâî. Ñîãëàñíî ñëåäñòâèþ 2.36, ôóíêöèÿ Gn îáìàíûâàåò âñåñõåìû ðàçìåðà 2poly(n) è êîíñòàíòíîé ãëóáèíû, â ÷àñòíîñòè ñõåìû, ðàñïîçíàþùèå Pn . Ðàç äîëÿ îáúåêòîâ, óäîâëåòâîðÿþùèõ ñâîéñòâó Pn , ñðåäè âñåõîáúåêòîâ íå ìåíüøå α, òî ïðè äîñòàòî÷íî áîëüøèõ n äîëÿ îáúåêòîâ, óäîâëåòâîðÿþùèõ ñâîéñòâó Pn , ñðåäè çíà÷åíèé Gn äîñòàòî÷íî áëèçêà ê α, õîòÿáû áîëüøå α/2.2.6Âû÷èñëèòåëüíàÿ XOR-Ëåììà ëèòåðàòóðå âñòðå÷àåòñÿ íåñêîëüêî óòâåðæäåíèé, êîòîðûå ïîëó÷èëèíàçâàíèå XOR-ëåììà. Íàì ïîòðåáóåòñÿ òàê íàçûâàåìàÿ âû÷èñëèòåëüíàÿ XOR-Ëåììà, äîêàçàííàÿ Âàçèðàíè è Âàçèðàíè â ðàáîòå [51].
Ýòà ëåììàñâÿçûâàåò âåðîÿòíîñòü ïðåäñêàçàíèÿ ïñåâäîñëó÷àéíîé âåëè÷èíû è óñïåøíîñòü îòëè÷èòåëÿ ýòîé ïñåâäîñëó÷àéíîé âåëè÷èíû îò èñòèííî ñëó÷àéíîé.Ìû ñôîðìóëèðóåì ýòó ëåììó â óñå÷¼ííîé ôîðìå, ïîëíóþ ôîðìóëèðîâêóè îáçîð îñòàëüíûõ XOR-ëåìì ìîæíî íàéòè â îáçîðå [20].29Òåîðåìà 2.38 (Âû÷èñëèòåëüíàÿ XOR-ëåììà [51], ÷àñòíûé ñëó÷àé). Ïóñòüz åñòü ñëó÷àéíàÿ âåëè÷èíà, ðàâíîìåðíî ðàñïðåäåë¼ííàÿ íà {0, 1}m , à σåñòü ñëó÷àéíûé áèò (ò.å. ñëó÷àéíàÿ âåëè÷èíà, ðàâíîìåðíî ðàñïðåäåë¼ííàÿ íà {0, 1}).
Ïóñòü f : {0, 1}m → {0, 1}k è g : {0, 1}m → {0, 1} ñóòü ïîëèíîìèàëüíî âû÷èñëèìûå ôóíêöèè. Ïóñòü T : {0, 1}k × {0, 1} → {0, 1} íåêîòîðûé âåðîÿòíîñòíûé ïîëèíîìèàëüíûé àëãîðèòì, ïðè÷¼ìPrz [T (f (z), g(z)) = 1] − Prz,σ [T (f (z), σ) = 1] > ε.(2.3)Ïóñòü Gσ : {0, 1}k → {0, 1} àëãîðèòì, îïðåäåë¼ííûé ðàâåíñòâîìGσ (x) = T (x, σ) ⊕ σ ⊕ 1. (Ãäå ⊕ îáîçíà÷àåò ñëîæåíèå ïî ìîäóëþ 2). ÒîãäàPrz,σ [Gσ (f (z)) = g(z)] >2.71+ ε.2(2.4)Îòäåëüíûå èñïîëüçóåìûå íåðàâåíñòâà ýòîì ðàçäåëå ìû ïðèâåä¼ì ñïèñîê íåðàâåíñòâ, êîòîðûå áóäóò èñïîëüçîâàòüñÿ â âûêëàäêàõ.Âíà÷àëå äîêàæåì íåñëîæíóþ îöåíêó äëÿ ÷èñëà ñî÷åòàíèé.
Îáùåèçâåñòn(n−1)...(n−k+1)íî, ÷òî Cnk =. Îöåíèâ êàæäûé ìíîæèòåëü â ÷èñëèòåëå ÷èñëîìk!nkkn, ïîëó÷èì, ÷òî Cn 6 k! .  ñèëó èçâåñòíîé ôîðìóëû Ñòèðëèíãà âûïîëíåíîkk! > ke , ÷òî ïðè ïîäñòàíîâêå äà¼ò îöåíêóCnk < ne kk.(2.5)Äàëåå, ñôîðìóëèðóåì íåñêîëüêî âàðèàíòîâ íåðàâåíñòâà ×åðíîâà, îöåíèâàþùåãî ñâåðõó âåðîÿòíîñòü áîëüøèõ óêëîíåíèé. Ïåðâûé âàðèàíò îáû÷íîíàçûâàþò íåðàâåíñòâîì Õ¼ôäèíãà.Òåîðåìà 2.39 ( [23]).
Ïóñòü ξ1 , . . . , ξn ñóòü íåçàâèñèìûå îäèíàêîâî ðàñïðåäåë¼ííûå ñëó÷àéíûå âåëè÷èíû, ïðèíèìàþùèå çíà÷åíèÿ èç [0, 1] è èìåþùèå ìàòåìàòè÷åñêîå îæèäàíèå p. Òîãäà äëÿ ëþáîãî ε > 0 âåðîÿòíîñòüP2ñîáûòèÿξi > (p + ε)n íå ïðåâûøàåò e−2ε n , è âåðîÿòíîñòü ñîáûòèÿP2ξi < (p − ε)n òàêæå íå ïðåâûøàåò e−2ε n .Äàëåå, íàì ïîòðåáóåòñÿ áîëåå îáùàÿ ôîðìà, êîòîðóþ îáû÷íî íàçûâàþòíåðàâåíñòâîì ×åðíîâàÕ¼ôäèíãà:30Òåîðåìà 2.40 ( [23]).
Ïóñòü ξ1 , . . . , ξn ñóòü íåçàâèñèìûå îäèíàêîâî ðàñïðåäåë¼ííûå áåðíóëëèåâñêèå ñëó÷àéíûå âåëè÷èíû, èìåþùèå ìàòåìàòèP÷åñêîå îæèäàíèå p. Òîãäà äëÿ ëþáîãî ε > 0 âåðîÿòíîñòü ñîáûòèÿξi >(p + ε)n íå ïðåâûøàåò e−D(p+εkp)n , ãäå D(xky) ðàññòîÿíèå ÊóëüáàêàËåéáëåðà ìåæäó áåðíóëëèåâñêèìè ñëó÷àéíûìè âåëè÷èíàìè, ïðèíèìàþùèìè çíà÷åíèå 1 ñ âåðîÿòíîñòÿìè x è y ñîîòâåòñòâåííî, ò.å.D(xky) = x ln1−xx+ (1 − x) ln.y1−y(2.6)Ìû áóäåì ïðèìåíÿòü ýòî íåðàâåíñòâî äëÿ ñïåöèàëüíîãî ñëó÷àÿ, êîãäàε = p.
 ýòîì ñëó÷àå âåðíî ñëåäóþùååÑëåäñòâèå 2.41. Ïóñòü ξ1 , . . . , ξn ñóòü íåçàâèñèìûå îäèíàêîâî ðàñïðåäåë¼ííûå áåðíóëëèåâñêèå ñëó÷àéíûå âåëè÷èíû ñ âåðîÿòíîñòüþ âûïàäåíèÿPåäèíèöû p < 12 . Òîãäà âåðîÿòíîñòü ñîáûòèÿξi > 2pn íå ïðåâûøàåò1e− 3 pn .Çàìåòèì, ÷òî ïðèìåíåíèå òåîðåìû 2.39 ïðè ìàëûõ p äàëî áû õóäøóþ2îöåíêó e−2p n .Äîêàçàòåëüñòâî. Ïîäñòàâèì â ôîðìóëó (2.6) 2p âìåñòî x è p âìåñòî y .Ïîëó÷èì âåëè÷èíó2p ln 2 + (1 − 2p)(ln(1 − 2p) − ln(1 − p)).(2.7)Âîñïîëüçóåìñÿ íåðàâåíñòâîìln(1 − p) < −p,(2.8)à òàêæå ôîðìóëîé Òåéëîðà äëÿ ôóíêöèè (1−2p) ln(1−2p) â ôîðìå Ëàãðàí4p3æà: (1 − 2p) ln(1 − 2p) = −2p + 2p2 + 3(1−θ)2 , îòêóäà(1 − 2p) ln(1 − 2p) > −2p + 2p2 .(2.9)Èñïîëüçîâàâ íåðàâåíñòâà (2.8) è (2.9), îöåíèì âåëè÷èíó (2.7) âåëè÷èíîé2p ln 2 + p(1 − 2p) − 2p + 2p2 = (2 ln 2 − 1)p > 31 p. Ïîäñòàâèâ ýòó îöåíêó âåëè÷èíû D(2pkp) â óòâåðæäåíèå òåîðåìû 2.40, ïîëó÷àåì óòâåðæäåíèåñëåäñòâèÿ. Òàêèì îáðàçîì, ñëåäñòâèå äîêàçàíî.31Ãëàâà 3Ïðèìåíåíèå ýêñòðàêòîðîâ äëÿäîêàçàòåëüñòâà òåîðåìû Ìó÷íèêà îáóñëîâíîé ñëîæíîñòèÒåîðåìà Àí.
À. Ìó÷íèêà ( [30]) îäíî èç ãëàâíûõ äîñòèæåíèé òåîðèèêîëìîãîðîâñêîé ñëîæíîñòè íà÷àëà XXI âåêà. Íåôîðìàëüíî îíà ãëàñèò, ÷òîäëÿ ëþáûõ ñëîâ a è b ñóùåñòâóåò ïðîãðàììà p, ïå÷àòàþùàÿ a íà âõîäå b,îäíîâðåìåííî èìåþùàÿ áëèçêóþ ê ìèíèìàëüíî âîçìîæíîé äëèíó è ïðîñòàÿ îòíîñèòåëüíî a. Ýòîò ðåçóëüòàò î÷åíü ñèëüíûé, ïîñêîëüêó àëãîðèòì,ïîðîæäàþùèé p èç a, ïðàêòè÷åñêè íè÷åãî íå çíàåò ïðî b, íî ïðè ýòîì çàêëàäûâàåò â ïðîãðàììó p âñþ èíôîðìàöèþ îá a, îòñóòñòâóþùóþ â b. Ìîæíîïðåäñòàâèòü ñåáå òàêóþ êîììóíèêàöèîííóþ ñèòóàöèþ: èìåþòñÿ äâà àãåíòà: Àëèñà, çíàþùàÿ a, è Áîá, çíàþùèé b.
Àëèñà äîëæíà ïåðåäàòü Áîáóèíôîðìàöèþ îá a, èñïîëüçóÿ êàíàë îãðàíè÷åííîé ïðîïóñêíîé ñïîñîáíîñòè(ñì. ðèñ. 3.1). Î÷åâèäíî, ÷òî ýòî íåâîçìîæíî ñäåëàòü àëãîðèòìè÷åñêè, åñëè ïðîïóñêíàÿ ñïîñîáíîñòü ìåíüøå óñëîâíîé ñëîæíîñòè a îòíîñèòåëüíî b.Òåîðåìà ãëàñèò, ÷òî ýòà îöåíêà òî÷íà, åñëè ðàçðåøèòü Àëèñå è Áîáó èñïîëüçîâàòü íåáîëüøîå ÷èñëî áèòîâ ñîâåòà, ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
