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

Ïðè óñëîâèÿõ ëåììû ñóùåñòâóåò êîíñòàíòà c > 0Pnòàêàÿ, ÷òîi=1 li > cn log2 n.Äîêàçàòåëüñòâî. Ëåììà î÷åâèäíî âûïîëíÿåòñÿ ïðè r = 1. Ïóñòür > 2. ×èñëî âñåõ ñëîâ äëèíû ìåíüøåé, ÷åì b 21 logr nc íå ïðåâîñõîäèò√√11rb 2 logr nc 6 r 2 logr n = n. Ïîýòîìó ñðåäè ñëîâ b̄i íå ìåíåå, ÷åì n − nñëîâ, èìåþò äëèíó íå ìåíüøå ÷åì b 12 logr nc. ÏîýòîìóËåììà 4.10. ÏóñòünXli > (n −i=1√1n)b logr nc > cn log2 n2äëÿ íåêîòîðîé êîíñòàíòû c.Ëåììàn1 , n2 , . . . , nk , .

. .4.12.Ïóñòü÷èñëîâàÿïîñëåäîâàòåëüíîñòüíå îãðàíè÷åíà ñâåðõó. Òîãäà èç íåå ìîæíî âûäåëèòüni1 , ni2 , . . . òàêóþ, ÷òî äëÿ ëþáîãî s è âñåõ1 6 j < is âûïîëíÿåòñÿ nj < nis .Äîêàçàòåëüñòâî. Ïåðâûì ýëåìåíòîì ïîäïîñëåäîâàòåëüíîñòè âîçüìåì n1 . Ïóñòü óæå âûáðàíû ni1 , ni2 , .

. . , nir . Òîãäà, ïðîñìàòðèâàÿ ýëåìåíòû ïî ïîðÿäêó ïîñëå nir , â êà÷åñòâå î÷åðåäíîãî ýëåìåíòà âûáèðàåìïåðâûé ýëåìåíò nir+1 , áîëüøèé, ÷åì nir . Ïîñêîëüêó nir+1 > nir , à âñåýëåìåíòû ìåæäó nir è nir+1 íå ïðåâîñõîäÿò nir , òî âñå îíè ìåíüøå, ÷åìnir+1 . Ïîýòîìó, åñëè âñå ýëåìåíòû nj èñõîäíîé ïîñëåäîâàòåëüíîñòè ñ j =1, 2, . . . , ir − 1 ìåíüøå, ÷åì nir , òî âñå ýëåìåíòû nj ñ j = 1, 2, .

. . , ir+1 − 1ìåíüøå, ÷åì nir+1 . Òàêèì îáðàçîì ïî èíäóêöèè ïðîâåðÿåòñÿ òðåáóåìîåïîäïîñëåäîâàòåëüíîñòü44ñâîéñòâî. Òî, ÷òî nir+1 ñóùåñòâóåò, ñëåäóåò èç íåîãðàíè÷åííîñòè èñõîäíîéïîñëåäîâàòåëüíîñòè.Îáîçíà÷èì ÷åðåç ξM (ā|b̄) ñëåä ïðè ðàáîòå ìàøèíû Òüþðèíãà M íàñëîâå āb̄ â òî÷êå, ðàçäåëÿþùåé ā è b̄.Ëåììà 4.13.

Ïóñòüā, b̄, c̄ íåêîòîðûå ñëîâà è ïóñòü ξM (ā|b̄c̄) =ξM (āb̄|c̄). Òîãäà ïðè ðàáîòå M íà ñëîâå āc̄ ñëåâà è ñïðàâà îò òî÷êè, ðàçäåëÿþùåé ā è c̄, ìàøèíà ðàáîòàåò òàê æå, êàê íà ñîîòâåòñòâóþùèõ÷àñòÿõ ïðè ðàáîòå íà āb̄c̄.Óòâåðæäåíèå ýòîé ëåììû âûòåêàåò èç ëåììû 4.1.Ïðè ðàáîòå ìàøèíû Òüþðèíãà íà âõîäíîì ñëîâå ā = a1 a2 .

