В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 6
Текст из файла (страница 6)
Íî ýòîóñëîâèå ðàâíîñèëüíî òîìó, ÷òî èç vi â vj ñóùåñòâóåò ïóòü äëèíû íå áîëååp + 1. Òàêèì îáðàçîì, óòâåðæäåíèå ëåììû âåðíî è ïðè k = p + 1. Ëåììàäîêàçàíà.Åñëè â îðãðàôå G èç vi â vj ñóùåñòâóåò õîòÿ áû îäèí îðèåíòèðîâàííûé ïóòü, òî ñóùåñòâóåò òàêîé ïóòü áåç ïîâòîðåíèÿ âåðøèí è,ñëåäîâàòåëüíî, äëèíû íå áîëåå n−1, ãäå n ÷èñëî âåðøèí â G. Ïîýòîìóèç ëåììû ñëåäóåò, ÷òî Ā◦k = B ïðè ëþáîì k > n − 1. Áóäåì âû÷èñëÿòümïîñëåäîâàòåëüíî Ā, Ā◦2 , Ā◦4 , Ā◦8 , . . . Ā◦2 , ãäå m = dlog2 (n − 1)e.
Òàêmêàê 2m > n − 1, òî Ā◦2 = B . Ïî òåîðåìå 3.2 ñóùåñòâóåò àëãîðèòìÄîêàçàòåëüñòâî24äëÿ âû÷èñëåíèÿ âñåõ ýòèõ ìàòðèö, è â ÷àñòíîñòè B , ñ ÷èñëîì áèòîâûõîïåðàöèé m · O(nlog2 7 · log2 n) = O(nlog2 7 log3 n). Òåîðåìà äîêàçàíà.Çàìå÷àíèå. Ñì. çàìå÷àíèÿ ê òåîðåìå 3.1.3.3. Ðàñïîçíàâàíèå ïðèíàäëåæíîñòè áóëåâûõôóíêöèé ïðåäïîëíûì êëàññàì ÏîñòàÐàññìîòðèì çàäà÷ó ðàñïîçíàâàíèÿ ñâîéñòâ áóëåâûõ ôóíêöèé, ïðè÷åì ñåé÷àñ áóäåì ñ÷èòàòü, ÷òî áóëåâû ôóíêöèè ïîñòóïàþò íà âõîä àëãîðèòìà â âåêòîðíîì ïðåäñòàâëåíèè.
À èìåííî, ïóñòü âñå íàáîðû äëèíûn èç 0 è 1 óïîðÿäî÷åíû åñòåñòâåííûì îáðàçîì (êàê ñîîòâåòñòâóþùèåèì äâîè÷íûå ÷èñëà). Òîãäà áóëåâñêóþ ôóíêöèþ f (x1 , . . . , xn ) îò n ïåðåìåííûõ ìîæíî çàäàòü âåêòîðîì (a0 , a1 , . . . , a2n −1 ) åå çíà÷åíèé íà âñåõ 2níàáîðàõ.  êà÷åñòâå àëãîðèòìîâ ìû ðàññìîòðèì àëãîðèòìû ñ áèòîâûìèîïåðàöèÿìè. Ëþáîé òàêîé àëãîðèòì ìîæíî ðàññìàòðèâàòü êàê ñõåìó èçôóíêöèîíàëüíûõ ýëåìåíòîâ (ÑÔÝ), ýëåìåíòàìè â êîòîðîé ìîãóò áûòüëþáûå ôóíêöèè îò 2 ïåðåìåííûõ (èëè îò 1 ïåðåìåííîé). Åñëè îòâåò âçàäà÷å äëÿ äàííîãî âõîäà äà, òî íà âûõîäå äîëæíà áûòü 1, èíà÷å 0. Ïîäñëîæíîñòüþ àëãîðèòìà áóäåì ïîíèìàòü ÷èñëî áèòîâûõ îïåðàöèé (÷èñëîýëåìåíòîâ â ÑÔÝ).Òåîðåìà Ïîñòà î ïîëíîòå ñèñòåìû áóëåâûõ ôóíêöèé ñâîäèò âîïðîñî ïîëíîòå ê âîïðîñó î ïðèíàäëåæíîñòè ôóíêöèé 5 ïðåäïîëíûì êëàññàìT0 , T1 , S, L, M (ñì.
[18]). Ìû ðàññìîòðèì âîïðîñ î ñëîæíîñòè ðàñïîçíàâàíèÿ ýòèõ ñâîéñòâ. Íàïîìíèì, ÷òîf ∈ T0 ⇐⇒ f (0, . . . , 0) = 0, f ∈ T1 ⇐⇒ f (1, . . . , 1) = 1,f ∈ S ⇐⇒ f (x̄1 , . . . , x̄n ) = f¯(x1 , . . . , xn ),f ∈ L ⇐⇒ f (x1 , . . . , xn ) = c0 ⊕ c1 x1 ⊕ . . . ⊕ cn xn ,f ∈ M ⇐⇒ äëÿ âñåõ α̃ = (α1 , . . . , αn ) è β̃ = (β1 , . . . , βn )òàêèõ, ÷òî ∀i(αi 6 βi ), âûïîëíÿåòñÿ f (α̃) 6 f (β̃).Óòâåðæäåíèå 3.1. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , . . .
, xn )∈ T0 ?ñóùåñòâóåò àëãîðèòì(ÑÔÝ) ñî ñëîæíîñòüþ 1. ýòîì ñëó÷àå âûõîä z çàäàåòñÿ ôîðìóëîé z = ᾱ0 .Óòâåðæäåíèå 3.2. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , . . . , xn )∈ T1 ?ñóùåñòâóåò àëãîðèòì(ÑÔÝ) ñî ñëîæíîñòüþ 0. ýòîì ñëó÷àå âûõîä z çàäàåòñÿ ôîðìóëîé z = a2n −1 .Óòâåðæäåíèå 3.3. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ∈ S? ñóùåñòâóåòN = 2n äëèíà âõîäà.ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , .
. . , xn )(ÑÔÝ) ñî ñëîæíîñòüþO(N ),ãäå25àëãîðèòìÏî îïðåäåëåíèþ ñàìîäâîéñòâåííûõ ôóíêöèéf (x1 , . . . , xn ) ∈ S òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî α̃ = (α1 , . . . , αn )âûïîëíÿåòñÿ f (α1 , . . . , αn ) 6= f (ᾱ1 , . . . , ᾱn ), òî åñòü êîãäà äëÿ âñåõ i =0, 1, . . . , 2n−1 − 1 âûïîëíÿåòñÿ ai 6= a2n −1−i . Òàêèì îáðàçîì, äëÿ ðàñïîçíàâàíèÿ ñâîéñòâà f ∈ S? äîñòàòî÷íî èñïîëüçîâàòü 2n−1 áóëåâûõîïåðàöèé ai ⊕ a2n −1−i è çàòåì âçÿòü êîíúþíêöèþ ïîëó÷åííûõ çíà÷åíèé.Îáùåå ÷èñëî áèòîâûõ îïåðàöèé áóäåò 2n−1 + 2n−1 − 1 = N − 1.Äîêàçàòåëüñòâî.Óòâåðæäåíèå 3.4. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ∈ L? ñóùåñòâóåòN = 2n äëèíà âõîäà.ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , .
. . , xn )(ÑÔÝ) ñî ñëîæíîñòüþO(N ),ãäåàëãîðèòìËåììà 3.3.(f (0, x2 , . . . , xn ) ∈ L,f (x1 , . . . , xn ) ∈ L ⇐⇒f (1, x2 , . . . , xn ) ≡ f (0, x2 , . . . , xn ) ⊕ d, d ∈ {0, 1}.Åñëè f (x1 , . . . , xn ) = c1 x1 ⊕ c2 x2 ⊕ . . . ⊕ cn xn + c0 ,òî, î÷åâèäíî, f (0, x2 , .
. . , 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β̃ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
