Теоремы и идеи доказательства (2012) (1133236), страница 4
Текст из файла (страница 4)
. . , 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 èãëàâû. ïîêðûòèÿ äëÿ ìàòðèöûïàðàãðàôà ïåðâîéFäëÿ ïàðû(M, N )W1≤t≤pM ht,ii6=M ht,jiyt ÿâëÿåòñÿ îäíîâðåìåííî ÔÀËîáðàòíî. Òàê ÷òî ëåììà âåðíà ñîãëàñíî ïåðâîé ëåììå øåñòîãîÑëåäñòâèå.Êàæäàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ âèäà yt1 · · · ytr ñîêðàùåííîé ÄÍÔ ôóíêf (y1 , . . . , yp ), ïîëó÷àþùàÿñÿ èç ÊÍÔ ëåììû â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, ñîîòâåòñòâóåò òóïèêîâîìó òåñòó, ñâÿçàííîìó ñ ìíîæåñòâîì T = {t1 , . . . , tr } è îáöèèðàòíî.Ëåììà.Äëèíà ëþáîãî òóïèêîâîãî äèàãíîñòè÷åñêîãî òåñòà äëÿ îòäåëèìîé ïî ñòîëáöàìB p,sdlog se äî (s − 1).t ñòðîê ìàòðèöû M îáðàçóþò åå òóïèc - ìàòðèöà, ñîñòîÿùàÿ èç ïåðâûõ t ñòðîê ìàòðèöû M . ×èñëîêîâûé äèàãíîñòè÷åñêèé òåñò.
Mttðàçëè÷íûõ áóëåâûõ ñòîëáöîâ âûñîòû t ðàâíî 2 . Ïîñêîëüêó âñå s ñòîëáöîâ ðàçëè÷íû, s ≤ 2 ,òî åñòü t ≥ dlog se.∀q, q ∈ [1, t] îïðåäåëèì îòíîøåíèå ýêâèâàëåíòíîñòè: m0 ∼ m00 òîãäà è òîëüêî òîãäà, êîãäàìàòðèöû èç ìíîæåñòâàçàêëþ÷åíà â ïðåäåëàõ îòÝòàïû äîêàçàòåëüñòâà. ÏóñòüM ∈ B p,sè ïåðâûåqc ñîâïàäàþò â ñòðîêàõ ñ íîìåðàìè èç [1, q]. ×èñëî êëàññîâ ýêâèâàm0 , m00 ìàòðèöû Mëåíòíîñòè θ(q). Ïîñêîëüêó òåñò òóïèêîâûé, θ(q) < θ(q +1).
Ïîñêîëüêó òåñò äèàãíîñòè÷åñêèé,θ(t) = s. Ïîëó÷àåì 1 = θ(0) < θ(1) < · · · < θ(t) = s, òî åñòü t ≤ (s − 1). Ëåììà. Ïóñòü ϕ(s), t(s) è p(s) öåëî÷èñëåííûå íåîòðèöàòåëüíûå ôóíêöèè íàòóðàëüíîãîàðãóìåíòà s, äëÿ êîòîðûõ t(s) = d2 log se + ϕ(s), p(s) ≥ t(s), ϕ(s) −→ ∞. Òîãäà ó ïî÷òè âñåõñòîëáöûs→∞îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçB p(s),sïåðâûåt(s)ñòðîê îáðàçóþò äèàãíîñòè÷åñêèé òåñò.B p(s),s : 2t (2t − 1) . .
. (2t −(s−1)1s + 1) · 2= 2 (1 − 2t ) . . . (1 − 2t ). Èõ äîëÿ ñðåäè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö(s−1)1s2p,sps−2ϕ(s)èç B(2 ) íå ìåíüøå, ÷åì (1 − t ) . . . (1 −, ÷òî ñòðåìèòñÿ ê 122t ) ≥ 1 − 2t ≥ 1 − 2ïðè s ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè. Ýòàïû äîêàçàòåëüñòâà. Îöåíèì êîëè÷åñòâî çàäàííûõ ìàòðèö(p−t)sÑëåäñòâèå.psÄëÿ ëþáîé íåîòðèöàòåëüíîé è íåîãðàíè÷åííî âîçðàñòàþùåé ôóíêöèèó ïî÷òè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçòåñòà íå áîëüøå, ÷åì2 log s + ϕ(s).11B p,sϕ(s)äëèíà ìèíèìàëüíîãî äèàãíîñòè÷åñêîãîËåììà. Äëÿ ëþáûõ p ≥ 0, q ≥ 0 è ëþáîé ÊÑ Σ ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑ Σ0 , Σ0 ∈KU(p,q) , äëÿ êîòîðîé L(Σ0 ) ≤ (p + 1)(q + 1)L(Σ).Ýòàïû äîêàçàòåëüñòâà.
Ñõåìà ñòðîèòñÿ ïóòåì ïàðàëëåëüíîãî è (èëè) ïîñëåäîâàòåëüíîãîäóáëèðîâàíèÿ êîíòàêòîâ.Ëåììà.Äëÿëþáîéñàìîêîððåêòèðóþùèåñÿ ÊÑÊÑΣ0èΣΣ00ñóùåñòâóþòýêâèâàëåíòíûåñîîòâåòñòâåííî òàêèå, ÷òîåé(1,0)-è(0,1)-L(Σ0 ) ≤ L(Σ) + ζ(Σ), L(Σ00 ) ≤L(Σ) + ζ(Σ).LK(n)∼(1,0)Ýòàïû äîêàçàòåëüñòâà. Ñòðîèòñÿ çàìåíîé îäíîðîäíûõ ìåòåëîê íà öèêëû (çâåçäû).Òåîðåìà Äëÿ n = 1, 2, . . .LK(0,1) (n) ∼èìåþò ìåñòî ñëåäóþùèå àñèìïòîòè÷åñêèå ðàâåíñòâà:2nnÝòàïû äîêàçàòåëüñòâà. Íèæíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû âòîðîãî ïàðàãðàôàòðåòüåé ãëàâû.
Âåðõíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû øåñòîãî ïàðàãðàôà òðåòüåé ãëàâûè çàìå÷àíèÿ ê íåé.nζ(Σf ) = o( n2√n ).Òàê ÷òî ñóùåñòâóþò ÊÑ, êîòîðûå ðåàëèçóþò ÔÀË2nñëîæíîñòüþ, àñèìïòîòè÷åñêè íå ïðåâîñõîäÿùåén . Ëåììà. Äëÿ n = 1, 2, . . . èìåþò ìåñòî ðàâåíñòâà LK(0,1) (ln )ñî¯= LK(0,1) (ln ) = 4n.σ, σ ∈ B , èç âõîäà (âûõîäà) ýòîé ñõåìû, ïðîâåäåìxσn (xσ1 ) â âåðøèíó, ñîåäèíåííóþ êîíòàêòîì âèäà xσ̄n (xσ̄q ) ñ åå âûõîäîì (âõîäîì).Ýòàïû äîêàçàòåëüñòâà. Äëÿ êàæäîãîêîíòàêò âèäàf12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