. . anòî÷êîé i áóäåì íàçûâàòü òî÷êó ïîñëå ÿ÷åéêè, â êîòîðîé íàõîäèòñÿ ai .Òåîðåìà 4.9. Ïóñòü ìàøèíà Òüþðèíãà M ðàñïîçíàåò ÿçûê L ⊆∗A . Ïóñòü dM (n) ìàêñèìàëüíàÿ äëèíà ñëåäîâ â òî÷êàõ 1, 2, . . . , n∗ïðè ðàáîòå ìàøèíû M íà âñåõ ñëîâàõ ā ∈ A äëèíû n, à TM (n) ìàêñèìàëüíîå âðåìÿ âû÷èñëåíèÿ (÷èñëî øàãîâ) ìàøèíû M íà ñëîâàõ∗äëèíû n èç A . Òîãäà åñëè âûïîëíÿåòñÿ õîòÿ áû îäíî èç äâóõ óñëîâèé:à) dM (n) = o(log n); á) TM (n) = o(n log n), òî L ðåãóëÿðíûé ÿçûê.Äîêàçàòåëüñòâî òåîðåìû (îò ïðîòèâíîãî). Äîïóñòèì, ÷òî L íåðåãóëÿðíûé ÿçûê. Òîãäà ïî òåîðåìå 4.8 dM (n) íåîãðàíè÷åííàÿ ïîñëåäîâàòåëüíîñòü. Ïî ëåììå 4.12 èç íåå ìîæíî âûäåëèòü ïîäïîñëåäîâàòåëüíîñòün1 , n2 , .

. . òàêóþ, ÷òîdM (n) < dM (ni )(4.1)äëÿ âñåõ n < ni (i = 1, 2, . . .).Ëåììà 4.14. Ïóñòün1 , n2 , . . . óäîâëåòâîðÿþò (4.1) è āi ñëîâîäëèíû ni , íà êîòîðîì äîñòèãàåòñÿ dM (ni ). Òîãäà ïðè ðàáîòå M íà ñëîâåāi îäèí è òîò æå ñëåä â òî÷êàõ 1, 2, . . . , ni íå ìîæåò ïîâòîðÿòüñÿáîëåå ÷åì 2 ðàçà.¯ =Ïðåäïîëîæèì, ÷òî āi = āb̄c̄d¯ è ξM (ā|b̄c̄d)¯ = ξM (āb̄c̄|d)¯ , ãäå ā, b̄, c̄ íå ïóñòûå ñëîâà. Ïðè ðàáîòå MξM (āb̄|c̄d)íà ñëîâå āi åñòü ñëåäû äëèíû dM (ni ). Ïî êðàéíåé ìåðå îäèí òàêîé ñëåäëèáî íå ëåæèò âíóòðè b̄, ëèáî íå ëåæèò âíóòðè c̄. Òîãäà ïî ëåììå 4.13îí ñîõðàíèòñÿ ïðè ðàáîòå M ëèáî íà ñëîâå āc̄d¯, ëèáî íà ñëîâå āb̄d¯, íîýòî ïðîòèâîðå÷èò òîìó, ÷òî dM (n) < dM (ni ) äëÿ âñåõ n < ni .

Ëåììàäîêàçàíà.Èç ýòîé ëåììû ïîëó÷àåì, ÷òî ïðè ðàáîòå M íà ñëîâå āi â òî÷êàõ1, 2, . . . , ni èìååòñÿ íå ìåíåå n2i ðàçíûõ ñëåäîâ. Òîãäà ïî ëåììàì 4.10 è4.11 dM (ni ) > c log2 n2i , è ñóììà äëèí ýòèõ ðàçíûõ ñëåäîâ, à çíà÷èò èâðåìÿ ðàáîòû ìàøèíû M , íå ìåíüøå, ÷åì cni log2 n2i , ãäå c íåêîòîðàÿêîíñòàíòà. Åñëè âûïîëíåíî óñëîâèå à) èëè á) èç òåîðåìû 4.9, òî ïîëóÄîêàçàòåëüñòâî.45÷àåì ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, îò ïðîòèâíîãî, ïîëó÷àåì, ÷òî ïðèâûïîëíåíèè óñëîâèÿ à) èëè á) ÿçûê L ðåãóëÿðåí. Òåîðåìà 4.9 äîêàçàíà.Ñëåäñòâèå. ÅñëèdM (n) = o(log n)èëèTM (n) = o(n log n),N , ðàñïîçíàþùàÿdN (n) = 1, TN (n) = n + 1.ñóùåñòâóåò ìàøèíà Òüþðèíãà (àâòîìàò)ÿçûêL,äëÿ êîòîðîé4.5.

