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

. (Qm xm )[F (α1 , . . . , αk , xk+1 , . . . , xm )].Ïðèìåíèì äëÿ ðåøåíèÿ èñõîäíîé çàäà÷è (è âñåõ åå ïîäçàäà÷) ñëåäóþùèéðåêóðñèâíûé àëãîðèòì:1. Âû÷èñëèòü (Q2 x2 ) . . . (Qm xm )F (0, x2 , . . . , xm ) ýòèì æå ðåêóðñèâíûì àëãîðèòìîì. Çàïîìíèòü ïîëó÷åííîå çíà÷åíèå (1 áèò) â äîïîëíèòåëüíîé ÿ÷åéêå.752.Âû÷èñëèòüíàòîéæåçîíåýòèìæåàëãîðèòìîì(Q2 x2 ) . . . (Qm xm )F (1, x2 , . . .

, xm ).3. Åñëè Q1 = ∀ è îáà çíà÷åíèÿ, âû÷èñëåííûå â 1 è 2, ðàâíû 1, òîâûäàòü îòâåò 1, èíà÷å âûäàòü 0. Åñëè Q1 = ∃ è îáà çíà÷åíèÿ â 1 è 2ðàâíû 0, òî âûäàòü 0, èíà÷å âûäàòü 1.Èç îïèñàíèÿ àëãîðèòìà âèäíî, ÷òî äëÿ ðåøåíèÿ çàäà÷è êàæäîãîóðîâíÿ íóæíî íà 1 ÿ÷åéêó áîëüøå, ÷åì íà ðåøåíèå ëþáîé åå ïîäçàäà÷è.Òàê êàê íà âû÷èñëåíèå F (α1 , . . . , αm ) òðåáóåòñÿ ïàìÿòè íå áîëåå p1 (n),òî äëÿ âû÷èñëåíèÿ èñòèííîñòíîãî çíà÷åíèÿ èñõîäíîé ôîðìóëû òðåáóåòñÿïàìÿòü íå áîëåå p1 (n) + n ÿ÷ååê. Äëÿ óïðàâëåíèÿ ïðîöåññîì ïåðåõîäà îòîäíèõ ïîäçàäà÷ ê äðóãèì â îïèñàííîì àëãîðèòìå äîñòàòî÷íî ïîìíèòü,êàêàÿ ïîäçàäà÷à ðåøàåòñÿ â äàííûé ìîìåíò, òî åñòü ïîìíèòü çíà÷åíèÿα1 , .

. . , αk , îïðåäåëÿþùèå ýòó ïîäçàäà÷ó. Òàêèì îáðàçîì, â öåëîì îïðèñàííûé àëãîðèòì òðåáóåò íå áîëåå p(n) ÿ÷ååê ïàìÿòè, ãäå p íåêîòîðûéïîëèíîì.Òåîðåìà 6.2. Çàäà÷à QBF ÿâëÿåòñÿ P SP ACE -ïîëíîé.Äîêàçàòåëüñòâî. Íàì íàäî äîêàçàòü, ÷òî ëþáàÿ çàäà÷à L èçP SP ACE ïîëèíîìèàëüíî ñâîäèòñÿ ê QBF . Åñëè L ∈ P SP ACE , òîñóùåñòâóåò ìàøèíà Òüþðèíãà M , êîòîðàÿ ðåøàåò çàäà÷ó L ñ ïàìÿòüþíå áîëåå p1 (n) è âðåìåíåì íå áîëåå 2p(n) (ñì. ëåììó 6.1), ãäå näëèíàâõîäà. Ïóñòü x âõîä äëèíû n äëÿ çàäà÷è L. Íàì íàäî çà ïîëèíîìèàëüíîå âðåìÿ ïîñòðîèòü êâàíòèôèöèðîâàííóþ ôîðìóëó F (x) òàê,÷òî F (x) èñòèííà òîãäà è òîëüêî òîãäà, êîãäà x ∈ L.

Òîò ôàêò, ÷òîx ∈ L, ðàâíîñèëåí óòâåðæäåíèþ: äëÿ âõîäà x ñóùåñòâóåò ïðèíèìàþùåå(ñ îòâåòîì äà) âû÷èñëåíèå ìàøèíû M . Ýòî ïîñëåäíåå óòâåðæäåíèåìû è âûðàçèì â âèäå ôîðìóëû F (x) . Òàê æå, êàê ïðè äîêàçàòåëüñòâåN P -ïîëíîòû çàäà÷è ÂÛÏ, ââåäåì äâà ìíîæåñòâà ïåðåìåííûõ V è V 0 ,îïèñûâàþùèõ 2 ïðîèçâîëüíûå êîíôèãóðàöèè íà çîíå p1 (n), è çàïèøåìôîðìóëó F0 (V, V 0 ), âûðàæàþùóþ òîò ôàêò, ÷òî V è V 0 ïðàâèëüíî çàäàþòêîíôèãóðàöèè è ëèáî V = V 0 , ëèáî èç êîíôèãóðàöèè V ìû çà îäèíøàã ìàøèíû M ïåðåõîäèì â êîíôèãóðàöèþ V 0 .

