Теоремы и идеи доказательства (2012) (1133236), страница 3
Текст из файла (страница 3)
Ïîëó÷èìnL(Un ) = 22.n2~Ñëåäñòâèå. LC− n.Á (P2 (n)) ≤ 2nn âûïîëíÿþòñÿ íåðàâåíñòâà: LC (Q~n ) ≤ 2n + O(n · 2 2 ),nLK (Q~n ) ≤ 2n+1 − 2, LC (J~n ) ≤ 2n + O(n · 2 2 ), LK (J~n ) ≤ 2n+2 − 4, Lπ (µn ) ≤ 3 · 2n − 2, LΦ (µn ) ≤n+2CC2− 3, L (ln ) ≤ 4n − 4, L (ln ) ≤ 4n − 4 + b n1 c.0Ýòàïû äîêàçàòåëüñòâà. Ðàçîáüåì ÁÏ X(n) íà äâå ãðóïïû x= (x1 , . . . , xq ), x00 =n000000(xq+1 , . .
. , xn ), q = d 2 e. Äåøèôðàòîðû Σ , Σ îò x , x ñîîòâåòñòâåííî, ðåàëèçóþùèå ñâîèËåììà.Äëÿ ëþáîãî íàòóðàëüíîãîñèñòåìû ÝÊ ïî ïåðâîé ëåììå. Îáúåäèíèì ñõåìû, êîíúþíêòèðóÿ êàæäóþ ïàðó âûõîäîâ. Äëÿ2nÔÝ &, èõ âûõîäû ñ÷èòàåì âûõîäîì Σ. Ïîëó÷èì äâà äåøèôðàòîðà ñëîæn · 2 è 2 ÔÝ &. Îòêóäà è âûõîäÿò íåðàâåíñòâà äëÿ LC (Q~n ) è LC (J~n ).K ~nn+1Äëÿ L (Q− 2. Ñëîæíîñòü èíâåðñíîé ñõåìûn ) ïîñòðîèì (1, 2 )-ÊÄ. Åãî ñëîæíîñòü 2~(ñõåìû äëÿ Jn ) íå ïðåâîñõîäèò åå áîëåå, ÷åì â äâà ðàçà.πnÄëÿ L (µn ) ïîñòðîèì (1, 2 )-ÊÄ. Åãî âûõîäû ñîåäèíèì ñ âûõîäîì ìóëüòèïëåêñîðà êîíòàênòàìè ñ ïîìåòêàìè y0 , .
. . , y2n −1 . Ñëîæíîñòü ïîëó÷èâøåéñÿ ñõåìû áóäåò 3·2 −2. Ïðîìîäåëèðóÿnπ -ñõåìó, ïîëó÷èì ôîðìóëó ñëîæíîñòè 4 · 2 − 3 (íàäî ïðîñòî àêêóðàòíî ðàñïèñàòü ìîäåëèðîýòîãî ïîíàäîáèòñÿn2íîñòüþnâàíèå ÊÄ).⊕x1 ⊕ x2 Σ ⊕2 èìååò ñëîæíîñòü 4. Σn ÿâëÿåòñÿ êîìïîçèöèåé n − 1⊕ñõåìû Σ2 . Ñõåìà äëÿ ln ïîëó÷àåòñÿ èç ñõåìû äëÿ ln çàìåíîé âñåõ ÔÝ & íà ∨ è âñåõ ÔÝ ∨ íà&. Ëåììà. Åñëè ÔÀË f (x1 , . . . , xn ) ñóùåñòâåííî çàâèñèò îò âñåõ ñâîèõ ÁÏ, òî LC (f ) ≥ n − 1,KL (f ) ≥ n.
Åñëè ïðè ýòîì ÔÀË f íå ÿâëÿåòñÿ ìîíîòîííîé ÔÀË (êàæäàÿ ÁÏ xi , i ∈ [1, k],Cíå ÿâëÿåòñÿ íè ìîíîòîííîé, íè èíìîíîòîííîé ÁÏ ÔÀË f ), òî L (f ) ≥ n (cîîòâåòñòâåííî,KL (f ) ≥ n + k ).Ñõåìà, ðåàëèçóþùàÿf ñóùåñòâåííî çàâèñèò îò âñåõ ÁÏ, òî ðàíã ìèíèìàëüLC (f ) ≥ L∨,& (Σf ) ≥ n − 1. Åñëè ÔÀË f íå ìîíîòîííà, òîCÔÝ ¬, ïîýòîìó L (f ) ≥ n.Ýòàïû äîêàçàòåëüñòâà. Åñëè ÔÀËíîé ÑÔÝΣfíå ìåíüøån.Òîãäàäîëæåí áûòü åùå õîòÿ áû îäèí7Σf äîëæíû áûòüx̄i , i ∈ [1, n]. Åñëè ïðè ýòîì k ÁÏ íå ÿâëÿþòñÿ íè ìîíîòîííûìè,íè èíìîíîòîííûìè ÁÏ ÔÀË f , òî â Σf äîëæíî áûòü k çàìûêàþùèõ è k ðàçìûêàþùèõKêîíòàêòîâ.
Òàêèì îáðàçîì, L (f ) ≥ n + k . CÑëåäñòâèå. L (ln ) ≥ n, LK (ln ) ≥ 2n, LC (µn ) ≥ 2n + n, LK (µn ) ≥ 2n + 2n.Ëåììà. Äëÿ ñèñòåìû F = (f1 , . . . , fm ), ñîñòîÿùåé èç ïîïàðíî ðàçëè÷íûõ ÔÀË îòëè÷íûõKCîò êîíñòàíò (îò ïåðåìåííûõ), ñïðàâåäëèâî íåðàâåíñòâî L (F ) ≥ m (ñîîòâåòñòâåííî, LÁ (F ) ≥m).Ýòàïû äîêàçàòåëüñòâà. ΣF ïðèâåäåííàÿ (1, m)-ÊÑ, ðåàëèçóþùàÿ F . ΣF ñâÿçíûé ãðàôñ íå ìåíåå, ÷åì m + 1 âåðøèíîé.
Ñëåäîâàòåëüíî, L(ΣF ) ≥ |V (ΣF )| − 1 ≥ m. Âòîðîå íåðàâåíñòâî âûòåêàåò èç òîãî, ÷òî fi , i ∈ [1, m] ðåàëèçóþòñÿ íà ïîïàðíî ðàçëè÷íûõ âûõîäàõ ÑÔÝ,îòëè÷íûõ îò åå âõîäîâ. ~n ) ≥ 2n , LK (Q~n ) ≥ 2n , LC (J~n ) ≥ 2n , LK (J~n ) ≥ 2n , LC (P~2 (n)) ≥ 22n − n,Ñëåäñòâèå. LC (QÁnLK (P~2 (n)) ≥ 22 − 2.Çàìå÷àíèå  ñèëó ñëåäñòâèÿ óíèâåðñàëüíàÿ ÑÔÝ Un , ïîñòðîåííàÿ â ëåììå 1.3, ÿâëÿåòñÿCìèíèìàëüíîé ïî ñëîæíîñòè ÑÔÝ â êëàññå UÁËåììà.
Äëÿ ïîëîæèòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë a, y , q èç íåðàâåíñòâ a log q > 1,log log(a log q)log q(ay)y ≥ q , ñëåäóåò íåðàâåíñòâî y ≥ log(alog q) (1 + log(ae log q) ), ãäå e îñíîâàíèå íàòóðàëüíîãîÏîñêîëüêó ÔÀËfêîíòàêòû ñ ïîìåòêàìèñóùåñòâåííî çàâèñèò îò âñåõ ÁÏ, â ìèíèìàëüíîé ÊÑxièëèlog qlog a .Ýòàïû äîêàçàòåëüñòâà. Âòîðîå íåðàâåíñòâî âûòåêàåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿëîãàðèôìà, à èç íåðàâåíñòâa > 1, ay ≥ q íåðàâåíñòâîy≥a = 1, log q > 1. Âîçüìåìy 0 log y 0 ≤ log q , è ïîëó÷èì,y÷òî äîêàçûàåìîå íåðàâåíñòâî âåðíî, èñïîëüçóÿ óñëîâèå (ay)≥ q .
Ïðè a > 0, (ay)y ≥ qayaýêâèâàëåíòíî (ay)≥ q . È äîêàçûâàåìîå íåðàâåñòâî ïîëó÷àåòñÿ èç y ≥ y 0 çàìåíîé y íà ayè log q íà a log q . Òåîðåìà. Äëÿ íåêîòîðîé ïîñëåäîâàòåëüíîñòè ε = ε(n), n = 1, 2, . . . , òàêîé, ÷òî ε(n) ≥ 0ïðè n ≥ n0 è ε(n) ñòðåìèòñÿ ê 0 ïðè n ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè, äëÿ ïî÷òè âñåõ ÔÀËn2nKf, f ∈ P2 (n), âûïîëíÿþòñÿ íåðàâåíñòâà LC (f ) ≥ (1 + ε(n)) 2n , LΦ (f ) ≥ (1 − ε(n)) logn , L (f ) ≥nn2(1 − ε(n)) 2n , Lπ (f ) ≥ (1 − ε(n)) logn , D(f ) ≥ n − log log n − ε(n).CL+1Ýòàïû äîêàçàòåëüñòâà.
Âîñïîëüçóåìñÿ íåðàâåíñòâàìè ||U (L, n)|| ≤ (8(L + n)),ΦL+1KL||U (L, n)|| ≤ (8n), ||U (L, n)|| ≤ (8nL) . À òàêæå çàìå÷àíèåì î òîì, ÷òî åñëè äëÿ íåêîòîb 0 < δ < 1 âûïîëíÿåòñÿ ||U(Ψ,b n)|| ≤ δ · 22n , òî Ψ(f ) ≥ Ψb äëÿ íå ìåíåå ÷åì (1 − δ) · 22nðûõ n, Ψ,ÔÀË f èç P2 (n). Èñêîìûå íåðàâåíñòâà ïîëó÷èì, ïîäñòàâëÿÿ îñîáûì îáðàçîì ïîäîáðàííûåδ, a, y è q â ïðåäûäóùóþ ëåììó è óêàçàííîå óòâåðæäåíèå. n2n2n2nKπÑëåäñòâèå. LC (n) & 2n , LΦ (n) & logn , L (n) & n , L (n) & log n .K σËåììà.Äëÿ ëþáîãî íàòóðàëüíîãî n è σ ∈ B âûïîëíÿþòñÿ íåðàâåíñòâà: L (ln ) ≤ 4n −j kn4 + 1 , LK (P~2 (n)) ≤ 2 · 22 .ëîãàðèôìà. Äîêàæåì ïåðâîå íåðàâåíñòâî. Ðàññìîòðèì ñëó÷àé, êîãäày0ðàâíûì ïðàâîé ÷àñòè íåðàâåíñòâà.
Òîãäà ìîæíî ïîêàçàòü, ÷òînÝòàïû äîêàçàòåëüñòâà. Îöåíêà äëÿ ëèíåéíîé ôóíêöèè íàïðÿìóþ ñëåäóåò èç ïîñòðîåíèÿñõåìû Êàðäî. Ïðè ýòîìîáðàòèìñÿ ê Ìèõàèëó.Òåîðåìà.nLC (n) . 8 2nj k1nn = 1.íóæíî äëÿ ñëó÷àÿ, êîãäàÄëÿ ïîëó÷åíèÿ âòîðîé îöåíêèÄëÿ ôóíêöèé ØåííîíàLK (n)LC (n)èâûïîëíåíû ñîîòíîøåíèÿ:nLK (n) . 4 2n,.Ýòàïû äîêàçàòåëüñòâà. Ïðèìåíèì ìåòîä Øåííîíà ñèíòåçà ÔÀË ïóòåì ðàçëîæåíèÿôóíêöèè ïî(n − q) ïîñëåäíèì ïåðåìåííûì. ÊÑ (ÑÔÝ) äëÿ ÔÀË f ïðåäñòàâëÿåò ñîáîé ñóïåðq è ìóëüòèïëåêñîðà ïîðÿäêà (n − q). Âçÿâïîçèöèþ óíèâåðñàëüíîãî ìíîãîïîëþñíèêà ïîðÿäêàïàðàìåòðqíóæíûì îáðàçîì, à òàêæå âîñïîëüçîâàâøèñü ðåçóëüòàòîì ïðåäûäóùèõ îöåíîêñëîæíîñòè ýòèõ ñõåì ïîëó÷èì òðåáóåìûå îöåíêè.Ëåììà.Gïîðÿäêà1.Äëÿ ëþáûõ íàòóðàëüíûõmè âûñîòûs,p, mès,ãäåp=êîòîðîå ÿâëÿåòñÿ ÄÓÌ ðàíãàlpm2ms , ñóùåñòâóåò ñòàíäàðòíîå ÄÓÌè äëÿ êîòîðîãî:λ = |G| ≤ p2s2.
ñèñòåìà èçpîðòîãîíàëüíûõ õàðàêòåðèñòè÷åñêèõñòâîì, ÷òî äëÿ ëþáîé ÔÀËg, g ∈ P2 (m),ψ1 , . . . , ψ pè íåêîòîðûõ ÔÀË8G îáëàäàåò òåì ñâîég1 , . . . , gp èç G ñïðàâåäëèâîÄÓÌíå òîëüêî ïðåäñòàâëåíèåg = g1 ∨ . . . ∨ gp ,íî èg = ψ1 g1 ∨ . . . ∨ ψp gp .Ýòàïû äîêàçàòåëüñòâà. Ïî ïîñòðîåíèþ ñòàíäàðòíîãî ÄÓÌ.Òåîðåìà. Ìåòîä Ëóïàíîâà.ñóùåñòâóåò ðåàëèçóþùàÿ ååÑÔÝΣf , Σf ∈ U C ,òàêàÿ, ÷òîf, f ∈ P2 (n),n).L(Σf ) ≤ 2n (1 + 5 log n+O(1)nÄëÿ ëþáîé ÔÀËf ïî (n − q) ïîñëåäíèìf , â âèäå Σf = Σ00 (Σ0 ), ãäå Σ00 ìóëüòèïëåêñîð00ïîðÿäêà (n − q), à Σ ðåàëèçóåò ñèñòåìó ôóíêöèé, êîòîðàÿ ðåàëèçóåò âñå ÔÀË âèäà fσ 00 (x ),000n−q0000ãäå x = (x1 , . . . , xq ), σ ∈ B, è fσ 00 (x ) = f (x , σ ).
Êàæäàÿ òàêàÿ ÔÀË áóäåò ðåàëèçîâàíà,Ýòàïû äîêàçàòåëüñòâà. Êàê è â ìåòîäå Øåííîíà, ðàçëîæèì ÔÀËïåðåìåííûì. Íàéäåì ÑÔÝ, ðåàëèçóþùóþ ÔÀËêàê äèçúþíêöèÿ õàðàêòåðèñòè÷åñêèõ ÔÀË ñòàíäàðòíîãî ÄÓÌ G.Ïîñòðîèì ñòàíäàðòíîå ÄÓÌ G ïîðÿäêàçóåò ñèñòåìó ÔÀË~Gëåå2è âûñîòûs ≤ 2q . ΣG ÑÔÝ, êîòîðàÿ ðåàëè-è ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå ñõåì, ïîñòðîåííûå ìîäåëèðîâàíèåìôóíêöèé èõ ñîâåðøåííûìè ÄÍÔ.
ÂqqGíå áîëååp · 2sôóíêöèé, â êàæäîé èç êîòîðûõ íå áî-åäèíèö. Òîãäà, ïî ëåììå î ñëîæíîñòè ÔÑÝ, ðåàëèçóþùåé ñîâåðøåííóþ ÄÍÔ ôóíêöèè,L(ΣG ) ≤ 3p2s+q . Ñëîæíîñòü ìóëüòèïëåêñîðà óæå ðàññìàòðèâàëàñü. L(Σ00 ) ≤ 4 · 2n−q .0n−qÄëÿ ðåàëèçàöèè êàæäîé ÔÀË fσ 00 (x ) íóæíî (p − 1) ÔÝ ∨. Âñåãî òàêèõ ÔÀË 2. Òàêèì00n−qn−qn−qîáðàçîì ïîëó÷èì ñõåìó Σ : L(Σ ) = 2(p − 1) + L(ΣG ). L(Σf ) ≤ 2(p − 1) + 4 · 2+ 3p2s+q .Âçÿâ ïàðàìåòðû s, m, q íóæíûì îáðàçîì, ïîëó÷èì òðåáóåìóþ îöåíêó.
nÑëåäñòâèå. LC (n) ∼ 2n .Ëåììà. Äëÿ ëþáûõ íàòóðàëüíûõ m, λ è q = m + λ è äëÿ ëþáîé ñèñòåìû ÔÀË g =(g1 , . . . , gλ ) èç P2λ (m) ñóùåñòâóåò m-ðåãóëÿðíîå ðàçáèåíèå ∆ = (δ1 , . . . , δ2q−m ) êóáà B q òàêîå,÷òî ëþáàÿ ÔÀË gi íà ëþáîé êîìïîíåíòå δj ñîâïàäàåò ëèáî ñ îäíîé èç ÁÏ xm+1 , . . . , xq , ëèáîïîëó÷èì:ñ åå îòðèöàíèåì.gi íà ëþáîé êîìxm+1 , . . . , xq , ëèáî ñ åå îòðèöàíèåì. Ýòî çíà÷èò,÷òî ñòîëáåö çíà÷åíèé ëþáîé ÔÀË gi íà ïåðâûõ m ïåðåìåííûõ íàáîðîâ èç δj ñîâïàäàåò ñîñòîëáöîì çíà÷åíèé îäíîé èç ÁÏ xm+1 , . . .
, xq , ëèáî ñ åãî îòðèöàíèåì. êà÷åñòâå δ1 ìû áåðåì m-ðåãóëÿðíîå ìíîæåñòâî, îòâå÷àþùåå ñèñòåìå ÔÀË g =(g1 , . . . , gλ ). ×òîáû ïîëó÷èòü δ2 , . . . , δ2q−m , ìû âñåìè âîçìîæíûìè ñïîñîáàìè íàêëàäûâàåìqîòðèöàíèå íà (q − m) ïîñëåäíèõ ñòîëáöîâ. Ëþáîé íàáîð èç B åñòü â δ ñ òî÷íîñòüþ äî (q − m)ïîñëåäíèõ ñòîëáöîâ. Ïîñêîëüêó ìû ïåðåáèðàëè âñå âîçìîæíûå îòðèöàíèÿ (q − m) ïîñëåäíèõqñòîëáöîâ, â îäíîì èç δi íàéäåòñÿ èñêîìûé íàáîð. Èç ýòîãî è èç òîãî, ÷òî |∆| = 2 ïîëó÷àåì,q÷òî ∆ ðàçáèåíèå B . Òåîðåìà.
Äëÿ ëþáîé ÔÀË f, f ∈ P2 (n), â U Φ ñóùåñòâóåò ðåàëèçóþùàÿ åå ôîðìóëà Ff ,2 log log n+O(1)2näëÿ êîòîðîé L(Ff ) ≤).log n (1 +log nmÝòàïû äîêàçàòåëüñòâà. Ïîñòðîèì ñòàíäàðòíîå ÄÓÌ G ïîðÿäêà m è âûñîòû s ≤ 2 ,~ ïî ïðåäûäó|G| = λ, q = m + λ, ∆ = (δ1 , . . . , δ2λ ) ðàçáèåíèå B q , ïîëó÷åííîå äëÿ GÝòàïû äîêàçàòåëüñòâà. Ïîÿñíþ, ÷òî èìååòñÿ â âèäó ïîä ëþáàÿ ÔÀËïîíåíòåδjñîâïàäàåò ëèáî ñ îäíîé èç ÁÏλùåé ëåììå. Ïîñòðîèì äëÿfôîðìóëó, èìåþùóþ âèä2WFef =Ui (x0 )Fbn−q (x00 , Je0,i , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