ÊëàññûPèòîòîò æåNPÏóñòü àëãîðèòì îñóùåñòâëÿåò ïðåîáðàçîâàíèå ϕ :A → B ñëîâ â àëôàâèòå A â ñëîâà â àëôàâèòå B . Òîãäà ýòîò àëãîðèòì íàçûâàåòñÿ ïîëèíîìèàëüíûì (èëè èìåþùèì ïîëèíîìèàëüíóþñëîæíîñòü), åñëè ñóùåñòâóåò ïîëèíîì p(n) òàêîé, ÷òî äëÿ ëþáîãî íàòóðàëüíîãî n âðåìÿ ðàáîòû àëãîðèòìà íà ëþáîì âõîäíîì ñëîâå äëèíû níå ïðåâîñõîäèò p(n). (Ïðè ýòîì ìîæíî ñ÷èòàòü, ÷òî âñå êîýôôèöèåíòûâ p(n) íåîòðèöàòåëüíû, òî åñòü p(n) âîçðàñòàþùàÿ ôóíêöèÿ.)Îïðåäåëåíèå. Çàäà÷åé ðàñïîçíàâàíèÿ íàçûâàåòñÿ ëþáîå îòîáðàæåíèå ϕ : A∗ → {äà, íåò }.Ñ ëþáîé çàäà÷åé ðàñïîçíàâàíèÿ ϕ ìîæíî ñâÿçàòü ÿçûê Lϕ ⊆ A∗ñëåäóþùèì îáðàçîì: ā ∈ Lϕ ⇐⇒ ϕ : ā → äà. È îáðàòíî, ëþáîé ÿçûêìîæíî ðàññìàòðèâàòü êàê çàäà÷ó ðàñïîçíàâàíèÿ.Îïðåäåëåíèå. Êëàññ P ýòî êëàññ âñåõ ÿçûêîâ (çàäà÷ ðàñïîçíàâàíèÿ), äëÿ êàæäîãî èç êîòîðûõ ñóùåñòâóåò ðàñïîçíàþùèé àëãîðèòì ñïîëèíîìèàëüíîé ñëîæíîñòüþ.Îïðåäåëåíèå.

Áóäåì ãîâîðèòü, ÷òî ÿçûê L1 ⊆ A∗ ïîëèíîìèàëüíîñâîäèòñÿ ê ÿçûêó L2 ⊆ B ∗ , åñëè ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì(íàïðèìåð, ìàøèíà Òüþðèíãà) ϕ : A∗ → B ∗ , òàêîé ÷òî ϕ(ā) ∈ L2 ⇐⇒ā ∈ L1 .Îïðåäåëåíèå.∗∗L1 ⊆ A∗ , L2 ⊆ B ∗ , L2 ∈ P è L1 ïîëèíîìèàëüíî ñâîäèòñÿ ê L2 . Òîãäà L1 ∈ P .Äîêàçàòåëüñòâî. Ïî óñëîâèþ ñóùåñòâóþò ìàøèíû Òüþðèíãà M1è M2 òàêèå, ÷òî M1 ïîëèíîìèàëüíî ñâîäèò L1 ê L2 , à M2 ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ ðàñïîçíàåò L2 .