Êàê ïîêàçàíî ïðè äîêàçàòåëüñòâå N P -ïîëíîòû çàäà÷è ÂÛÏ äëèíà ôîðìóëû F0 (V, V 0 ) ìîæåòáûòü îãðàíè÷åíà íåêîòîðûì ïîëèíîìîì p2 (n) è åå ìîæíî ïîñòðîèòü çàïîëèíîìèàëüíîå îò n âðåìÿ. Ôîðìóëà F0 (V, V 0 ) âûðàæàåò òîò ôàêò, ÷òîèç êîíôèãóðàöèè V â êîíôèãóðàöèþ V 0 ìîæíî ïåðåéòè çà íå áîëåå ÷åì 1øàã. Ïîñòðîèì òåïåðü èíäóêòèâíî ôîðìóëû F1 , F2 , . .

. , Fs , ãäå s = p(n),ñëåäóþùèì îáðàçîì. Ïóñòü W åùå îäíî ìíîæåñòâî ïåðåìåííûõ, îïèñûâàþùèõ êîíôèãóðàöèþ íà çîíå p1 (n). Òîãäà ïîëîæèìFk (V, V 0 ) = ∃W [Fk−1 (V, W )&Fk−1 (W, V 0 )].76Ôîðìóëà Fk âûðàæàåò òîò ôàêò, ÷òî V, V 0 ïðàâèëüíûå êîíôèãóðàöèèè èç V â V 0 ìîæíî ïåðåéòè çà íå áîëåå, ÷åì 2k øàãîâ. Ôîðìóëà âêâàäðàòíûõ ñêîáêàõ ðàâíîñèëüíà ñëåäóþùåé ôîðìóëå:(∀Y )(∀Z)[(Y = V )&(Z = W ) ∨ (Y = W )&(Z = V 0 ) → Fk−1 (Y, Z)]ãäå Y, Z äâà ìíîæåñòâà ïåðåìåííûõ, îïèñûâàþùèõ 2 ïðîèçâîëüíûå êîíôèãóðàöèè íà çîíå p1 (n).

Ïîýòîìó ôîðìóëó Fk ìîæíî çàïèñàòü â âèäå:Fk (V, V 0 ) ≡ (∃W )(∀Y )(∀Z)[((Y = V )&(Z = W ) ∨ (Y = W )&(Z = V 0 )) → Fk−1 (Y, Z)].Òàêèì îáðàçîì, äëèíà Fk (V, V 0 ) îòëè÷àåòñÿ îò äëèíû Fk−1 (V, V 0 ) íåáîëåå ÷åì íà íåêîòîðûé ïîëèíîì p3 (n) è äëèíà Fk (V, V 0 ) íå ïðåâîñõîäèòp2 (n) + kp3 (n). Ïóñòü âðåìÿ ðàáîòû ìàøèíû M íå ïðåâîñõîäèò 2p(n) ès = p(n). Òîãäà Fs (V, V 0 ) èìååò äëèíó íå áîëåå p2 (n)+p(n)·p3 (n) = p4 (n),ãäå p4 ïîëèíîì, è âûðàæàåò òîò ôàêò, ÷òî V è V 0 ïðàâèëüíûå êîíôèãóðàöèè è èç V â V 0 ìîæíî ïåðåéòè çà íå áîëåå 2p(n) øàãîâ ìàøèíûM .

