В.Б. Алексеев - Введение в теорию сложности алгоритмов (1158872), страница 6
Текст из файла (страница 6)
, xn ) ∈ L è f (1, x2 , . . . , xn ) ≡ f (0, x2 , . . . , xn ) ⊕ c1 .Äëÿ äîêàçàòåëüñòâà îáðàòíîãî ïåðåõîäà çàìåòèì, ÷òî äëÿ ëþáîé áóëåâîéôóíêöèè ñïðàâåäëèâî ïðåäñòàâëåíèåÄîêàçàòåëüñòâî.f (x1 , . . . , xn ) = x̄1 · f (0, x2 , . . . , xn ) ⊕ x1 · f (1, x2 , . . . , xn ) == (x1 ⊕ 1) · f (0, x2 , . . . , xn ) ⊕ x1 · f (1, x2 , .
. . , xn ) == x1 · (f (0, x2 , . . . , xn ) ⊕ f (1, x2 , . . . , xn )) ⊕ f (0, x2 , . . . , xn ).Ïîýòîìó, åñëè f (1, x2 , . . . , xn )≡ f (0, x2 , . . . , xn ) ⊕ d, òî åñòüf (0, x2 , . . . , xn ) ⊕ f (1, x2 , . . . , xn ) ≡ d, è f (0, x2 , . . . , xn ) ∈ L, òî èf (x1 , x2 , . . . , xn ) ∈ L.Ëåììà äîêàçàíà.Áóäåì ñòðîèòü àëãîðèòì (ÑÔÝ) äëÿ ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , .
. . , xn ) ∈ L? ðåêóðñèâíî â ñîîòâåòñòâèè ñ ëåììîé. Äëÿ ïðîâåðêèóñëîâèÿ f (1, x2 , . . . , xn ) ≡ f (0, x2 , . . . , xn ) äîñòàòî÷íî 2n − 1 áèíàðíûõáèòîâûõ îïåðàöèé (2n−1 ñðàâíåíèé ai = ai+2n−1 è 2n−1 − 1 êîíúþíêöèéïîëó÷åííûõ çíà÷åíèé). Àíàëîãè÷íî 2n − 1 áèíàðíûõ îïåðàöèé äîñòàòî÷íî äëÿ ïðîâåðêè óñëîâèÿ f (1, x2 , . . . , xn ) ≡ f (0, x2 , . . . , xn ) ⊕ 1. Äëÿïðîâåðêè óñëîâèÿ f (1, x2 , . . . , xn ) = f (0, x2 , . . . , xn ) ⊕ d äîñòàòî÷íî âçÿòüäèçúþíêöèþ äâóõ ïîëó÷åííûõ ðåçóëüòàòîâ ñðàâíåíèé. Ïðè ýòîì îáùåå÷èñëî áèòîâûõ îïåðàöèé 2(2n − 1) + 1 < 2n+1 .
Ïóñòü L(n) ìèíèìàëüíîå÷èñëî áèòîâûõ îïåðàöèé äëÿ îòâåòà íà âîïðîñ f (x1 , . . . , xn ) ∈ L? Òîãäà26L(1) = 1 (ò.ê. âûõîä z ≡ 1) è â ñîîòâåòñòâèè ñ ëåììîéL(n) < L(n − 1) + 2n+1 < L(n − 2) + 2n + 2n+1 << L(n − 3) + 2n−1 + 2n + 2n+1 < . . . << L(1) + 23 + 24 + . . . + 2n+1 < 2n+2 = 4N.Óòâåðæäåíèå 3.4 äîêàçàíî.Óòâåðæäåíèå 3.5. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ∈ M ? ñóùåñòâóåò àëãîðèòìn(ÑÔÝ) ñî ñëîæíîñòüþ O(N log N ), ãäå N = 2 äëèíà âõîäà.Äîêàçàòåëüñòâî.
Èçâåñòíî, ÷òî f (x1 , . . . , xn ) ∈ M òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáûõ äâóõ íàáîðîâ α̃ è β̃ òàêèõ, ÷òî α̃ =(α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ) è β̃ = (α1 , . . . , αi−1 , 0, αi+1 , . . . , αn ) (ãäå i ëþáîå), âûïîëíÿåòñÿ f (α̃) 6 f (β̃) [18]. ×èñëî óêàçàííûõ ïàð íàáîðîâ (α̃, β̃) ðàâíî n · 2n−1 . Òàêèì îáðàçîì, äëÿ ðàñïîçíàâàíèÿ ñâîéñòâà f ∈ M ? äîñòàòî÷íî èñïîëüçîâàòü n · 2n−1 áèòîâûõ îïåðàöèé x 6 y (òî åñòü x → y ) è çàòåì âçÿòü êîíúþíêöèþ ïîëó÷åííûõ çíà÷åíèé. Îáùåå÷èñëî áèòîâûõ îïåðàöèé áóäåò n · 2n−1 + n · 2n−1 − 1 = N log2 N − 1.Èç óòâåðæäåíèé 3.1-3.5 è òåîðåìû Ïîñòà î ïîëíîòå [18] ïîëó÷àåìñëåäóþùåå óòâåðæäåíèå.ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , .
. . , xn )Òåîðåìà 3.4. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ ðàñïîçíàâíèÿ ïîëíîòû ñèñòåìû ôóíêöèé ñóùåñòâóåò àëãîðèòì (ÑÔÝ) ñîO(N log N ), ãäå N äëèíà âõîäà.Çàìå÷àíèå. Âîðîíåíêî À. À. [6] íàøåë áîëåå áûñòðûé àëãîðèòì√ñî ñëîæíîñòüþ O(N log N log log N ) äëÿ ðàñïîçíàâàíèÿ ñâîéñòâà ìîíîòîííîñòè (êëàññ M ), îòêóäà ñëåäóåò, ÷òî â ïîñëåäíåé òåîðåìå îöåíêó√O(N log N ) ìîæíî ïîíèçèòü äî O(N log N log log N ).ñëîæíîñòüþ3.4. Ðàñïîçíàâàíèå ñîõðàíåíèÿ äâóõìåñòíûõïðåäèêàòîâÏóñòü Ek = {0, 1, . . .
, k − 1} è ïóñòü Ekn ìíîæåñòâî âñåõ íàáîðîâäëèíû n ñ ýëåìåíòàìè èç Ek . ×åðåç Pk áóäåì îáîçíà÷àòü ìíîæåñòâî âñåõk -çíà÷íûõ ôóíêöèé, òî åñòü ôóíêöèé, îòîáðàæàþùèõ Ekn â Ek ïðè âñåõn.Îïðåäåëåíèå. Ïðåäèêàòîì (m-ìåñòíûì) íà êîíå÷íîì ìíîæåñòâåD íàçûâàåòñÿ ëþáàÿ ôóíêöèÿ R(y1 . . . ym ) : Dm −→ {èñòèíà, ëîæü}.Îïðåäåëåíèå. Ïóñòü f (x1 . . . xn ) ∈ Pk è R(y1 , y2 ) 2-ìåñòíûéïðåäèêàò íà ìíîæåñòâå Ek . Áóäåì ãîâîðèòü, ÷òî f (x1 . . . xn ) ñîõðàíÿåòïðåäèêàò R, åñëè äëÿ ëþáûõ íàáîðîâ α̃ = (α1 . . . αn ) è β̃ = (β1 .
. . βn )27âûïîëíÿåòñÿ èìïëèêàöèÿ:(∀jR(αj , βj )) → R(f (α̃), f (β̃)).Îáîçíà÷èì U (R) êëàññ âñåõ ôóíêöèé,ñîõðàíÿþùèõ ïðåäèêàò R. Ïóñòüα̃ = (α1 , . . . , αn ), β̃ = (β1 , . . . , βn ) íàáîðû ñ ýëåìåíòàìè èç D èR 2-ìåñòíûé ïðåäèêàò íà D. Òîãäà îïðåäåëèì ïðåäèêàò Rn íà Dnñëåäóþùèì îáðàçîì:Rn (α̃, β̃) ≡ ∀jR(αj , βj ).Åñëè γ̃ = (α1 , .
. . , αn−1 ), δ̃ = (δ1 , . . . , δn−1 ), òî ëåãêî âèäåòü, ÷òîRn (α̃, β̃) ≡ Rn−1 (γ̃, δ̃)&R(αn , βn ).Ôèêñèðóåì Ek . Çàäàí ïðåäèêàò R(y1 , y2 ) íà Ek . Òðåáóåòñÿïîñòðîèòü àëãîðèòì äëÿ îòâåòà íà âîïðîñ f (x1 . . . xn ) ∈ U (R)?. Ïðèýòîì ñ÷èòàåòñÿ, ÷òî íàáîðû èç Ekn óïîðÿäî÷èâàþòñÿ ëåêñèêîãðàôè÷åñêèè ôóíêöèÿ f çàäàåòñÿ âåêòîðîì f = (a0 , a1 , . .
. , akn −1 ) åå çíà÷åíèé íàýòèõ íàáîðàõ; N = k n äëèíà âõîäà.  êà÷åñòâå àëãîðèòìîâ áóäåìðàññìàòðèâàòü ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ ñ ïðîèçâîëüíûìèáèíàðíûìè îïåðàöèÿìè íàä ýëåìåíòàìè ìíîæåñòâà Ek , íî áóäåì ãîâîðèòü î áèòîâîé ñëîæíîñòè, ïîñêîëüêó, åñëè ýëåìåíòû ìíîæåñòâà Ekçàêîäèðîâàòü äâîè÷íûìè ñëîâàìè, òî êàæäóþ òàêóþ îïåðàöèþ ìîæíîñìîäåëèðîâàòü íåêîòîðûì ÷èñëîì äâîè÷íûõ îïåðàöèé, ïîýòîìó ïåðåõîäê äâîè÷íûì ñõåìàì óâåëè÷èâàåò ñëîæíîñòü òîëüêî â êîíñòàíòó ðàç, àìû ðàññìàòðèâàåì ñëîæíîñòü òîëüêî ïî ïîðÿäêó.Òðèâèàëüíûé àëãîðèòì äëÿ ýòîé çàäà÷è èìååò ñëîæíîñòü O(N 2 )(ïðîâåðêà ïàð). Åñëè ïðåäèêàò R èñòèíåí íà d ïàðàõ, òî ñóùåñòâóåòàëãîðèòì ñî ñëîæíîñòüþ O(dn ) = O(N logk d ).
Îäíàêî âåðåí ñëåäóþùèéáîëåå ñèëüíûé ðåçóëüòàò, êîòîðûé îñíîâàí íà ìåòîäå ïåðåõîäà îò çàäà÷èðàñïîçíàâàíèÿ ê çàäà÷å âû÷èñëåíèÿ íåêîòîðîãî àëãåáðàè÷åñêîãî âûðàæåíèÿ [1].Çàäà÷à.Òåîðåìà 3.5. Äëÿ ëþáîãî ïðåäèêàòàR(y1 , y2 ) íà Ek ñóùåñòâóåòàëãîðèòì (ÑÔÝ), ðàñïîçíàþùèé f (x1 . . . xn ) ∈ U (R)? ñî ñëîæíîñòüþO(N log N ), ãäå N = k n äëèíà âõîäà.Äîêàçàòåëüñòâî.f (x1 . . . xn ) ∈/ U (R) ⇐⇒ ∃α̃, β̃(Rn (α̃, β̃)&R̄(f (α), f (β))) ⇐⇒⇐⇒ ∃α̃, β̃∃c, d(Rn (α̃, β̃)&(f (α̃) = c)&(f (β̃) = d)&R̄(c, d)) ⇐⇒_ _⇐⇒(Rn (α̃, β̃)&(f (α̃) = c)&(f (β̃) = d)&R̄(c, d)) =c,d∈Ek α̃,β̃28_=_(Rn (α̃, β̃)&(f (α̃) = c)&(f (β̃) = d)).(c,d):R̄(c,d) (α̃,β̃) ïîñëåäíåì âûðàæåíèè â ïåðâîé äèçúþíêöèè êîíñòàíòíîå ÷èñëî ñëàãàåìûõ, ïîýòîìó ñëîæíîñòü âû÷èñëåíèÿ ýòîãî âûðàæåíèÿ ïî ïîðÿäêóîïðåäåëÿåòñÿ ñëîæíîñòüþ âû÷èñëåíèÿ âòîðîé äèçúþíêöèè.
Ïðè ôèêñèðîâàííûõ c, d âû÷èñëåíèå ëîãè÷åñêèõ ïåðåìåííûõ uα̃ ≡ (f (α̃) = c) èvβ̃ ≡ (f (β̃) = d) òðåáóåò O(N ) îïåðàöèé.Ïóñòü L(N ) = L0 (n) ìèíèìàëüíàÿ áèòîâàÿ ñëîæíîcòü âû÷èñWëåíèÿ âûðàæåíèÿ α̃,β̃ Rn (α̃, β̃)uα̃ vβ̃ ïðè çàäàííûõ uα̃ , vβ̃ . Äîêàæåì, ÷òîL(N ) = O(N log N ).Ïóñòü α̃ = (γ̃, αn ), β̃ = (δ̃, βn ). Òîãäà__Rn (α̃, β̃)uα̃ vβ̃ =Rn−1 (γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =α̃,β̃α̃=(γ̃,αn ),β̃=(δ̃,βn )=_ _=_Rn−1 (γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =γ̃,δ̃ αn ,βnRn−1(γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =αn ,βnγ̃,δ̃=__Rn−1(γ̃, δ̃)_u(γ̃,αn )αnγ̃,δ̃=_v(δ̃,βn ) =βn :R(αn ,βn )__( Rn−1 (γ̃, δ̃)u(γ̃,αn ) w(δ̃,αn ) ),αn γ̃,δ̃ãäå w(δ̃,αn ) = βn :R(αn ,βn ) v(δ̃,βn ) .Îòñþäà L0 (n) 6 kL0 (n − 1) + k n (k − 1) + k − 1, ïîñêîëüêó çàäà÷à äëÿn ñâîäèòñÿ ê k òàêèì æå çàäà÷àì äëÿ n − 1, ïðè ýòîì äëÿ âû÷èñëåíèÿêàæäîé èç k n ïåðåìåííûõ w òðåáóåòñÿ íå áîëåå k −1 äèçúþíêöèé è ïîñëåðåøåíèÿ âñåõ k ïîäçàäà÷ òðåáóåòñÿ k − 1 äèçúþíêöèé äëÿ âû÷èñëåíèÿäèçúþíêöèè ïî αn .
Ïåðåõîäÿ ê L(N ), ïîëó÷àåì L(N ) 6 kL( Nk ) + O(N ),îòêóäà, ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå, L(N ) = O(N log N ).Òåîðåìà äîêàçàíà.W3.5. ÊëàññûFmÏóñòü òåïåðü R(y1 , . . . , ym ) m-ìåñòíûé ïðåäèêàò íà ìíîæåñòâåEk = {0, 1, . . . , k−1}. Åñëè α̃j = (α1j , α2j , . . . , αnj ), j = 1, 2, .
. . , m íàáîðûñ ýëåìåíòàìè èç Ek , òî îïðåäåëèìRn (α̃1 , α̃2 , . . . , α̃m ) ≡ ∀iR(αi1 , αi2 , . . . , αim ).29Áóäåì ãîâîðèòü, ÷òî ôóíêöèÿ f (x1 , . . . , xn ) èç Pkñîõðàíÿåò R, åñëè äëÿ ëþáûõ m íàáîðîâ α̃1 , α̃2 , . . . , α̃m âûïîëíÿåòñÿèìïëèêàöèÿÎïðåäåëåíèå.Rn (α̃1 , α̃2 , . . . , α̃m ) =⇒ R(f (α̃1 ), f (α̃2 ), . .
. , f (α̃m )).(3.1)Ðàññìîòðèì ñëåäóþùèé ïðåäèêàò Rm íà E2 = {0, 1}:(èñòèíà ⇐⇒ ∃i(yi = 0),Rm (y1 , . . . , ym ) =ëîæü⇐⇒ ỹ = (1, . . . , 1).Êëàññ âñåõ ôóíêöèé àëãåáðû ëîãèêè, ñîõðàíÿþùèõ ïðåäèêàò Rm ,îáîçíà÷èì F m . Êëàññû F m ïðè m = 2, 3, 4, . . . îáðàçóþò îäíó èç 8áåñêîíå÷íûõ öåïî÷åê çàìêíóòûõ êëàññîâ â àëãåáðå ëîãèêè. Ðàññìîòðèìñëåäóþùóþ çàäà÷ó.Çàäà÷à. Ïóñòü m > 2 ôèêñèðîâàííîå íàòóðàëüíîå ÷èñëî. Òðåáóåòñÿ ïîñòðîèòü àëãîðèòì äëÿ îòâåòà íà âîïðîñ f (x1 , . .
. , xn ) ∈ F m ?ïðè óñëîâèè, ÷òî ôóíêöèÿ ïîñòóïàåò íà âõîä â âèäå âåêòîðà çíà÷åíèéf (x1 , . . . , xn ) = (a0 , a1 , . . . , a2n −1 ) äëèíû N = 2n .Çàìåòèì, ÷òî òðèâèàëüíûé àëãîðèòì, îñíîâàííûé íà ïðîñìîòðåâñåõ âûáîðîê ïî m çíà÷åíèé ôóíêöèè è ïðîâåðêå èìïëèêàöèè (3.1)òðåáóåò ïî ïîðÿäêó íå ìåíåå N m îïåðàöèé. Îäíàêî çäåñü îïÿòü ìîæíî ïðèìåíèòü ìåòîä ïåðåõîäà îò çàäà÷è ðàñïîçíàâàíèÿ ê âû÷èñëåíèþàëãåáðàè÷åñêîãî âûðàæåíèÿ, ÷òîáû èñïîëüçîâàòü ñèëó àëãåáðû [1].Òåîðåìà 3.6. Äëÿ ëþáîãî ôèêñèðîâàííîãîàëãîðèòì äëÿ îòâåòà íà âîïðîñ3ñëîæíîñòüþ O(N log N ).m > 2 ñóùåñòâóåò f (x1 . . .
xn ) ∈ U (Rm )? ñ áèòîâîéÊîíñòàíòà çàâèñèò îò m (ðàñòåò ñ ðîñòîì m).Äîêàçàòåëüñòâî. Ïóñòü α̃1 , α̃2 , . . . , α̃m ïðîèçâîëüíûå íàáîðû, ãäåα̃j = (α1j , α2j , . . . , αnj ), è ïóñòü qα̃ äëÿ ïðîèçâîëüíîãî íàáîðà α̃ îáîçíà÷àåòòàêóþ ëîãè÷åñêóþ ïåðåìåííóþ, ÷òî qα̃ = èñòèíà òîãäà è òîëüêî òîãäà,êîãäà f (α̃) = 1. Òîãäà ïî îïðåäåëåíèþÇàìå÷àíèå.f (x1 , . . . , xn ) ∈/ Fm ⇐⇒n⇐⇒ ∃α̃1 , . . . , α̃m (Rm(α̃1 , . . .
, α̃m )&(f (α̃1 ) = 1)& . . . &(f (α̃m ) = 1)) ⇐⇒_n⇐⇒Rm(α̃1 , . . . , α̃m )qα̃1 · . . . · qα̃m =α̃1 ,...,α̃m=_Rm (α11 . . . α1m ) · Rm (α21 . . . α2m ) · . . . · Rm (αn1 . . . αnm )qα̃1 · . . . · qα̃m .α̃1 ,...,α̃m30Îïðåäåëèì ôóíêöèþ tm (α1 , . . . , αm ), ãäå αj ∈ {0, 1}, è ïåðåìåííûå uαñëåäóþùèì îáðàçîì:tm (α1 , . . . , αm ) =(0,åñëè R̄m (α1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
