Диссертация (1103424), страница 5
Текст из файла (страница 5)
Áîëåå òîãî, â ýòîé êîìáèíàöèè áóäåò íå áîëüøå N íåíóëåâûõêîýôôèöèåíòîâ.Ïåðåôîðìóëèðóåì ïîñëåäíåå óòâåðæäåíèå ñëåäóþùèì îáðàçîì: ïóñòüäàíî N íåîòðèöàòåëüíûõ ÷èñåë, êàæäîå èç êîòîðûõ íå ïðåâûøàåò 1/Kîò îáùåé ñóììû. Íàçîâ¼ì îïåðàöèåé îäíîâðåìåííîå óìåíüøåíèå K èçýòèõ ÷èñåë íà îäíó è òó æå âåëè÷èíó (âåëè÷èíó îïåðàöèè), ïðè êîòîðîìâñå ÷èñëà îñòàþòñÿ íåîòðèöàòåëüíûìè è íèêàêîå èç íèõ ïî-ïðåæíåìó íåïðåâûøàåò 1/K îò îáùåé ñóììû. Òîãäà íå áîëåå ÷åì çà N îïåðàöèé ìîæíîîáðàòèòü âñå ÷èñëà â 0.Äîêàæåì ñôîðìóëèðîâàííîå óòâåðæäåíèå ìåòîäîì ìàòåìàòè÷åñêîé èíäóêöèè. Áàçà (N = K = 1) î÷åâèäíà.  ïðîöåññå ïåðåõîäà áóäåì óìåíüøàòü íà åäèíèöó ëèáî è N , è K , ëèáî òîëüêî N . Âûáåðåì ïðîèçâîëüíûåÒàêæå àâòîðó èçâåñòíî îñòðîóìíîå äîêàçàòåëüñòâî, èñïîëüçóþùåå âûïóêëûé àíàëèç, îïèñàííîåÈëü¼é Èðõèíûì [4] ïî ìîòèâàì ëåêöèé Äìèòðèÿ Èöûêñîíà [5].221K íåíóëåâûõ ÷èñåë èç íàáîðà.
Óìåíüøèì èõ íà ìàêñèìàëüíî âîçìîæíóþâåëè÷èíó, ïðè êîòîðîé íå íàðóøàþòñÿ óñëîâèÿ. Âîçìîæíû äâà ñëó÷àÿ. Âîïåðâûõ, îäíî èç âûáðàííûõ ÷èñåë ìîæåò îáðàòèòüñÿ â íóëü, òîãäà ìîæíîåãî èñêëþ÷èòü è ïðèìåíèòü ïðåäïîëîæåíèå èíäóêöèè äëÿ N − 1 è K . Äåéñòâèòåëüíî, êàæäîå èç ÷èñåë ïî-ïðåæíåìó íå áîëüøå 1/K îò îáùåé ñóììû,è äëÿ îñòàâøèõñÿ ÷èñåë äîñòàòî÷íî N − 1 îïåðàöèè. Âî-âòîðûõ, îäíî èçíåâûáðàííûõ ÷èñåë (îáîçíà÷èì åãî çà x) ìîæåò ñòàòü ðàâíûì 1/K îò îáùåé ñóììû. (ßñíî, ÷òî íè ñ êàêèì èç âûáðàííûõ ÷èñåë òàêîãî ñëó÷èòüñÿ íåìîæåò, ïîñêîëüêó îíè óìåíüøàþòñÿ, à íåâûáðàííûå íåò).  òàêîì ñëó÷àåñóììà âñåõ ÷èñåë, êðîìå x, ðàâíà (K − 1)/K îáùåé ñóììû, à êàæäîå èç÷èñåë íå ïðåâûøàåò K1 K−1K = 1/(K − 1) ñóììû âñåõ ÷èñåë, êðîìå x.
Òàêèìîáðàçîì, ê íàáîðó ÷èñåë áåç x ìîæíî ïðèìåíèòü ïðåäïîëîæåíèå èíäóêöèèäëÿ N − 1 è K − 1. Ê êàæäîìó íàáîðó ÷èñåë, ê êîòîðîìó ïðèìåíÿåòñÿîïåðàöèÿ èç ïðåäïîëîæåíèÿ èíäóêöèè, ìû äîáàâèì ÷èñëî x, ñäåëàâ òàêèìîáðàçîì èç K − 1 ÷èñëà K ÷èñåë. Ñóììà âåëè÷èí âñåõ ýòèõ îïåðàöèé ðàâíà1/(K − 1) îò ñóììû âñåõ ÷èñåë, êðîìå x, ò.å. 1/(K − 1) · (K − 1)/K = 1/Kîò ñóììû âñåõ ÷èñåë, ò.å. ðàâíà x.
Òàêèì îáðàçîì, ïðè äîáàâëåíèè x êîâñåì íàáîðàì ïîñëå ïðîâåäåíèÿ âñåõ îïåðàöèé âñå ÷èñëà îáíóëÿòñÿ, ÷òî èòðåáîâàëîñü.Âåðîÿòíîñòíûì ìåòîäîì [1] ìîæíî äîêàçàòü ñóùåñòâîâàíèå ýêñòðàêòîðîâ ñ î÷åíü õîðîøèìè ïàðàìåòðàìè. À èìåííî, âåðíà ñëåäóþùàÿ òåîðåìà.Òåîðåìà 2.19 ( [36]). Ïðè âñåõ n, k è ε ñóùåñòâóþò ýêñòðàêòîðû äëÿd = log(n − k) + 2 log(1/ε) + O(1) è m = k + d − log(1/ε) − O(1).Îäíàêî äëÿ ïðèëîæåíèé æåëàòåëüíî, ÷òîáû ýêñòðàêòîðû çàäàâàëèñü ÿâíîé êîíñòðóêöèåé. Ôîðìàëüíî ïîä ÿâíûìè ýêñòðàêòîðàìè ïîíèìàþòñÿ âû÷èñëÿåìûå çà ïîëèíîìèàëüíîå âðåìÿ:Îïðåäåëåíèå 2.20.
Ïóñòü m(n), d(n), k(n) è ε(n) ñóòü âû÷èñëèìûå çàïîëèíîìèàëüíîå âðåìÿ ôóíêöèè íàòóðàëüíîãî àðãóìåíòà. (Çíà÷åíèÿ ïåðâûõ òð¼õ òàêæå íàòóðàëüíûå ÷èñëà, ïîñëåäíåé ðàöèîíàëüíûå ÷èñëàíà (0, 1)). Òîãäà ñåìåéñòâî ôóíêöèé Extn : {0, 1}n × {0, 1}d(n) → {0, 1}m(n)íàçûâàåòñÿ ñåìåéñòâîì ÿâíûõ (k, ε)-ýêñòðàêòîðîâ (èëè ïðîñòî ÿâíûì (k, ε)ýêñòðàêòîðîì), åñëè Extn âû÷èñëÿåòñÿ çà ïîëèíîìèàëüíîå îò n âðåìÿ è ïðèâñåõ n ÿâëÿåòñÿ (k(n), ε(n))-ýêñòðàêòîðîì.22Çà ïîñëåäíèå 20 ëåò ïîñòðîåíî ìíîæåñòâî ðàçëè÷íûõ ÿâíûõ ýêñòðàêòîðîâ, íî íè îäíà èç êîíñòðóêöèé [17; 21; 29; 33; 37; 38; 48; 49] íå äà¼òîïòèìàëüíûõ ïàðàìåòðîâ. Íàì ïîòðåáóþòñÿ ýêñòðàêòîðû, ñóùåñòâîâàíèåêîòîðûõ óòâåðæäàåò ñëåäóþùàÿ òåîðåìà:Òåîðåìà 2.21 ( [37]).
Äëÿ âñåõ n, k , m è ε > 0, òàêèõ ÷òîm 6 k 6 n,ñóùåñòâóþò ÿâíûå (k , ε)-ýêñòðàêòîðû äëÿ d = OO(log2 (n/ε) · log(1/γ)), ãäå γ =k−m+1m−1log2 (n/ε)log(k/m)è äëÿ d =< 21 .Ìû âîñïîëüçóåìñÿ ýòîé òåîðåìîé äëÿ òàêèõ ïàðàìåòðîâ, èç êîòîðûõâûâîäèòñÿÑëåäñòâèå 2.22. Äëÿ âñåõ n, k 6 n è ε > 1/ poly(n) ñóùåñòâóþò ÿâíûå(k, ε)-ýêñòðàêòîðû äëÿ m = k è d = O(log3 n).Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ òåîðåìîé 2.21 äëÿ m = k è ε =111/ poly(n). Òîãäà γ = m−1= k−1è d = O(log2 (n/ε) · log(1/γ)) =O(log2 (poly(n)) · log(k − 1)) = O(log3 n).Ýêñòðàêòîðû ñ äâóìÿ èñòî÷íèêàìè, êàê è ýêñòðàêòîðû ñ îäíèì èñòî÷íèêîì, óäîáíî ðàññìàòðèâàòü íå êàê ôóíêöèè íà ñëîâàõ, à êàê êîìáèíàòîðíûåîáúåêòû, à èìåííî ðàñêðàñêè êâàäðàòíûõ òàáëèö:Îïðåäåëåíèå 2.23. Ðàñêðàñêó òàáëèöû A × A â ìíîæåñòâî öâåòîâ C , ò.å.ôóíêöèþ Col : A × A → C , íàçîâ¼ì (K, ε)-ýêñòðàêòîðíîé, åñëè äëÿ ëþáûõìíîæåñòâ S ⊂ A è T ⊂ A ðàçìåðà íå ìåíüøå K è ëþáîãî ìíîæåñòâà Y ⊂ Câûïîëíåíî |Y | | Col−1 (Y ) ∩ (S × T )| −(2.2) < ε, |C||S| · |T |èíûìè ñëîâàìè, äîëÿ êëåòîê ïðÿìîóãîëüíèêà S ×T , ðàñêðàøåííûõ â öâåòàèç Y , îòëè÷àåòñÿ îò äîëè öâåòîâ èç Y ñðåäè âñåõ öâåòîâ íå áîëüøå, ÷åìíà ε.Ñîîòâåòñòâèå ìåæäó ôóíêöèÿìè è ðàñêðàñêàìè òàáëèö ñòðîèòñÿ åñòåñòâåííûì îáðàçîì, è ìîæíî äîêàçàòü ïî àíàëîãèè ñ óòâåðæäåíèåì 2.17òåîðåìó îá ýêâèâàëåíòíîñòè äâóõ îïðåäåëåíèé.Òàêæå ðàññìàòðèâàþòñÿ ñëåäóþùèå óñèëåíèÿ ïîíÿòèé ýêñòðàêòîðà:Îïðåäåëåíèå 2.24.
Ôóíêöèÿ Ext : {0, 1}n × {0, 1}d → {0, 1}m íàçûâàåòñÿ(k, ε)-ýêñòðàêòîðîì ñ îäíèì èñòî÷íèêîì â ñèëüíîì ñìûñëå, åñëè äëÿ ëþáîé23ñëó÷àéíîé âåëè÷èíû ξ íà {0, 1}n ñ ìèíèìàëüíîé ýíòðîïèåé íå ìåíüøå k èñëó÷àéíîé âåëè÷èíû η , ðàñïðåäåë¼ííîé ðàâíîìåðíî íà {0, 1}d íåçàâèñèìîîò ξ , èíäóöèðîâàííàÿ âåëè÷èíà (Ext(ξ, η), η) ðàñïîëîæåíà íà ðàññòîÿíèèíå áîëüøå ε îò Um+d .Èíòóèòèâíûé ñìûñë óñèëåíèÿ òàêîâ: ýêñòðàêòîð èçâëåêàåò ñëó÷àéíîñòüèìåííî èç ñëàáîãî èñòî÷íèêà, à íå èç ïðåäîñòàâëåííûõ åìó èñòèííî ñëó÷àéíûõ áèòîâ.Îïðåäåëåíèå 2.25. Ôóíêöèÿ Ext : {0, 1}n × {0, 1}n → {0, 1}m íàçûâàåòñÿ (k, ε)-ýêñòðàêòîðîì ñ äâóìÿ èñòî÷íèêàìè â ñèëüíîì ñìûñëå, åñëè äëÿ ëþáûõ íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ξ1 è ξ2 , òàêèõ ÷òîH∞ (ξ1 ) > k è H∞ (ξ2 ) > k , âûïîëíåíî dist((ξ1 , Ext(ξ1 , ξ2 )), (ξ1 , Um )) < εè dist((Ext(ξ1 , ξ2 ), ξ2 ), (Um , ξ2 )) < ε, ãäå ðàñïðåäåëåíèå Um íå çàâèñèò îò ξ1è ξ2 .Çäåñü èíòóèòèâíûé ñìûñë ñîñòîèò â òîì, ÷òî ýêñòðàêòîð ïðîèçâîäèòíîâóþ ñëó÷àéíîñòü, íå çàâèñÿùóþ íè îò îäíîãî èç íà÷àëüíûõ èñòî÷íèêîâ.2.3Êîëìîãîðîâñêèå ýêñòðàêòîðûÊîëìîãîðîâñêèå ýêñòðàêòîðû èíîé ñïîñîá ôîðìàëèçàöèè ïðîöåäóðû,èçâëåêàþùåé ñëó÷àéíîñòü èç íåðàâíîìåðíîãî èñòî÷íèêà ñëó÷àéíîñòè.Ïîä îáúåêòàìè, ñîäåðæàùèìè ñëó÷àéíîñòü, ïîíèìàþòñÿ òåïåðü íå ðàñïðåäåëåíèÿ, à êîíå÷íûå ñëîâà, à ïîä ìåðîé ñëó÷àéíîñòè êîëìîãîðîâñêàÿñëîæíîñòü: ÷åì áëèæå ñëîæíîñòü ñëîâà ê åãî äëèíå, òåì áîëåå ñëîâî ñëó÷àéíî.
Êàê è äëÿ îáû÷íûõ ýêñòðàêòîðîâ, îäíîãî èñòî÷íèêà íåäîñòàòî÷íîäëÿ èçâëå÷åíèÿ ñëó÷àéíîñòè: ëþáàÿ (âñþäó îïðåäåë¼ííàÿ) âû÷èñëèìàÿïðîöåäóðà íå óìåíüøàåò äåôåêò ñëó÷àéíîñòè (ò.å. ðàçíîñòü ìåæäó äëèíîé è ñëîæíîñòüþ) äëÿ êàêîãî-òî âõîäà. Ïîýòîìó èñòî÷íèêîâ ñëó÷àéíîñòèäîëæíî áûòü õîòÿ áû äâà. Ñ äðóãîé ñòîðîíû, òðåáîâàíèå íåçàâèñèìîñòèìîæíî îñëàáèòü è òðåáîâàòü ëèøü îãðàíè÷åííîé çàâèñèìîñòè.Îïðåäåëåíèå 2.26. Çàâèñèìîñòüþ ìåæäó ñòðîêàìè x è y íàçûâàåòñÿâåëè÷èíà dep(x, y) = C(x) + C(y) − C(x, y).Íåêîòîðûå àâòîðû èñïîëüçóþò äðóãèå îïðåäåëåíèÿ çàâèñèìîñòè, îòëè÷àþùèåñÿ îò èñõîäíîãî íà ñëàãàåìîå ïîðÿäêà O(log n), íàïðèìåð:24Óòâåðæäåíèå 2.27 (Òåîðåìà ÊîëìîãîðîâàËåâèíà, ñì.
[2], òåîðåìà 21).dep(x, y) = C(x) − C(x|y) + O(log n) = C(y) − C(y|x) + O(log n).Òàêæå çàâèñèìîñòü ÷àñòî íàçûâàþò âçàèìíîé èíôîðìàöèåé è îáîçíà÷àþò I(x : y).Òåïåðü îïðåäåëèì ïîíÿòèå êîëìîãîðîâñêîãî ýêñòðàêòîðà. Îíî áóäåò àíàëîãîì îïðåäåëåíèÿ ýêñòðàêòîðà ñ äâóìÿ èñòî÷íèêàìè.Îïðåäåëåíèå 2.28. Ôóíêöèÿ KExt : {0, 1}n × {0, 1}n → {0, 1}m íàçûâàåòñÿ (k, α, d)-êîëìîãîðîâñêèì ýêñòðàêòîðîì, åñëè äëÿ âñåõ x è y , òàêèõ ÷òîC(x) > k , C(y) > k è dep(x, y) < α, âûïîëíåíî C(KExt(x, y)) > m − d.Äîêàçàíî, ÷òî ñâîéñòâà ýêñòðàêòîðà ñ äâóìÿ èñòî÷íèêàìè è êîëìîãîðîâñêîãî ýêñòðàêòîðà î÷åíü áëèçêè.
Áîëåå êîíêðåòíî, ìîæíî äàòü îïðåäåëåíèåïðèáëèæ¼ííîãî ýêñòðàêòîðà (almost extractor) â òåðìèíàõ âåðîÿòíîñòíûõ ðàñïðåäåëåíèé è ìèí-ýíòðîïèè, êîòîðîå áóäåò ýêâèâàëåíòíî îïðåäåëåíèþ êîëìîãîðîâñêîãî ýêñòðàêòîðà ñ òî÷íîñòüþ äî íåáîëüøîãî óõóäøåíèÿïàðàìåòðîâ ïðè ïåðåõîäå â êàæäóþ ñòîðîíó. Çà ïîäðîáíîñòÿìè îòñûëàåì÷èòàòåëÿ ê îðèãèíàëüíûì ðàáîòàì [18; 22], à òàêæå îáçîðó [56].Îïðåäåëåíèå êîëìîãîðîâñêîãî ýêñòðàòîðà òàêæå ìîæíî óñèëèòü:Îïðåäåëåíèå 2.29.
Ôóíêöèÿ KExt : {0, 1}n × {0, 1}n → {0, 1}m íàçûâàåòñÿ (k, α, d)-êîëìîãîðîâñêèì ýêñòðàêòîðîì â ñèëüíîì ñìûñëå, åñëè äëÿâñåõ x è y , òàêèõ ÷òî C(x) > k , C(y) > k è dep(x, y) < α, âûïîëíåíîC(KExt(x, y)|x) > m − d è C(KExt(x, y)|y) > m − d.Ïîñòðîåíèå êîëìîãîðîâñêèõ ýêñòðàêòîðîâ, â òîì ÷èñëå â ñèëüíîì ñìûñëå, îïèñàíî â ðàáîòàõ Ìàðèóñà Çèìàíäà [5355].
Êîíñòðóêöèè Çèìàíäà îñíîâàíû íà ïàðàëëåëèçìå ìåæäó ñëîæíîñòíûìè è êîìáèíàòîðíûìè ñâîéñòâàìè ôóíêöèé. Ïðèâåä¼ì ôîðìóëèðîâêè òåîðåì, ïîëó÷åííûõ Çèìàíäîì:Òåîðåìà 2.30 ( [54], òåîðåìà 3.1, è [55], òåîðåìà 4). Ïóñòü k(n) è α(n)ñóòü âû÷èñëèìûå ôóíêöèè, òàêèå ÷òî 1 < k(n) < n è 1 < α(n) < k(n) −O(log n). Òîãäà ñóùåñòâóþò (k(n), α(n), α(n) + O(log n))-êîëìîãîðîâñêèéýêñòðàêòîð äëÿ m = 2k(n) − O(log n) è (k(n), α(n), α(n) + O(log n))êîëìîãîðîâñêèé ýêñòðàêòîð â ñèëüíîì ñìûñëå äëÿ m = k(n) − O(log n). ãëàâå 6 ìû îáîáùèì ïîíÿòèå êîëìîãîðîâñêîãî ýêñòðàêòîðà íà ñëó÷àéñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü è ïåðåëîæèì äîêàçàòåëüñòâî Çèìàíäà íà ýòîò ñëó÷àé.
Òàì æå ìû îïèøåì îñíîâíîé êîìáèíàòîðíûé èíñòðó25ìåíò, ââåä¼ííûé Çèìàíäîì è èñïîëüçîâàííûé èì äëÿ äîêàçàòåëüñòâà ï¼ñòðûå è ðàâíîìåðíî ï¼ñòðûå òàáëèöû.2.4Ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâÑõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ äàâíî èçó÷àþòñÿ â òåîðèè ñëîæíîñòè âû÷èñëåíèé. Ðàçíûå àâòîðû èñïîëüçóþò ñëåãêà îòëè÷íûå îïðåäåëåíèÿ, ïîýòîìó ìû óòî÷íèì îïðåäåëåíèå, à òàêæå ïðèâåä¼ì ôîðìóëèðîâêèòåîðåì, êîòîðûå íàì ïîòðåáóþòñÿ.Ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ áóäåì íàçûâàòü îðèåíòèðîâàííûé ãðàô áåç öèêëîâ, êàæäàÿ âåðøèíà êîòîðîãî ïîìå÷åíà îäíîé èç ìåòîêi, o, ¬, ∧, ∨.
Íàêëàäûâàþòñÿ ñëåäóþùèå óñëîâèÿ: âåðøèíû ñ ìåòêàìè iíå èìåþò âõîäÿùèõ ð¼áåð, âåðøèíû ñ ìåòêàìè o èëè ¬ èìåþò ðîâíî îäíîâõîäÿùåå ðåáðî, âåðøèíû ñ ìåòêàìè ∧ èëè ∨ èìåþò õîòÿ áû îäíî âõîäÿùåå ðåáðî, âåðøèíû ñ ìåòêàìè o íå èìåþò èñõîäÿùèõ ð¼áåð, à âåðøèíû ñìåòêàìè ¬, ∧, ∨ èìåþò õîòÿ áû îäíî èñõîäÿùåå ðåáðî. Îòñóòñòâèå öèêëîâïîçâîëÿåò êîððåêòíî îïðåäåëèòü âûñîòó êàæäîé âåðøèíû êàê ìàêñèìàëüíóþ äëèíó ïóòè, èäóùåãî èç îäíîé èç âåðøèí ñ ìåòêîé i â äàííóþ.
Åñëèâåðøèíàì ñ ìåòêàìè i ïðèñâîèòü áóëåâû çíà÷åíèÿ, òî çíà÷åíèÿ â ëþáîéäðóãîé âåðøèíå ìîæíî ïîñ÷èòàòü, ïðèìåíèâ ôóíêöèþ, ñîîòâåòñòâóþùóþå¼ ìåòêå, ê çíà÷åíèÿì â âåðøèíàõ, èç êîòîðûõ â íå¼ èä¼ò ðåáðî. (Òàêèåâåðøèíû áóäåì íàçûâàòü ïðîîáðàçàìè äàííîé). Ïðè ýòîì ìåòêå o ñîîòâåòñòâóåò òîæäåñòâåííàÿ ôóíêöèÿ, ò.å. â íå¼ ïåðåíîñèòñÿ çíà÷åíèå åäèíñòâåííîãî ïðîîáðàçà, à êîíúþíêöèè è äèçúþíêöèè ïðèìåíÿþòñÿ êî âñåìïðîîáðàçàì. Òàêèì îáðàçîì, ñõåìà ñ n âåðøèíàìè òèïà i è k âåðøèíàìèòèïà o âû÷èñëÿåò íåêîòîðóþ ôóíêöèþ f : {0, 1}n → {0, 1}k .
Ðàçìåðîì ñõåìû áóäåì íàçûâàòü êîëè÷åñòâî âåðøèí â íåé, à ãëóáèíîé ìàêñèìàëüíóþâûñîòó âåðøèíû.Îäíîé èç êëþ÷åâûõ òåì òåîðèè ñëîæíîñòè âû÷èñëåíèé ÿâëÿåòñÿ ïîëó÷åíèå âåðõíèõ è íèæíèõ îöåíîê íà ðàçìåð èëè ãëóáèíó ñõåì, êîòîðûå âû÷èñëÿþò òó èëè èíóþ êîíêðåòíóþ ôóíêöèþ.  ÷àñòíîñòè, áûëà äîêàçàíàòåîðåìà î íåâîçìîæíîñòè âû÷èñëåíèÿ ñõåìàìè ïîëèíîìèàëüíîãî ðàçìåðà èêîíñòàíòíîé ãëóáèíû ôóíêöèè áîëüøèíñòâà è äðóãèõ ïîðîãîâûõ ôóíêöèé.Òåîðåìà 2.31 ( [19]). Äëÿ ëþáîãî ìíîãî÷ëåíà p(·) è ëþáîé êîíñòàíòûd ñóùåñòâóåò n, äëÿ êîòîðîãî íèêàêàÿ ñõåìà ðàçìåðà p(n) è ãëóáèíû díå âû÷èñëÿåò âåðíî ôóíêöèþ maj : {0, 1}n → {0, 1}, çíà÷åíèå êîòîðîé26ñîâïàäàåò ñ áîëüøèíñòâîì àðãóìåíòîâ3 . Òî æå óòâåðæäåíèå âåðíî ïðèëþáîì (ôèêñèðîâàííîì) α ∈ (0, 1) äëÿ ôóíêöèè thrα : {0, 1}n → {0, 1},ðàâíîé 1, åñëè âåñ å¼ âõîäíîé ñòðîêè (ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