Ïóñòü ôîðìóëà Gx (V ) âûðàæàåò òîò ôàêò, ÷òî êîíôèãóðàöèÿ Vÿâëÿåòñÿ ïðàâèëüíîé íà÷àëüíîé êîíôèãóðàöèåé äëÿ âõîäà x (íà çîíåp1 (n)), à ôîðìóëà H(V ) âûðàæàåò òîò ôàêò, ÷òî â êîíôèãóðàöèè Vñîñòîÿíèå äà. Òîãäà òîò ôàêò, ÷òî äëÿ âõîäà x ñóùåñòâóåò ïðèíèìàþùååâû÷èñëåíèå ìàøèíû M ìîæíî ïðåäñòàâèòü ôîðìóëîéF (x) = (∃V )(∃V 0 )[Gx (V )&H(V 0 )&Fs (V, V 0 )].Ïîñêîëüêó äëèíà ôîðìóë Gx (V ) è H(V ) ìîæåò áûòü îãðàíè÷åíàïîëèíîìîì îò n è îíè ìîãóò áûòü ïîñòðîåíû çà ïîëèíîìèàëüíîå îò nâðåìÿ (ñì.

äîêàçàòåëüñòâî N P -ïîëíîòû çàäà÷è ÂÛÏ), òî ïîëó÷àåì, ÷òîäëèíà F (x) íå ïðåâîñõîäèò ïîëèíîìà îò n è F (x) ìîæåò áûòü ïîñòðîåíàçà ïîëèíîìèàëüíîå îò n âðåìÿ. Òåîðåìà äîêàçàíà.Ïðè îïðåäåëåíèè êëàññà DLOG îáû÷íî èñïîëüçóþò ìîäåëü ìíîãîëåíòî÷íîé ìàøèíû Òüþðèíãà. Ïóñòü ó ìàøèíû Òüþðèíãà èìååòñÿíåñêîëüêî ëåíò, îäíà èç êîòîðûõ âûäåëåíà êàê âõîäíàÿ, è íà êàæäîéëåíòå èìååòñÿ îäíà ãîëîâêà.

Îäèí øàã ðàáîòû òàêîé ìàøèíû ñîñòîèòâ îäíîâðåìåííîì âûïîëíåíèè îáû÷íûõ äåéñòâèé êàæäîé ãîëîâêîé (óêàæäîé ãîëîâêè ñâîè äåéñòâèÿ), ïðè÷åì âåñü íàáîð äåéñòâèé îäíîçíà÷íîîïðåäåëÿåòñÿ òåìè ñèìâîëàìè, êîòîðûå îáîçðåâàþòñÿ âñåìè ãîëîâêàìèè ñîñòîÿíèåì ìàøèíû. Âõîäíîå ñëîâî çàïèñûâàåòñÿ íà âõîäíîé ëåíòå âñòàíäàðòíîé êîíôèãóðàöèè è ãîëîâêà íà âõîäíîé ëåíòå ìîæåò òîëüêî÷èòàòü ñèìâîëû, íî íå ìîæåò çàïèñûâàòü íîâûå.Îïðåäåëåíèå. Êëàññ DLOG îïðåäåëÿåòñÿ êàê êëàññ âñåõ çàäà÷ðàñïîçíàâàíèÿ (ÿçûêîâ), äëÿ êîòîðûõ ñóùåñòâóåò ðàñïîçíàþùàÿ èõ ìíî77ãîëåíòî÷íàÿ ìàøèíà Òüþðèíãà, èñïîëüçóþùàÿ íà âñåõ ëåíòàõ, êðîìåâõîäíîé, íå áîëåå c log2 n ÿ÷ååê, ãäå n äëèíà âõîäà è c íåêîòîðàÿêîíñòàíòà (äëÿ äàííîé çàäà÷è).Èñïîëüçóÿ ëåììó 6.1, íåòðóäíî ïîêàçàòü, ÷òî DLOG ⊆ P .

ÒàêèìîáðàçîìDLOG ⊆ P ⊆ N P ⊆ P SP ACE.Ìîæíî äîêàçàòü, ÷òî DLOG 6= P SP ACE , ïîýòîìó õîòÿ áû îäíî èçóêàçàííûõ âêëþ÷åíèé äîëæíî áûòü ñòðîãèì. Îäíàêî êàêîå (èëè êàêèå)èìåííî, ïîêà (2002 ãîä) íå èçâåñòíî.78Ëèòåðàòóðà1. Àëåêñååâ Â. Á. Ëîãè÷åñêèå ïîëóêîëüöà è èõ èñïîëüçîâàíèå äëÿ ïîñòðîåíèÿ áûñòðûõ àëãîðòìîâ // Âåñòíèê ÌÃÓ, Ñåðèÿ 1. Ìàòåìàòèêà, ìåõàíèêà 1997, N 1. C. 2229.2. Àëåêñååâ Â. Á. Ñëîæíîñòü óìíîæåíèÿ ìàòðèö (îáçîð) //  êí.