Ðàññìîòðèì ìàøèíó ÒüþðèíãàM = M2 (M1 ). Òîãäà M : A∗ → {äà, íåò }, ïðè÷åì äëÿ ëþáîãî ñëîâàā ∈ A∗ èìååìÒåîðåìà 4.10. ÏóñòüM (ā) = äà ⇐⇒ M2 (M1 (ā)) = äà ⇐⇒ M1 (ā) ∈ L2 ⇐⇒ ā ∈ L1 ,òî åñòü M ðàñïîçíàåò ÿçûê L1 . Ïî óñëîâèþ âðåìÿ ðàáîòû (÷èñëî øàãîâ)ìàøèí M1 è M2 íà âõîäíûõ ñëîâàõ äëèíû n íå ïðåâîñõîäèò p1 (n) è p2 (n),ãäå p1 , p2 ïîëèíîìû. Òîãäà âðåìÿ ðàáîòû M íà ñëîâå ā äëèíû n íåïðåâîñõîäèò p1 (n) + p2 (|M1 (ā)|), ãäå |M1 (ā)| äëèíà ñëîâà M1 (ā). Òàê46êàê ìàøèíà Òüþðèíãà M1 íà êàæäîì øàãå ìîæåò óâåëè÷èâàòü äëèíóñëîâà íå áîëåå ÷åì íà 1, òî |M1 (ā)| 6 n + p1 (n) è âðåìÿ ðàáîòû M íà āíå ïðåâîñõîäèò p1 (n) + p2 (n + p1 (n)) = p3 (n), ãäå p3 ïîëèíîì.

(Çäåñüñ÷èòàåòñÿ, ÷òî âñå êîýôôèöèåíòû â p2 íåîòðèöàòåëüíû è, ñëåäîâàòåëüíî,p2 (n) íåóáûâàþùàÿ ôóíêöèÿ). Òàêèì îáðàçîì M ðàñïîçíàåò ÿçûê L1ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ. Òåîðåìà äîêàçàíà.Ýòà òåîðåìà ïîçâîëÿåò ïîëó÷àòü ïîëèíîìèàëüíûå àëãîðèòìû äëÿîäíèõ çàäà÷ ðàñïîçíàâàíèÿ èç èìåþùèõñÿ ïîëèíîìèàëüíûõ àëãîðèòìîâäëÿ äðóãèõ çàäà÷ ïðîñòî ïóòåì ïîëèíîìèàëüíîãî ñâåäåíèÿ îäíèõ çàäà÷ê äðóãèì.Ê ñîæàëåíèþ, äëÿ áîëüøèíñòâà çàäà÷, âîçíèêàþùèõ íà ïðàêòèêå,ïîêà íå èçâåñòíî, âõîäÿò ëè îíè â êëàññ P , íî ïî÷òè âñå òàêèå çàäà÷èîêàçûâàþòñÿ â äðóãîì êëàññå, êîòîðûé îáîçíà÷àþò N P .Îïðåäåëåíèå.

ßçûê L ⊆ A∗ (çàäà÷à ðàñïîçíàâàíèÿ) âõîäèò âêëàññ N P , åñëè è òîëüêî åñëè ñóùåñòâóþò àëôàâèò B , ïîëèíîì q(n) èïðåäèêàò Q(x, y) : A∗ × B ∗ → {èñòèíà, ëîæü } òàêèå, ÷òî Q(x, y) ∈ Pè äëÿ ëþáîãî ñëîâà ā ∈ A∗ âûïîëíÿåòñÿ:ā ∈ L ⇐⇒ ∃b̄ ∈ B ∗ (|b̄| 6 q(|ā|)&Q(ā, b̄))(çäåñü |ā| è |b̄| äëèíà ñëîâ ā è b̄).Ñëîâî b̄ íàçûâàþò ñåðòèôèêàòîì äëÿ ñëîâà ā, à àëãîðèòì, ðàñïîçíàþùèé ïðåäèêàò Q(ā, b̄), àëãîðèòìîì ïðîâåðêè ñåðòèôèêàòà. Òàêèìîáðàçîì, åñëè ā ∈ L (â çàäà÷å ðàñïîçíàâàíèÿ äëÿ âõîäà ā îòâåò äà), òîäîëæíî ñóùåñòâîâàòü áûñòðîå ïîäòâåðæäåíèå äëÿ ýòîãî, òî åñòü äîëæåíñóùåñòâîâàòü ïîäòâåðæäàþùèé ýòî ñåðòèôèêàò b̄ (íåáîëüøîé äëèíû) èáûñòðûé ñïîñîá ïîäòâåðäèòü, ÷òî ýòî äåéñòâèòåëüíî ïîäõîäÿùèé ñåðòèôèêàò.

