Теоремы и идеи доказательства (2012) (1133349), страница 4
Текст из файла (страница 4)
. . , 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 , . . . , Je1,i ).i=1Fbn−q (x00 , y0 , . . . , y2n−q −1 )(n − q), Ui , i ∈ [1, 2λ ] ñîâåðøåííàÿ ÄÍÔõàðàêòåðèñòè÷åñêîé ÔÀË δi , Jσ 00 ,i ìîäåëèðóåò ÔÀË f íà êîìïîíåíòå δi . Ïîñëå îïòèìèçàef ïî ÷èñëó îòðèöàíèé, ïîëó÷èì L&,∨ (Ff ) ≤ 2q−m (q · 2m + (p − 1)2n−q + 3 · 2n−q ),öèè FL¬ (Ff ) ≤ q · 2q + 2 · 2n−m . Âçÿâ m è s ïðàâèëüíûì îáðàçîì, ïîëó÷èì íåîáõîäèìóþ îöåíêó. e f , êîòîðàÿ ìîÇàìå÷àíèå. Óñòàíîâëåííàÿ îöåíêà ñïðàâåäëèâà è äëÿ ñëîæíîñòè π -ñõåìû Σef ñ ïîäíÿòûìè îòðèöàíèÿìèäåëèðóåò ïîñòðîåííóþ â õîäå ïîëó÷åíèÿ ôîðìóëû Ff ôîðìóëó Fè ðåàëèçóåò ÔÀË f .ef ) ≤ Alt(Fbn−q ) + 3.Çàìå÷àíèå. Alt(F2n2nπÑëåäñòâèå.
LΦ (n) ∼ logn , L (n) ∼ log n .Òåîðåìà. Äëÿ n = 1, 2, . . . âûïîëíÿåòñÿ íåðàâåíñòâî D(n) ≤ n − log log n + O(1). ìóëüòèïëåêñîð ïîðÿäêàÝòàïû äîêàçàòåëüñòâà. Âìåñòî ìóëüòèïëåêñîðà èç ïðåäûäóùåãî äîêàçàòåëüñòâà ñëåäóåòâçÿòü ÊÄ ïîðÿäêà(n − q).Îòêóäà è ïîëó÷èì òðåáóåìóþ îöåíêó.Ñëåäñòâèå. D(n) = n − log log n ± O(1).Òåîðåìà. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä.ñòâóåò ðåàëèçóþùàÿ åå ÊÑΣfòàêàÿ, ÷òîL(Σf ) ≤92nn (1Äëÿ ëþáîé ÔÀË+ O( √1n )).f, f ∈ P2 (n),ñóùå-m è âûñîòû s ≤ 2m ,|G| = p, q = m + p.
ψ1 , . . . , ψp õàðàêòåðèñòè÷åñêèå ôóíêöèè G. ∆ = (δ1 , . . . , δ2p ) ðàçáèåíèå~ . Ïî ñâîéñòâàì äàííîãî ðàçáèåíèÿ, ëþáàÿ ÔÀË g, g ∈ P2 (q) íà ëþáîéB q , ïîëó÷åííîå äëÿ Gêîìïîíåíòå ðàçáèåíèÿ âèäà δ1 ⊕ α, ãäå α = (0, . . . , 0, αm+1 , . . . , αm+p ) ñîâïàäàåò ñ ÔÀË ǧ =ᾱᾱm+1· g1 ∨ . . . ∨ xq q · gp , ãäå gi = gψi .xm+1~ íà îñíîâå ÊÄ.
ÏîñòðîèìÏóñòü q = m + p, ΣG (1, λ)-ÊÑ, ðåàëèçóþùàÿ ñèñòåìó ÔÀË G2p (1, 2n−q )-ÊÑ, êîòîðûå ñîäåðæàò ÊÑ ΣG â êà÷åñòâå ïîäñõåìû è ðåàëèçóþò êàæäóþ ÔÀËǧσ00 . Σ0 ïîëó÷àåòñÿ â ðåçóëüòàòå îòîæäåñòâëåíèÿ âõîäîâ âñåõ ïîñòðîåííûõ ÊÑ.σq+1Σ00 ñòðîèì, êàê ÊÑ, ðåàëèçóþùóþ ñòîëáåö èç âñåõ ÔÀË âèäà χi (x0 ) · xq+1. . . xσnn .
Ñòðîèìpn−qpîáúåäèíåíèåì 2 ÊÄ ïîðÿäêà (2, 1) è (2 , 1) ÊÄ, ðåàëèçóþùèì χi îòîæäåñòâëåíèåì âûõî000n−mäîâ. Σf = Σ (Σ ). L(Σf ) ≤ (p + 2)2+ (λ + 1)2q+1 . Âçÿâ ïàðàìåòðû m è s íóæíûì îáðàçîì,ïîëó÷èì íåîáõîäèìóþ îöåíêó. nÑëåäñòâèå. LK (n) ∼ 2n .pn−m+1Çàìå÷àíèå. Ïîñòðîåííóþ ÊÑ Σf ìîæíî ðàçáèòü íà íå áîëåå, ÷åì λp · 2 + 2+ (λ +n2√q+11)2= O( n n ) çâåçä, êàæäàÿ èç êîòîðûõ ñîñòîèò èç êîíòàêòîâ îäíîãî è òîãî æå òèïà.Ýòàïû äîêàçàòåëüñòâà. Ïîñòðîèì ñòàíäàðòíîå ÄÓÌËåììà.Äëÿ êëàññà ÔàëQòàêîãî, ÷òîL (Q(n)) &ïîðÿäêàn = o( logloglog|Q(n)||Q(n)| )(log n = o(log log |Q(n)|)),ïîëíÿþòñÿ ñëåäóþùèå àñèìïòîòè÷åñêèå íåðàâåíñòâàKGCL (Q(n)) &âû-log |Q(n)|log log |Q(n)| , (ñîîòâåòñòâåííîlog |Q(n)|log log |Q(n)| ).Ýòàïû äîêàçàòåëüñòâà.
Äîêàçûâàåòñÿ àíàëîãè÷íî ïîñëåäíåé òåîðåìå âòîðîãî ïàðàãðàôà.Ëåììà.(1, m)-ÊÑ Σ ðåàëèçóåò m ðàçëè÷íûõ ÔÀË,L(Σ) ≥ 2m − 2.nÝòàïû äîêàçàòåëüñòâà. Σ ñâÿçíàÿ ÊÑ. Èç åå ðàçäåëèòåëüíîñòè ñëåäóåò, ÷òî ∀α, α ∈ Bñåòü Σ|α ñîñòîèò íå ìåíåå ÷åì èç m êîìïîíåíò ñâÿçíîñòè. Çíà÷èò, áûëî óäàëåíî íå ìåíåå, ÷åìm−1 êîíòàêòîâ. Òàêèì îáðàçîì ïîëó÷èì, ÷òî |E(Σ|ᾱ)| ≥ m−1. Ñóììèðóÿ ýòî íåðàâåíñòâî ïînâñåì íàáîðàì êóáà B è ó÷èòûâàÿ, ÷òî êàæäûé êîíòàêò ÊÑ Σ íå ïðîâîäèò ðîâíî íà ïîëîâèíåÅñëè ðàçäåëèòåëüíàÿ ïî âûõîäàìîòëè÷íûõ îò 0, òîâñåõ íàáîðîâ (êàæäûé êîíòàêò áûë ïîñ÷èòàí ñòîëüêî ðàç, ñêîëüêî íàáîðîâ îí ïðîâîäèò, òîåñòü2n−1ðàç) ïîëó÷èì2n−1 L(Σ) ≥ 2n (m − 1).Îòêóäà è ñëåäóåò äîêàçûâàåìîå íåðàâåíñòâî.Ñëåäñòâèå.n ÿâëÿåòñÿ ìèíèìàëüíîé ðàçäåëèòåëüíîé (1, 2n )Qn .Ëåììà.
Åñëè ñèñòåìà ÔÀË F = (f1 , . . . , fm ) ñîñòîèò èç ïîïàðíî ðàçëè÷íûõ ÔÀË îò ÁÏmPX(n), îòëè÷íûõ îò 0 è 1, òî LK (F ) ≥ 21−n|Nfj |.Êîíòàêòíîå äåðåâî ïîðÿäêàÊÑ, ðåàëèçóþùåé ñèñòåìó ÔÀËj=1Ýòàïû äîêàçàòåëüñòâà.∀α, α ∈ B nâ ñåòèΣ|αèìååòñÿ êîìïîíåíòà ñâÿçíîñòè, âêëþ-÷àþùàÿ âõîä è ñòîëüêî âûõîäîâ, ñêîëüêî ôóíêöèé îáðàùàþòñÿ â åäèíèöó íà|E(Σ|α)| ≥ f1 (α) + · · · + fm (α).mPn−12L(Σ) ≥|Nfj |.ïîëó÷èìα.ÎòñþäàÑóììèðóÿ íåðàâåíñòâî âî âñåì íàáîðàì ïîëó÷èìj=1Ñëåäñòâèå.
LK (Jn ) ≥ 2n+1 − 2.Ëåììà. Äëÿ n = 1, 2, . . . âûïîëíÿþòñÿíåðàâåíñòâàn2n+1 + O( 2n ).nLK (Q~n ) ≤ 2n + O( 2n ), LK (J~n ) ≤λ = 2m , q = m + λ, q ≤ n. ∆ = (δ1 , . . . , δ2λ )~ m ñèñòåìå ÔÀË èç ÝÊ ðàíãà m. m-ðåãóëÿðíîå ðàçáèåíèå êóáà B , îòâå÷àþùåå ñèñòåìå Qσqσ100Ëþáàÿ ÝÊ ðàíãà q K(x ) = x1 .
. . xq , σ = (σ1 , . . . , σq ) ∈ δi ñîâïàäàåò íà ìíîæåñòâå δi ñ~ m . Èíà÷å ãîâîðÿ, ñîâïàäàåò ñ ÁÏ xασ0 , m+1 ≤ jσ0 ≤ q , ασ0 ∈ B . Ëþáàÿîäíîé èç ÝÊ ñèñòåìû Qjσ 0ασ 0σ1σ000ÝÊ K = x1 . . . xnn ìîæåò áûòü ïðåäñòàâëåíà â âèäå K = χi (x ) · xj 0 · Kσ 00 (x ).σλ0(1, 2 )-ÊÑ Σ ðåàëèçóåò ñèñòåìó ÔÀË χ~ îáúåäèíåíèåì ÊÑ äëÿ χi , ïîñòðîåííûõ íà îñíîâå(&)00èõ ñîâåðøåííûõ ÄÍÔ. Kσ 00 (x ) ðåàëèçóþòñÿ ÊÄ. Ïîëó÷àåòñÿ ñõåìà Σn .(&) λ ñõåìå Σn2 ïîäñõåì ñëîæíîñòüþ q2m (ñëîæíîñòü Σ0i ) + 2n−q+1 − 2 (ñëîæíîñòü ÊÄn−qïîðÿäêà n − q ) + 2· λ (ê êàæäîìó èç âûõîäîâ ÊÄ ïðèñîåäèíåíî λ êîíòàêòîâ).
Ïîëó÷àåì(&)λmn−q+1L(Σn ) = 2 (q2 +2−2+λ2n−q ). Âñïîìíèì, ÷òî λ = q −m, ðàñêðîåì ñêîáêè è ïîëó÷èì:(&)n−mn−m+1L(Σn ) = λ2+2+ q2q . Îòêóäà è ïîëó÷èì òðåáóåìóþ îöåíêó. Ýòàïû äîêàçàòåëüñòâà. Âûáåðåì ïàðàìåòðû:q10~n ) ∼ 2n , LK (J~n ) ∼ 2n+1 .Ñëåäñòâèå. LK (QnËåììà. Äëÿ n = 1, 2, . . . âûïîëíÿþòñÿ íåðàâåíñòâà Lπ (µn ) ≤ 2 · 2n + O( 2n ), LC (µn ) ≤n2 · 2n + O( 2n ), D(µn ) ≤ n + 6, ïðè÷åì ñóùåñòâóåò òàêàÿ ðåàëèçàöèÿ ÔÀË µn è áåñïîâòîðíàÿ ïîèíôîðìàöèîííûì ÁÏ ôîðìóëà Fn ñ ïîäíÿòûìè îòðèöàíèÿìè, ãëóáèíà êîòîðîé óäîâëåòâîðÿåònïîñëåäíåìó èç íèõ, àëüòåðíèðîâàíèå íå áîëüøå 3, à ñëîæíîñòü íå ïðåâîñõîäèò 7 · 2 .Ýòàïû äîêàçàòåëüñòâà.
Èñêîìàÿ π -ñõåìà Σn ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèñîåäèíåíèÿ ê(&)êàæäîìó èç âûõîäîâ Σnñîîòâåòñòâóþùåé åìó èíôîðìàöèîííîé ÁÏ è îòîæäåñòâëåíèÿ êîíöåâûõ âåðøèí âñåõ òàêèõ êîíòàêòîâ â âûõîäíóþ âåðøèíó Σn . ÑÔÝ Sn ïîëó÷àåòñÿ èç ôîðìóëû, ìîäåëèðóþùåé Σn â ðåçóëüòàòå ïðèâåäåíèÿ âåðøèí, ñîîòâåòñòâóþùèõ ÔÝ ¬.Ôîðìóëó F̃n ïîñòðîèì ìîäåëèðîâàíèåì ÊÑ Σn . Ôîðìóëó Fn ïîëó÷èì èç íåå îïòèìèçàöèåéïî ãëóáèíå. Ïîëó÷èì ôîðìóëó, îáëàäàþùóþ âñåìè íåîáõîäèìûìè ñâîéñòâàìè. Ëåììà.
Åñëè äëÿ ÔÀË f, f ∈ P2 (n), è äëÿ ëþáîãî σ, σ ∈ B , ÔÀË fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1,CCCòî L&,∨ ≥ min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.CÝòàïû äîêàçàòåëüñòâà. Ïóñòü Σ ìèíèìàëüíàÿ ïî ÷èñëó ÔÝ & è ∨ ÑÔÝ èç êëàññà U ,êîòîðàÿ ðåàëèçóåò ÔÀË f è êîòîðàÿ íå ñîäåðæèò öåïî÷åê èç äâóõ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ÔÝ ¬. Ïóñòü êîíñòàíòà σ, σ ∈ B ðàâíà 0 òîãäà è òîëüêî òîãäà, êîãäà ÁÏ xn ïîäàåòñÿ â Σëèáî íà âõîä ÔÝ &, ëèáî íà âõîä ÔÝ ¬, âûõîä êîòîðîãî ïîñòóïàåò íà âõîä ÔÝ ∨. Òîãäà ïðèïîäñòàíîâêå σ âìåñòî xn è ÝÏ íà îñíîâå òîæäåñòâ ïîäñòàíîâêè êîíñòàíò áóäóò óäàëåíû ïîêðàéíåé ìåðå äâà ÔÝ òèïà & èëè ∨.
Ñëåäñòâèå. LC (µn ) ≥ 2n+1 + n − 2.Ñëåäñòâèå. LC (µn ) ∼ 2n+1 .Ñëåäñòâèå. n + 1 ≤ D(µn ) ≤ n + 6.p,sËåììà. Ôóíêöèÿ òåñòà f (y1 , . . . , yp ) äëÿ îòäåëèìîé ïî ñòîëáöàì ìàòðèöûè M , M ∈ B ,öåëè êîíòðîëÿNVf (y1 , . . . , yp ) =ìîæåò áûòü çàäàíà ñ ïîìîùüþ ÊÍÔ(i,j)∈NÝòàïû äîêàçàòåëüñòâà. ÔÀË òåñòàM èãëàâû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
