В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 7

. . , αm ),1,åñëè Rm (α1 , . . . , αm ).(0,uα =1,åñëè qα = ëîæü,åñëè qα = èñòèíà.Ëåãêî âèäåòü, ÷òî_Rm (α11 , . . . , α1m ) · . . . · Rm (αn1 , . . . , αnm )qα̃1 · . . . · qα̃m = èñòèíà ⇐⇒α̃1 ,...,α̃mXTn =tm (α11 , . . . , α1m ) · . . . · tm (αn1 , . . .

, αnm )uα̃1 · . . . · uα̃m > 0.α̃1 ,...,α̃mÏóñòü L0ap (n) = Lap (N ) íàèìåíüøåå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé, íåîáõîäèìûõ äëÿ âû÷èñëåíèÿ Tn . Îáîçíà÷èì β̃j =j(α1j , α2j , . . . , αn−1), γj = αnj è1m1mtn−1m (β̃1 , . . . , β̃m ) = tm (α1 , . . . , α1 ) · . . . · tm (αn−1 , . . . , αn−1 ).ÒîãäàTn =XXtm (α11 , . . . , α1m ) · . . . · tm (αn1 , . .

. , αnm ) · uβ̃1 ,γ1 · . . . · uβ̃m ,γm =β̃1 ,...,β̃m γ1 ,...,γm=XX=Xtn−1m (β̃1 , . . . , β̃m )uβ̃1 ,γ1 · . . . · uβ̃m ,γm =(γ1 ,...,γm )6=(1,...,1)β̃1 ,...,β̃mXtm (γ1 , . . . , γm )uβ̃1 ,γ1 · . . . · uβ̃m ,γm =(γ1 ,...,γm )∈E2mβ̃1 ,...,β̃m=Xtn−1m (β̃1 , . .

. , β̃m )tn−1m (β̃1 , . . . , β̃m )((uβ̃1 ,0 + uβ̃1 ,1 )(uβ̃2 ,0 + uβ̃2 ,1 ) · . . . · (uβ̃m ,0 + uβ̃m ,1 )−β̃1 ,...,β̃m−uβ̃1 ,1 uβ̃2 ,1 · . . . · uβ̃m ,1 ) =Xtn−1m (β̃1 , . . . , β̃m )vβ̃1 vβ̃2 · . . . · vβ̃m −β̃1 ,...,β̃m−Xn−1tm(β̃1 , . . . , β̃m )wβ̃1 wβ̃2 · . . . · wβ̃m ,β̃1 ,...,β̃mãäå vβ̃ = uβ̃,0 + uβ̃,1 , à wβ̃ = uβ̃,1 .Ñâåëè çàäà÷ó ñ ïàðàìåòðîì n ê 2 òàêèì æå ïîäçàäà÷àì ñ ïàðàìåòðîì n − 1. Îòñþäà L0ap (n) 6 2L0ap (n − 1) + 2n−1 + 1, ïîñêîëüêóäëÿ âû÷èñëåíèÿ âñåõ vβ̃ äîñòàòî÷íî 2n−1 ñëîæåíèé è îäíîãî âû÷èòàíèÿ31äîñòàòî÷íî äëÿ âû÷èñëåíèÿ Tn ïîñëå ðåøåíèÿ äâóõ ïîäçàäà÷.

Ïåðåõîäÿê N , èìååì L0ap (N ) = 2Lap ( N2 ) + O(N ). Îòñþäà ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå ïîëó÷àåì Lap (N ) = O(N log N ) (â ýòîé òåîðåìåèìååì a = 2, c = 2, α = 1). Îòìåòèì, ÷òî èñõîäíàÿ çàäà÷à áûëà äëÿuα̃ ∈ {0, 1}. Îäíàêî â ïîäçàäà÷àõ ïåðåìåííûå ìîãóò áûòü ïðîèçâîëüíûìè íàòóðàëüíûìè ÷èñëàìè. Ïåðåõîä ê ïîäçàäà÷àì äåëàåòñÿ n − 1 ðàç.Ïðè êàæäîì ïåðåõîäå ðàçðÿäíîñòü ïåðåìåííûõ óâåëè÷èâàåòñÿ íå áîëåå,÷åì íà 1, ïîýòîìó â ïîäçàäà÷àõ âñå ÷èñëà èìåþò äëèíó íå áîëåå n+1. Ïðèn = 0 ïîëó÷àþòñÿ ïîäçàäà÷è âû÷èñëåíèÿ T0 âèäà T0 = z·z·z·z·. .

.·z = z m ,â êîòîðûõ îáðàçóþòñÿ ÷èñëà äëèíû 6 m(n + 1). Ïðè ïåðåõîäå ê çàäà÷åèç ïîäçàäà÷ äëèíà ÷èñåë óâåëè÷èâàåòñÿ íå áîëåå, ÷åì íà 1, ïîýòîìó âñå÷èñëà â àëãîðèòìå èìåþò äëèíó íå áîëåå m(n + 1) + n 6 const · n. Ñëåäîâàòåëüíî, êàæäàÿ àðèôìåòè÷åñêàÿ îïåðàöèÿ òðåáóåò O(n2 ) = O(log2 N )áèòîâûõ îïåðàöèé, îòêóäà L(N ) = Lap (N ) · O(log2 N ) = O(N log3 N ).Òåîðåìà äîêàçàíà.324.

Îáùàÿ òåîðèÿ ñëîæíîñòè çàäà÷Åñëè ìû õîòèì ïîëó÷àòü óòâåðæäåíèÿ òèïà äëÿ ëþáûõ àëãîðèòìîâ, òî ìû äîëæíû ïðèíÿòü êàêóþ-íèáóäü óíèâåðñàëüíóþ ìîäåëüàëãîðèòìîâ. Îäíîé èç òàêèõ ìîäåëåé ÿâëÿåòñÿ ìàøèíà Òüþðèíãà.4.1. Ìàøèíû ÒüþðèíãàÌàøèíà Òüþðèíãà M èìååò ïîòåíöèàëüíî áåñêîíå÷íóþ ëåíòó, ðàçäåëåííóþ íà ÿ÷åéêè, è ãîëîâêó, êîòîðàÿ â êàæäûé (äèñêðåòíûé) ìîìåíòâðåìåíè t = 0, 1, 2, . . .

îáîçðåâàåò ðîâíî îäíó ÿ÷åéêó. Çàäàíî íåêîòîðîåêîíå÷íîå ìíîæåñòâî ñîñòîÿíèé Q = {q0 , q1 , . . . , ql }, è ìàøèíà â êàæäûéìîìåíò âðåìåíè íàõîäèòñÿ ðîâíî â 1 èç ýòèõ ñîñòîÿíèé. Çàäàí êîíå÷íûéëåíòî÷íûé (ðàáî÷èé) àëôàâèò C = {c0 , c1 , . . . , cm }, ãäå c0 = Λ ïóñòîéñèìâîë, è â êàæäûé ìîìåíò âðåìåíè â êàæäîé ÿ÷åéêå íàõîäèòñÿ ðîâíî 1ñèìâîë èç àëôàâèòà C , ïðè÷åì áóäåì ñ÷èòàòü, ÷òî ñèìâîëû, îòëè÷íûå îòΛ, íàõîäÿòñÿ ëèøü â êîíå÷íîì ÷èñëå ÿ÷ååê. Ìàøèíà M õàðàêòåðèçóåòñÿåå ïðîãðàììîé, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé êîíå÷íûé íàáîð êîìàíäâèäà: ci qj → ck qr T , ãäå ci ∈ C , ck ∈ C , qj ∈ Q, qr ∈ Q, T ∈ {L, R, S}. Íàêàæäîì òàêòå ìàøèíà M ðàáîòàåò ñëåäóþùèì îáðàçîì. Åñëè ãîëîâêàîáîçðåâàåò ÿ÷åéêó, â êîòîðîé íàõîäèòñÿ ñèìâîë ci , M íàõîäèòñÿ â ñîñòîÿíèè qj è â ïðîãðàììå ìàøèíû M åñòü êîìàíäà ci qj → ck qr T , òî ñèìâîëâ îáîçðåâàåìîé ÿ÷åéêå çàìåíÿåòñÿ íà ck , ìàøèíà ïåðåõîäèò â ñîñòîÿíèåqr è ãîëîâêà îñòàåòñÿ íà ìåñòå, åñëè T = S , èëè ñäâèãàåòñÿ íà 1 ÿ÷åéêóâïðàâî èëè âëåâî, åñëè T = R èëè T = L.

Äàëåå ìàøèíà ïåðåõîäèòê ñëåäóþùåìó òàêòó è ïîâòîðÿåò ýòîò ïðîöåññ. Åñëè æå â ïðîãðàììåìàøèíû íåò êîìàíäû, â ëåâîé ÷àñòè êîòîðîé ñòîèò ïàðà ci qj , òî ìàøèíàîñòàíàâëèâàåòñÿ.Ìû áóäåì ðàññìàòðèâàòü òîëüêî äåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà, òî åñòü òàêèå, ó êîòîðûõ â ïðîãðàììå êàæäàÿ ïàðà ci qj âñòðå÷àåòñÿ â ëåâûõ ÷àñòÿõ êîìàíä íå áîëåå îäíîãî ðàçà.

 ýòîì ñëó÷àå êàæäûéøàã ìàøèíû îïðåäåëÿåòñÿ îäíîçíà÷íî.Îïðåäåëåíèå. Åñëè A àëôàâèò, òî ÷åðåç A∗ áóäåì îáîçíà÷àòüìíîæåñòâî âñåõ (êîíå÷íûõ) ñëîâ â àëôàâèòå A. Ïóñòü C ëåíòî÷íûéàëôàâèò ìàøèíû M , C0 = C \ {Λ} è ïóñòü çàäàí íåêîòîðûé âõîäíîéàëôàâèò A, òàêîé, ÷òî A ⊆ C0 . Òîãäà ìû áóäåì ñ÷èòàòü, ÷òî ìàøèíà Mîñóùåñòâëÿåò ïðåîáðàçîâàíèå ϕM : A∗ → C0∗ ∪ {∗}, êîòîðîå îïðåäåëÿåòñÿñëåäóþùèì îáðàçîì (çäåñü ∗ â {∗} òðàêòóåòñÿ êàê íåîïðåäåëåííîñòü).Ïóñòü çàäàíî íåêîòîðîå ñëîâî ā = a1 a2 . . . an ∈ A∗ .

Ðàçìåñòèì ñèìâîëûýòîãî ñëîâà â ïîñëåäîâàòåëüíûå ÿ÷åéêè ëåíòû, à â îñòàëüíûå ÿ÷åéêè33ïîìåñòèì Λ, ïîìåñòèì ãîëîâêó íà ÿ÷åéêó, â êîòîðîé ñòîèò a1 , óñòàíîâèì ìàøèíó â íà÷àëüíîå ñîñòîÿíèå q1 è íà÷íåì ðàáîòó ìàøèíû. Åñëèïîñëå ýòîãî ìàøèíà M áóäåò ðàáîòàòü áåñêîíå÷íî äîëãî, òî ñ÷èòàåì,÷òî ϕM (a1 a2 . . . an ) = ∗.

Åñëè ìàøèíà M îñòàíîâèòñÿ è íà ëåíòå âñåñèìâîëû ðàâíû Λ èëè ìåæäó ñèìâîëàìè àëôàâèòà C0 áóäåò âñòðå÷àòüñÿΛ, òî òàêæå ϕM (a1 a2 . . . an ) = ∗. Åñëè æå ïîñëå îñòàíîâêè ìàøèíû Mâñå ñèìâîëû àëôàâèòà C0 íà ëåíòå ñòîÿò ïîäðÿä, îáðàçóÿ ñëîâî b̄, òîϕM (ā) = b̄.Òåçèñ Òüþðèíãà. Äëÿ ëþáîãî àëãîðèòìè÷åñêîãî ïðåîáðàçîâàíèÿ∗ϕ : A → C0∗ ∪ {∗} ñóùåñòâóåòïðåîáðàçîâàíèå ϕ.ìàøèíà ÒüþðèíãàM,îñóùåñòâëÿþùàÿ4.2. Ñóùåñòâîâàíèå ñëîæíûõ çàäà÷Ðàññìîòðèì âñå ìàøèíû Òüþðèíãà, èìåþùèå â ëåíòî÷íîì àëôàâèòå ñèìâîëû Λ è |. Ïóñòü Z + = {0} ∪ N , ãäå N ìíîæåñòâî íàòóðàëüíûõ÷èñåë. Áóäåì ïðåäñòàâëÿòü ÷èñëî k ∈ Z + íà ëåíòå ìàøèíû â âèäå êîäàΛ || . . . | Λ, ãäå êîëè÷åñòâî | ðàâíî k + 1 (îñòàëüíûå ñèìâîëû íà ëåíòå Λ).Íàáîð (k1 , k2 , .

. . , kn ) áóäåì ïðåäñòàâëÿòü â âèäå êîäà Λ || . . . | Λ || . . . |Λ . . . Λ || . . . | Λ,ãäå â ïåðâîì ìàññèâå k1 + 1 ñèìâîëîâ |, âî âòîðîì k2 + 1è ò.ä. Ïðèìåíÿÿ ìàøèíó M ê êîäó ÷èñëà èëè íàáîðà, áóäåì ïîìåùàòüãîëîâêó íà ñàìûé ïåðâûé ñèìâîë | è óñòàíàâëèâàòü ìàøèíó M â ååíà÷àëüíîå ñîñòîÿíèå q1 .Îïðåäåëåíèå. Äëÿ ëþáîé ìàøèíû Òüþðèíãà M è ëþáîãî íàòóðàëüíîãî ÷èñëà n áóäåì ñ÷èòàòü, ÷òî ìàøèíà M âû÷èñëÿåò ôóíêöèþf (x1 , x2 , . . . , xn ) : (Z + )n → Z + ∪ {∗} êîòîðàÿ îïðåäåëÿåòñÿ ñëåäóþùèìîáðàçîì.

Ïðèìåíèì ìàøèíó M ê êîäó íàáîðà (a1 , a2 , . . . , an ). Åñëè Mîñòàíîâèòñÿ è ïîñëå îñòàíîâêè íà ëåíòå áóäåò òîëüêî êîä íåêîòîðîãî÷èñëà b ∈ Z + , òî f (a1 , a2 , . . . , an ) = b. Âî âñåõ îñòàëüíûõ ñëó÷àÿõf (a1 , a2 , . . . , an ) = ∗ (íåîïðåäåëåííîñòü).Îïðåäåëåíèå. Ôóíêöèÿ f (x1 , x2 , . . . , xn ) : (Z + )n → Z + ∪ {∗}íàçûâàåòñÿ âû÷èñëèìîé, åñëè ñóùåñòâóåò ìàøèíà Òüþðèíãà M , êîòîðàÿåå âû÷èñëÿåò.Îïðåäåëåíèå. Ãîâîðÿò, ÷òî ìàøèíà M ïðàâèëüíî âû÷èñëÿåò ôóíêöèþ f (x1 , x2 , . . . , xn ), åñëè, íà÷èíàÿ ðàáîòó ñ êîäà íàáîðà(a1 , . . . , an ), ìàøèíà M â òîì ñëó÷àå, êîãäà f (a1 , a2 , . . .

, an ) íå îïðåäåëåíî, îáÿçàòåëüíî ðàáîòàåò áåñêîíå÷íî äîëãî, à â òîì ñëó÷àå, êîãäàf (a1 , a2 , . . . , an ) = b, ìàøèíà îñòàíàâëèâàåòñÿ, íà ëåíòå îñòàåòñÿ êîä b èãîëîâêà ìàøèíû îáîçðåâàåò ñàìûé ëåâûé ñèìâîë |.34Óòâåðæäåíèå. Åñëèf (x1 , x2 , . . . , xn ) âû÷èñëèìà, òî ñóùåñòâóåòM , êîòîðàÿ åå âû÷èñëÿåò ïðàâèëüíî.Äîêàçàòåëüñòâî ñì., íàïðèìåð, â [18].Îïðåäåëåíèå. Âñþäó îïðåäåëåííûå âû÷èñëèìûå ôóíêöèè ìû áóäåì íàçûâàòü îáùåðåêóðñèâíûìè ôóíêöèÿìè.

(Îáû÷íî îáùåðåêóðñèâíûå ôóíêöèè îïðåäåëÿþò èíà÷å, íî äàííîå îïðåäåëåíèå ýêâèâàëåíòíîîáû÷íîìó; ñì., íàïðèìåð, [18]).Ôóíêöèÿ, âû÷èñëÿåìàÿ ìàøèíîé M , íå èçìåíèòñÿ, åñëè ïðîèçâîëüíî ïåðåèìåíîâàòü âñå ñèìâîëû ëåíòî÷íîãî àëôàâèòà, êðîìå | è Λ, èâñå ñîñòîÿíèÿ, îñòàâëÿÿ íà÷àëüíîå ñîñòîÿíèå íà÷àëüíûì (êîíå÷íî, ðàçíûå ñèìâîëû äîëæíû ïåðåèìåíîâûâàòüñÿ â ðàçíûå). Ïîýòîìó ìû áóäåìñ÷èòàòü, ÷òî åñòü áåñêîíå÷íûé ôèêñèðîâàííûé àëôàâèò {c0 = Λ, c1 =|, c2 , c3 , . . .}, èç êîòîðîãî áåðåòñÿ ëåíòî÷íûé àëôàâèò ìàøèíû M , è áåñêîíå÷íûé ôèêñèðîâàííûé àëôàâèò {q0 , q1 , q2 , . . .}, èç êîòîðîãî áåðóòñÿñîñòîÿíèÿ ìàøèíû M . Áóäåì çàïèñûâàòü èíäåêñû â ñòðîêó ïîñëå c èëèq , ïðåäñòàâëÿÿ èõ â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ (íàïðèìåð, c6 = c110).Ïðîãðàììó ìàøèíû M áóäåì çàïèñûâàòü â âèäå ïîñëåäîâàòåëüíîñòèâñåõ åå êîìàíä ci qj −→ ck qr T , ðàçäåëåííûõ òî÷êîé ñ çàïÿòîé.

Òîãäàïðîãðàììà ëþáîé ìàøèíû áóäåò ïðåäñòàâëÿòü ñîáîé ñëîâî â àëôàâèòåD = {Λ, |, c, q, 0, 1, −→, R, L, S, ; }.ìàøèíà ÒüþðèíãàÒåîðåìà 4.1. Ñóùåñòâóåò àëãîðèòì íóìåðàöèè âñåõ ìàøèíÒüþðèíãà èç óêàçàííîãî âûøå ñåìåéñòâà òàêîé, ÷òî äëÿ âîññòàíîâëåíèÿ ïðîãðàììû ïî åå íîìåðó òàêæå ñóùåñòâóåò àëãîðèòì.Áóäåì ñ÷èòàòü, ÷òî ñèìâîëû àëôàâèòà D óïîðÿäî÷åíû (íàïðèìåð, òàê, êàê ýòî ñäåëàíî âûøå).