Êèáåðíåòè÷åñêèé ñáîðíèê, íîâàÿ ñåðèÿ, âûï. 25 Ì.: Ìèð, 1988. Ñ.189-236.3. Àëåêñååâ Â. Á., Ëîæêèí Ñ. À. Ýëåìåíòû òåîðèè ãðàôîâ, ñõåì èàâòîìàòîâ Ì.: Èçäàòåëüñêèé îòäåë ô-òà ÂÌèÊ ÌÃÓ, 2000. 58ñ.4. Àõî À., Õîïêðîôò Äæ., Óëüìàí Äæ. Ïîñòðîåíèåòåëüíûõ àëãîðèòìîâ. Ì.: Ìèð, 1979. 536 ñ.è àíàëèç âû÷èñëè-5. Áàðçäèíü ß. Ì.

Ñëîæíîñòü ðàñïîçíàâàíèÿ ñèììåòðèè íà ìàøèíàõÒüþðèíãà //  ñá. Ïðîáëåìû êèáåðíåòèêè, âûï. 15 Ì.: Íàóêà,1965. Ñ. 245-248.6. Âîðîíåíêî À. À. Î ñëîæíîñòè ðàñïîçíàâàíèÿ ìîíîòîííîñòè // êí. Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè, âûï. 8 Ì.:Íàóêà-Ôèçìàòëèò, 1999. Ñ. 301-303.7. Ãýðè Ì., Äæîíñîí Ä. Âû÷èñëèòåëüíûåçàäà÷è. Ì.: Ìèð, 1982. 416 ñ.ìàøèíû è òðóäíîðåøàåìûå8. Êàðàöóáà À.

À., Îôìàí Þ. Ï. Óìíîæåíèå ìíîãîçíà÷íûõ ÷èñåë íààâòîìàòàõ // ÄÀÍ ÑÑÑÐ 1962. Ò. 145. N 2. C. 293294.9. Êíóò Ä. Ý. Èñêóññòâî ïðîãðàììèðîâàíèÿ. Ò. 2. Ïîëó÷èñëåííûåãîðèòìû. 3-å èçä. Ì.: "Âèëüÿìñ 2000. 832 ñ.àë-10. Êíóò Ä. Ý. Èñêóññòâî ïðîãðàììèðîâàíèÿ. Ò. 3. Ñîðòèðîâêà è ïîèñê. 2-å èçä. Ì.: "Âèëüÿìñ 2000.

832 ñ.11. Êóäðÿâöåâ Â. Á., Àëåøèí Ñ. Â., Ïîäêîëçèí À. Ñ. Ââåäåíèåàâòîìàòîâ. Ì.: Íàóêà, 1985. 320 ñ.79â òåîðèþ12. Êóê Ñ. À. Ñëîæíîñòü ïðîöåäóð âûâîäà òåîðåì //  êí. Êèáåðíåòè÷åñêèé ñáîðíèê, íîâàÿ ñåðèÿ, âûï. 12 Ì.: Ìèð, 1975. Ñ. 5-15.13. Ïàïàäèìèòðèó Õ., Ñòàéãëèö Ê. Êîìáèíàòîðíàÿ îïòèìèçàöèÿ.ãîðèòìû è ñëîæíîñòü. Ì.: Ìèð, 1985. 510 ñ.14. Ðåéíãîëüä Ý., Íèâåðãåëüò Þ., Äåî Í. ÊîìáèíàòîðíûåÒåîðèÿ è ïðàêòèêà. Ì.: Ìèð, 1980.

476 ñ.Àë-àëãîðèòìû.15. Òîîì À. Ë. Î ñëîæíîñòè ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ, ðåàëèçóþùåé óìíîæåíèå öåëûõ ÷èñåë // ÄÀÍ ÑÑÑÐ 1963. Ò. 150. C. 496498.16. Øåíõàãå À., Øòðàññåí Â. Áûñòðîå óìíîæåíèå áîëüøèõ ÷èñåë // Âêí. Êèáåðíåòè÷åñêèé ñáîðíèê, íîâàÿ ñåðèÿ, âûï. 10 Ì.: Ìèð, 1973.Ñ. 87-98.17. Øòðàññåí Â. Àëãîðèòì Ãàóññà íå îïòèìàëåí //  êí. Êèáåðíåòè÷åñêèé ñáîðíèê, íîâàÿ ñåðèÿ, âûï. 7 Ì.: Ìèð, 1970. Ñ.

67-70.18. ßáëîíñêèé Ñ. Â. Ââåäåíèå â äèñêðåòíóþÌ.: Âûñøàÿ øêîëà, 2001. 384 ñ.80ìàòåìàòèêó. 3-å èçä. .