1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 18
Текст из файла (страница 18)
Íàïðèìåð, àëãîðèòì, ïðè èñïîëíåíèè êîòîðîãî íåîáõîäèìî ïðîàíàëèçèðîâàòüâñå ïîñëåäîâàòåëüíîñòè äëèíû n èç öèôð îò 0 äî 9, ïîòðåáóåò äëÿ ýòîãîêàê ìèíèìóì 10n øàãîâ. Ïðåäïîëîæèì, ÷òî äëÿ àíàëèçà êàæäîé òàêîéïîñëåäîâàòåëüíîñòè íåîáõîäèìà îäíà ìèëëèîííàÿ ñåêóíäû. Òîãäà äëÿàíàëèçà âñåõ ïîñëåäîâàòåëüíîñòåé äëèíû, ñêàæåì 5, ïîòðåáóåòñÿ äåñÿòàÿ äîëÿ ñåêóíäû, äëÿ äëèíû 10 óæå 2 ÷àñà 40 ìèíóò, äëÿ äëèíû 11 áîëåå ñóòîê, äëÿ äëèíû 12 îêîëî 10 ñóòîê, äëÿ äëèíû 13 ïî÷òè 4ìåñÿöà, äëÿ äëèíû 14 áîëåå 3 ëåò, äëÿ äëèíû 15 áîëåå 30 ëåò. ×àñòî âñòðå÷àþòñÿ ñèòóàöèè, êîãäà íåîáõîäèìî ðåøàòü ïîäîáíûå çàäà÷èäëÿ ãîðàçäî áîëüøèõ n. Òàêèì îáðàçîì, â ðÿäå ïðàêòè÷åñêèõ ñëó÷àåâíåâîçìîæíî äîæäàòüñÿ, êîãäà æå íàêîíåö íàø êîìïüþòåð âûäàñò íàìîòâåò. Ìîæíî ïûòàòüñÿ óïîâàòü íà òî, ÷òî áûñòðîäåéñòâèå ñîâðåìåííûõêîìïüþòåðîâ ðàñòåò, è ýòî íå ÿâëÿåòñÿ ñåðüåçíîé ïðîáëåìîé.
Îäíàêî,íàïðèìåð, çà ïåðèîä ñ 1998 ïî 2003 ãîäû áûñòðîäåéñòâèå ïåðñîíàëüíûõêîìïüþòåðîâ âîçðîñëî ïðèìåðíî â 10 ðàç. Îòñþäà ñëåäóåò ïðîñòîé âûâîä. ÷òî åñëè áûñòðîäåéñòâèå êîìïüþòåðîâ áóäåò âîçðàñòàòü â 10 ðàç101102Ãëàâà 5. Ââåäåíèå â ñëîæíîñòü àëãîðèòìîâêàæäûå 5 ëåò è åñëè ñåé÷àñ ìû â ñîñòîÿíèè ðåàëüíî ðåøàòü ïîäîáíûåçàäà÷è ñàìîå áîëüøåå äëÿ íåêîòîðîãî n, òî, âèäèìî, ëåò ÷åðåç 5 ìû ñìîæåì ðåøàòü ýòè çàäà÷è äëÿ n + 1. Åñëè, ñêàæåì, â ðàññìàòðèâàåìîéñèòóàöèè, ñåãîäíÿ ìû â ñîñòîÿíèè ðåàëüíî ðåøàòü çàäà÷ó äëÿ n = 11,òî ÷åðåç 20 ëåò ìû ñìîæåì ðåøàòü èõ óæå äëÿ n = 15. È ïðîãðàììèñòó,êîòîðîìó íàäî çàïðîãðàììèðîâàòü ðåøåíèå çàäà÷è äëÿ n = 20, îñòàåòñÿòîëüêî ïîñî÷óâñòâîâàòü.Òàêèì îáðàçîì, îöåíêà ÷èñëà îïåðàöèé ðàáîòû àëãîðèòìà äåëîî÷åíü âàæíîå è îòíþäü íå áåñïîëåçíîå.Ñ÷èòàåòñÿ, ÷òî ðåàëüíî ïðèãîäíû äëÿ ñ÷åòà àëãîðèòìû, ÷èñëî îïåðàöèé êîòîðûõ îöåíèâàåòñÿ íåêîòîðûì ïîëèíîìîì p(n) îò äëèíû âõîäíûõäàííûõ n.
Ýòà îöåíêà, áåçóñëîâíî, ñïîðíà è äîñòàòî÷íî ãðóáà, íî â ðÿäåñëó÷àåâ îíà, òåì íå ìåíåå, ïîçâîëÿåò îòäåëèòü ïðàêòè÷åñêè ïðèãîäíûåàëãîðèòìû îò íåïðèãîäíûõ.  ñëåäóþùåì ïàðàãðàôå ìû äàäèì áîëååñòðîãèå îïðåäåëåíèÿ.5.2 Íåäåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà èêëàññû P è NPÐàñøèðèì ïîíÿòèå ìàøèíû Òüþðèíãà, ðàçðåøèâ ïîìåùàòü â åå ïðîãðàììó äëÿ êàæäûõ qi è aj óæå íå ìàêñèìóì îäíó à íåñêîëüêî êîìàíäâèäà qi aj → . . . Òåïåðü, íàõîäÿñü â ñîñòîÿíèè qi è îáîçðåâàÿ íà ëåíòåñèìâîë aj , â ïðîöåññå âû÷èñëåíèÿ ìàøèíà ìîæåò èñïîëíÿòü ëþáóþ èçòàêèõ êîìàíä. Òàêèì îáðàçîì, èç îäíîé êîíôèãóðàöèè âîçìîæíî ïðîèçâåñòè íåñêîëüêî ðàçëè÷íûõ âû÷èñëåíèé. Ââèäó òîãî, ÷òî ñëåäóþùèéøàã ìàøèíû óæå íå ÿâëÿåòñÿ îäíîçíà÷íî îïðåäåëåííûì êîíôèãóðàöèåé ìàøèíû, òàêèå ìàøèíû íàçûâàþòñÿ íåäåòåðìèíèðîâàííûìè.
×òîáûïîä÷åðêíóòü ýòî ðàçëè÷èå, îáû÷íûå ìàøèíû Òüþðèíãà áóäóò íàçûâàòüñÿ èíîãäà äåòåðìèíèðîâàííûìè. Î÷åâèäíî, ÷òî äåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì íåäåòåðìèíèðîâàííûõ.Ïóñòü A êîíå÷íûé àëôàâèò è ïóñòü ¤, 0, 1 ∈/ A. Íåäåòåðìèíèðîâàííàÿ ìàøèíà Òüþðèíãà ñ âíåøíèì àëôàâèòîì, ñîäåðæàùèì A ∪ {¤, 0, 1},íàçûâàåòñÿ ïîëèíîìèàëüíî îãðàíè÷åííîé íàä A, åñëè ñóùåñòâóåò ïîëèíîì p(x) ñ íàòóðàëüíûìè êîýôôèöèåíòàìè òàêîé, ÷òî äëÿ ëþáîãîw ∈ A∗ ëþáîå âû÷èñëåíèå èç êîíôèãóðàöèè q1 ¤w¤ çàêàí÷èâàåòñÿ âñîñòîÿíèè q0 è ñîäåðæèò íå áîëåå, ÷åì p(|w|) øàãîâ.Áóäåì ãîâîðèòü, ÷òî äåòåðìèíèðîâàííàÿ Ìàøèíà Òüþðèíãà M ðàñïîçíàåò ÿçûê L íàä A, åñëè L ⊆ A∗ è äëÿ ëþáîãî w ∈ A∗ âûïîëíåíîñëåäóþùåå ñâîéñòâî: åñëè çàïóñòèòü M èç êîíôèãóðàöèè q1 ¤w¤, òî â5.2. Íåäåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà è êëàññû P è NP103ñëó÷àå w ∈ L îíà îñòàíîâèòñÿ â êîíôèãóðàöèè âèäà .
. . q0 1 . . ., à â ñëó÷àå w ∈/ L îíà îñòàíîâèòñÿ â êîíôèãóðàöèè âèäà . . . q0 0 . . . Åñëè ïðè ýòîìM ïîëèíîìèàëüíî îãðàíè÷åíà, òî ãîâîðÿò, ÷òî ÿçûê L ïîëèíîìèàëüíîðàñïîçíàåòñÿ ýòîé ìàøèíîé íàä A. Åñëè L ïîëèíîìèàëüíî ðàñïîçíàåòñÿ êàêîéíèáóäü ìàøèíîé íàä A, òî ãîâîðÿò, ÷òî L ïîëèíîìèàëüíîðàñïîçíàâàåì íà äåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà íàä A (ñëîâîäåòåðìèíèðîâàííûõ ïðè ýòîì, êàê ïðàâèëî, îïóñêàþò).Áóäåì òàêæå ãîâîðèòü, ÷òî íåäåòåðìèíèðîâàííàÿ Ìàøèíà Òüþðèíãà M ðàñïîçíàåò ÿçûê L íàä A, åñëè L ⊆ A∗ è äëÿ ëþáîãî w ∈ A∗âûïîëíåíî ñëåäóþùåå ñâîéñòâî: âñå âû÷èñëåíèÿ íà ìàøèíå M èç êîíôèãóðàöèè q1 ¤w¤ êîãäà-íèáóäü çàâåðøàòñÿ, ïðè÷åì w ∈ L âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò õîòÿ áû îäíî âû÷èñëåíèå,çàâåðøàþùååñÿ â êîíôèãóðàöèè âèäà . . .
q0 1 . . . Åñëè ïðè ýòîì M ïîëèíîìèàëüíî îãðàíè÷åíà, òî ãîâîðÿò, ÷òî ÿçûê L ïîëèíîìèàëüíî ðàñïîçíàåòñÿ ýòîé ìàøèíîé íàä A. Åñëè L ïîëèíîìèàëüíî ðàñïîçíàåòñÿêàêîéíèáóäü íåäåòåðìèíèðîâàííîé ìàøèíîé íàä A, òî ãîâîðÿò, ÷òî Lïîëèíîìèàëüíî ðàñïîçíàâàåì íà íåäåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà íàä A.Èç ñëåäóþùåãî óòâåðæäåíèÿ ôàêòè÷åñêè ñëåäóåò, ÷òî óïîìèíàíèåàëôàâèòà A â ýòèõ îïðåäåëåíèÿõ ìîæíî îïóñòèòü.Ïðåäëîæåíèå 5.2.1 Ïóñòü L ïðîèçâîëüíûé ÿçûê íàä êîíå÷íûì àëôàâèòîì A, ¤, 0, 1 ∈/ A, è ïóñòü àëôàâèò A0 ñîñòîèò èç âñåõ ñèìâîëîâ, ñîäåðæàùèõñÿ õîòÿ áû â îäíîì èç ñëîâ ÿçûêà L.
Òîãäà ñëåäóþùèåóñëîâèÿ ýêâèâàëåíòíû:1. L (ïîëèíîìèàëüíî) ðàñïîçíàåòñÿ íåêîòîðîé ìàøèíîé Òüþðèíãàíàä A;2. L (ïîëèíîìèàëüíî) ðàñïîçíàåòñÿ íåêîòîðîé ìàøèíîé Òüþðèíãàíàä A0 .Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî (1)→(2) î÷åâèäíî.Äîêàæåì (2)→(1). Ïðåäïîëîæèì, ÷òî ìàøèíà Òüþðèíãà M ðàñïîçíàåò L íàä A0 . Ïóñòü òàêæå A0 = {a1 , .
. . , ak } è A \ A0 = {c1 , . . . , cm }.Èäåÿ ñîñòîèò â òîì, ÷òîáû ìîäèôèöèðîâàòü M òàê, ÷òîáû îíà ðàñïîçíàâàëà L óæå íàä A. Ìîäèôèöèðîâàííàÿ ìàøèíà, íà÷àâ èç êîíôèãóðàöèèq1 ¤w¤, w ∈ A∗ , ïðîéäåò ïî âñåì ñèìâîëàì ñëîâà w è ïðîâåðèò, åñòü ëèñðåäè íèõ õîòÿ áû îäèí èç ñèìâîëîâ c1 , . . . , cm . Åñëè äà, òî îíà îñòàíîâèòñÿ â êîíôèãóðàöèè âèäà .
. . q0 0 . . ., à åñëè íåò, òî îíà âåðíåòñÿ êïåðâîìó ñèìâîëó ¤ è çàïóñòèò èñõîäíóþ ìàøèíó M .104Ãëàâà 5. Ââåäåíèå â ñëîæíîñòü àëãîðèòìîâÒåïåðü îñóùåñòâèì ïîñòðîåíèå òàêîé ìàøèíû. Îïðåäåëèì ìàøèíóM0 ñëåäóþùèìè êîìàíäàìè:q1 ¤ → r1 ¤Rr1 a1 → r1 a1 R···r1 ak → r1 ak Rr1 ¤ → r2 ¤Lr2 a1 → r2 a1 L···r2 ak → r2 ak Lr2 ¤ → q0 ¤r1 c1 → q0 0···r1 cm → q0 0Çäåñü r0 è r1 íîâûå ñîñòîÿíèÿ, íå âñòðå÷àþùèåñÿ â M è îòëè÷íûå îòq0 , q1 .Íåòðóäíî óáåäèòüñÿ, ÷òî åñëè w ∈ A∗0 , òî ìàøèíà M0 ÷åðåç 2(|w| + 1)øàãîâ îñòàíîâèòñÿ â êîíôèãóðàöèè q0 ¤w¤. Åñëè íåò, òî çà ìåíåå, ÷åì2(|w| + 1) øàãîâ îíà îñòàíîâèòñÿ â êîíôèãóðàöèè âèäà .
. . q0 0 . . .Îïðåäåëèì òåïåðü ìàøèíó M 0 , êàê ðåçóëüòàò äîáàâëåíèÿ â ìàøèíóM êîìàíäû q0 → q0 0.Ëåãêî âèäåòü, ÷òî êîìïîçèöèÿ ìàøèí M 00 = M0 · M 0 , îïðåäåëåííàÿâ óïðàæíåíèè 4 íà ñòð. 75, îáëàäàåò òðåáóåìûìè ñâîéñòâàìè, òî åñòüðàñïîçíàåò ÿçûê L óæå íàä àëôàâèòîì A. Íåòðóäíî òàêæå óáåäèòüñÿ,÷òî åñëè M áûëà ïîëèíîìèàëüíî îãðàíè÷åíà, ñêàæåì, ïîëèíîìîì p(x),òî òàêîâà è M 00 , ïîñêîëüêó ïðè çàïóñêå ìàøèíû M 00 èç êîíôèãóðàöèèq1 ¤w¤ ôàêòè÷åñêè ñíà÷àëà ìàøèíà M0 âûïîëíèò íå áîëåå, ÷åì 2(|w|+1)øàãîâ, à ïîòîì ìàøèíà M 0 âûïîëíèò íå áîëåå, ÷åì p(|w|) + 1 øàãîâ.Îòñþäà îáùåå ÷èñëî øàãîâ íå ïðåâîñõîäèò ïîëèíîìà 2(|w|+1)+p(|w|)+1.Ïðåäëîæåíèå äîêàçàíî. ¤Àíàëîãè÷íîå ïðåäëîæåíèå ìîæíî ñôîðìóëèðîâàòü è äëÿ íåäåòåðìèíèðîâàííûõ ìàøèí Òüþðèíãà (ïðåäëàãàåòñÿ ÷èòàòåëþ â âèäå óïðàæíåíèÿ).
Èòàê, ââèäó ñäåëàííûõ çàìå÷àíèé, â äàëüíåéøåì ìû íå áóäåìóïîìèíàòü, íàä êàêèì àëôàâèòîì ðàñïîçíàåòñÿ òîò èëè èíîé ÿçûê.Îïðåäåëèì òåïåðü âàæíûå êëàññû ÿçûêîâ:P= {L | L ïîëèíîìèàëüíî ðàñïîçíàâàåì íà5.2. Íåäåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà è êëàññû P è NP105äåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà},NP= {L | L ïîëèíîìèàëüíî ðàñïîçíàâàåì íàíåäåòåðìèíèðîâàííûõ ìàøèíàõ Òüþðèíãà}Ïðåäëîæåíèå 5.2.2 Êëàññ P çàìêíóò îòíîñèòåëüíî äîïîëíåíèé.Äîêàçàòåëüñòâî. Ïóñòü ìàøèíà Òüþðèíãà M ïîëèíîìèàëüíî ðàñïîçíàåò ÿçûê L íàä A. Çàìåíèì â ïðîãðàììå äëÿ M âñå ñèìâîëû àëôàâèòà 0 íà 1 è 1 íà 0 ñîîòâåòñòâåííî. Ëåãêî âèäåòü,÷òî ïîëó÷åííàÿ òàêèìîáðàçîì ìàøèíà ïîëèíîìèàëüíî ðàñïîçíàåò ÿçûê A∗ \ L íàä A.
¤Òåîðåìà 5.2.3 Ñóùåñòâóåò âû÷èñëèìûé ÿçûê E , íå ïðèíàäëåæàùèéêëàññó P .Äîêàçàòåëüñòâî. Ïóñòü α = qi aj → qk am S , S ∈ {Λ, L, R} ïðîèçâîëüíàÿ êîìàíäà ìàøèíû Òüþðèíãà. Îáîçíà÷èì ÷åðåç αb ñëîâîq | . . . | a | . . . | → q | . . . | a | . . . | S,| {z } | {z }| {z } | {z }ijkjãäå q , a, |, →, Λ, L, R ôèêñèðîâàííûå ïîïàðíî ðàçëè÷íûå ñèìâîëû.c îáîçíà÷àÄëÿ ìàøèíû Òüþðèíãà M ñ ïðîãðàììîé α1 , . .
. αp ïóñòü Måò ñëîâî αc1 ; αc2 ; . . . ; αcp , ãäå ; íåêîòîðûé ñèìâîë, îòëè÷íûé îò âñåõóïîìÿíóòûõ âûøå ñèìâîëîâ.Ïîëîæèìc | M èç êîíôèãóðàöèè q1 ¤Mc¤E = {Mïðèõîäèò â êîíôèãóðàöèþ âèäà . . . q0 1 . . .cçà íå áîëåå, ÷åì 2|M | øàãîâ.}Ìíîæåñòâî E âû÷èñëèìî. Ýòî ñëåäóåò èç òåçèñà ×¼ð÷à. Äåéñòâèòåëüíî,ñóùåñòâóåò èíòóèòèâíî âû÷èñëèìàÿ ïðîöåäóðà, ïîçâîëÿþùàÿ ïî ïðîèçâîëüíîìó ñëîâó íàä àëôàâèòîì{q, a, |, →, Λ, L, R, ; }c äëÿ êàêîéòî ìàøèíû Òüþîïðåäåëèòü, ÿâëÿåòñÿ ëè îíî ñëîâîì âèäà Mcðèíãà M .
Åñëè M òàêîâî, òî âûïèøåì ïðîãðàììó ìàøèíû M è ïðîâåc¤ â êîíðèì, äåéñòâèòåëüíî ëè îíà ïðèõîäèò èç êîíôèãóðàöèè q1 ¤Mcôèãóðàöèþ âèäà . . . q0 1 . . . çà íå áîëåå, ÷åì 2|M | øàãîâ. Ýòî äàåò íàìàëãîðèòì äëÿ ðàñïîçíàâàíèÿ ýëåìåíòîâ ìíîæåñòâà E .106Ãëàâà 5. Ââåäåíèå â ñëîæíîñòü àëãîðèòìîâÏðåäïîëîæèì, ÷òî E ∈ P . Òîãäà ïî ïðåäëîæåíèþ 5.2.2, ìíîæåñòâîE ïîëèíîìèàëüíî ðàñïîçíàåòñÿ íåêîòîðîé ìàøèíîé Òüþðèíãà M . Ïóñòüp(x) áóäåò ñîîòâåòñòâóþùèì ïîëèíîìîì èç îïðåäåëåíèÿ ïîëèíîìèàëüíîé îãðàíè÷åííîñòè M .
Ìû ìîæåì ñ÷èòàòü, ÷òîcc|) < 2|M | .p(|M(5.1)Äåéñòâèòåëüíî, ïîñêîëüêó p(n)2n → ∞ ïðè n → ∞, íàéäåòñÿ òàêîå íàòóðàëüíîå ÷èñëî n0 , ÷òî ïðè âñåõ n > n0 áóäåò âûïîëíåíî p(n) < 2n . Ñc| ïóäðóãîé ñòîðîíû, ìû ìîæåì íåîãðàíè÷åííî óâåëè÷èâàòü ÷èñëî |Mòåì äîáàâëåíèÿ â ïðîãðàììó M íîâîé êîìàíäû âèäà qi aj → qk am S , ãäåqi íå ñîäåðæèòñÿ ñðåäè ñîñòîÿíèé èñõîäíîé ìàøèíû M , à i ìîæåò áûòüâûáðàíî íåîãðàíè÷åííî áîëüøèì. Ïîñëå òàêîé ìîäèôèêàöèè ìàøèíà áóäåò ðàáîòàòü òî÷íî òàê æå, êàê è èñõîäíàÿ, ïîñêîëüêó îíà íèêîãäà íåïåðåéäåò â ñîñòîÿíèå qi . Çàôèêñèðóåì òàêóþ ïðîãðàììó M , äëÿ êîòîðîéâûïîëíåíî óñëîâèå (5.1).c¤ îñòàÈòàê, ìàøèíà M , áóäó÷è çàïóùåííîé èç êîíôèãóðàöèè q1 ¤Mc|M|c|) < 2íàâëèâàåòñÿ çà íå áîëåå, ÷åì p(|Møàãîâ.
Ýòî îçíà÷àåò, ÷òî ïðèc ê E , óñëîâèå íà ÷èñðàññìîòðåíèè âîïðîñà î ïðèíàäëåæíîñòè ñëîâà Mc ∈ E ýêâèâàëåíòíî òîìó,ëî øàãîâ áóäåò èñòèííûì, è, òàêèì îáðàçîì, Mc¤ îñòàíàâ÷òî ìàøèíà M , áóäó÷è çàïóùåííîé èç êîíôèãóðàöèè q1 ¤Mëèâàåòñÿ â êîíôèãóðàöèè âèäà . . . q0 1 . . .Òåïåðü ïîñêîëüêó M ðàñïîçíàåò E , óñëîâèå, ÷òîc¤ îñòàìàøèíà M , áóäó÷è çàïóùåííîé èç êîíôèãóðàöèè q1 ¤Míàâëèâàåòñÿ â êîíôèãóðàöèè âèäà . . . q0 1 . . .c∈ýêâèâàëåíòíî óñëîâèþ M/ E , êîòîðîå â ñâîþ î÷åðåäü ââèäó îïðåäåëåíèÿ E ýêâèâàëåíòíî óñëîâèþíåâåðíî, ÷òîc¤ îñòàíàâëèM , áóäó÷è çàïóùåííîé èç êîíôèãóðàöèè q1 ¤Mâàåòñÿ â êîíôèãóðàöèè âèäà . . . q0 1 . .
.Òàêèì îáðàçîì, äâà âûïèñàííûõ íàìè êóðñèâîì óñëîâèÿ ýêâèâàëåíòíû ìåæäó ñîáîé è ÿâëÿþòñÿ îòðèöàíèÿìè äðóã äðóãà. Ïðîòèâîðå÷èå.Çíà÷èò íàøå ïðåäïîëîæåíèå î òîì, ÷òî E ∈ P ÿâëÿåòñÿ íåâåðíûì. ¤5.3 Ïîíÿòèå îá NPïîëíûõ ïðîáëåìàõÍàïîìíèì, ÷òî ìíîæåñòâî ñëîâ A ìîæíî ðàññìàòðèâàòü, êàê ïðîáëåìó èëè çàäà÷ó ðàñïîçíàâàíèÿ ýëåìåíòîâ ýòîãî ìíîæåñòâà. Ïîýòîìó ìû5.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