Åñëè æå ā ∈/ L, òî òàêîãî b̄ ïðîñòî íå äîëæíî ñóùåñòâîâàòü. Òàêèìîáðàçîì, îòâåòû äà è íåò çäåñü íå ñèììåòðè÷íû. Çàìåòèì òàêæå, ÷òîäëÿ ñëó÷àÿ ā ∈ L ëèøü óòâåðæäàåòñÿ ñóùåñòâîâàíèå ñåðòèôèêàòà b̄, íîíè÷åãî íå ãîâîðèòñÿ î ñëîæíîñòè åãî íàõîæäåíèÿ (åñëè â B èìååòñÿ ráóêâ è |ā| = n, òî |b̄| 6 q(n) è ÷èñëî òàêèõ ñëîâ b̄ íå ìåíüøå, ÷åì rq(n) ,òî åñòü ýêñïîíåíöèàëüíî çàâèñèò îò n).Ðàññìîòðèì ïðèìåðû ÿçûêîâ èç N P .ÊËÈÊÀ. Âõîä: ëþáîé íåîðèåíòèðîâàííûé ãðàô G [?] è íàòóðàëüíîå ÷èñëî k .Âîïðîñ: Ñóùåñòâóåò ëè â ãðàôå G êëèêà ðàçìåðà k , òî åñòü kâåðøèí òàêèõ, ÷òî ëþáàÿ ïàðà èç íèõ ñîåäèíåíà ðåáðîì?Áîëåå ñòðîãî, ìû äîëæíû çàäàòü âõîäíîé àëôàâèò A è ñïîñîáïðåäñòàâëåíèÿ ãðàôîâ è ÷èñëà k â ýòîì àëôàâèòå.

Ìîæíî, íàïðèìåð,ñ÷èòàòü, ÷òî A = {0, 1, ; } è ãðàô çàäàåòñÿ ìàòðèöåé ñìåæíîñòè (èç 0 è471), êîòîðàÿ çàòåì âûïèñûâàåòñÿ â îäíî ñëîâî ïîäðÿä ïî ñòðîêàì ìàòðèöûñ ðàçäåëèòåëåì ; ìåæäó ñòðîêàìè ìàòðèöû.  êîíöå ïîñëå ; çàïèñûâàåòñÿk â äâîè÷íîé ñèñòåìå.∈ NP .Äîêàçàòåëüñòâî.  êà÷åñòâå ñåðòèôèêàòà b̄ äëÿ âõîäà ā áóäåìáðàòü ñïèñîê èç íîìåðîâ k âåðøèí, ñîñòàâëÿþùèõ êëèêó. Î÷åâèäíî,|b̄| 6 q(|ā|), ãäå q íåêîòîðûé ïîëèíîì.

Ïðåäèêàò Q áóäåò îáîçíà÷àòü,÷òî äàííûå âåðøèíû çàäàþò êëèêó â äàííîì ãðàôå è ýòèõ âåðøèí ðîâíîk . Äëÿ ðàñïîçíàâàíèÿ ñïðàâåäëèâîñòè òàêîãî ñâîéñòâà Q ëåãêî ïîñòðîèòüàëãîðèòì ñî ñëîæíîñòüþ, íå ïðåâîñõîäÿùåé ïîëèíîìà îò ñóììàðíîéäëèíû êîäà ãðàôà ā è ñåðòèôèêàòà b̄.ÃÀÌÈËÜÒÎÍΠÖÈÊË (ÃÖ). Âõîä: ëþáîé íåîðèåíòèðîâàííûé ãðàô G.Âîïðîñ: Ñóùåñòâóåò ëè â ãðàôå G ãàìèëüòîíîâ öèêë, òî åñòü öèêë,ïðîõîäÿùèé ÷åðåç êàæäóþ âåðøèíó ðîâíî 1 ðàç?Óòâåðæäåíèå. ÃÖ ∈ N P .Äîêàçàòåëüñòâî. Ñåðòèôèêàòîì çäåñü ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü èç âåðøèí v1 , v2 , . .

. , vm . Ïðåäèêàò Q âûðàæàåò óòâåðæäåíèå, ÷òîâ ýòîé ïîñëåäîâàòåëüíîñòè âñå âåðøèíû ãðàôà âñòðå÷àþòñÿ ðîâíî 1 ðàçè â ãðàôå åñòü ðåáðà (vi , vi+1 ) äëÿ âñåõ i = 1, 2, . . . , m − 1, à òàêæåðåáðî (vm , v1 ). Äëÿ ðàñïîçíàâàíèÿ ñïðàâåäëèâîñòè òàêîãî ñâîéñòâà Qëåãêî ïîñòðîèòü àëãîðèòì ñî ñëîæíîñòüþ, íå ïðåâîñõîäÿùåé ïîëèíîìàîò ñóììàðíîé äëèíû êîäà ãðàôà ā è ñåðòèôèêàòà b̄.Îïðåäåëåíèå.

Êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÊÍÔ) íàçûâàåòñÿ áóëåâà ôîðìóëà âèäà F (x1 , . . . , xm ) = D1 &D2 & . . . &Dk , ãäå äëÿêàæäîãî j : Dj = tj,1 ∨ tj,2 ∨ . . . ∨ tj,nj è âñå tj,k ëèáî ïåðåìåííûå,ëèáî îòðèöàíèÿ ïåðåìåííûõ, ïðè÷åì êàæäàÿ ïåðåìåííàÿ âñòðå÷àåòñÿ âîäíîì Dj íå áîëåå îäíîãî ðàçà. Âûðàæåíèÿ Dj íàçûâàþò äèçúþíêòàìè,à ñîñòàâëÿþùèå èõ tj,k ëèòåðàëàìè.ÂÛÏÎËÍÈÌÎÑÒÜ (ÂÛÏ).

Âõîä: ëþáàÿ ôîðìóëà F â âèäåÊÍÔ.Âîïðîñ: ñóùåñòâóåò ëè íàáîð ïåðåìåííûõ (α1 , . . . , αm ), íà êîòîðîìF (α1 , . . . , αm ) = 1 (âûïîëíèìà ëè F )?Óòâåðæäåíèå. ÂÛÏ ∈ N P .Äîêàçàòåëüñòâî. Ñåðòèôèêàòîì äëÿ âõîäà F ÿâëÿåòñÿ íàáîð(α1 , . . . , αm ), íà êîòîðîì F (α1 , . . . , αm ) = 1. Ïðåäèêàò Q âûðàæàåò òîòôàêò, ÷òî äàííàÿ ôîðìóëà F íà äàííîì íàáîðå (α1 , . . . , αm ) äåéñòâèòåëüíî ïðèíèìàåò çíà÷åíèå 1. Äëÿ ðàñïîçíàâàíèÿ ñïðàâåäëèâîñòè òàêîãîñâîéñòâà Q ëåãêî ïîñòðîèòü àëãîðèòì ñî ñëîæíîñòüþ, íå ïðåâîñõîäÿÓòâåðæäåíèå.

ÊËÈÊÀ48ùåé ïîëèíîìà îò ñóììàðíîé äëèíû êîäà ôîðìóëû F è êîäà íàáîðà(α1 , . . . , αm ).Åùå ðàç îáñóäèì âîïðîñ î ïðåäñòàâëåíèè âõîäíûõ äàííûõ. Ìûíå ìîæåì, íàïðèìåð, âêëþ÷èòü â àëôàâèò A ïðîèçâîëüíûå ïåðåìåííûå, òàê êàê èõ áåñêîíå÷íîå ÷èñëî, à ëþáàÿ ìàøèíà Òüþðèíãà ðàáîòàåò ëèøü ñ êîíå÷íûìè àëôàâèòàìè. Îäíàêî äîñòàòî÷íî âçÿòü àëôàâèòA = {x, 0, 1, &, ∨, e, (, )} è ïåðåìåííóþ xi çàïèñûâàòü êàê x ñ èäóùèìäàëåå ÷èñëîì i, ïðåäñòàâëåííûì â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ.