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

. . , vi−1 , vi , vi+1 , . . . , v1 . Ïóñòü âûäåëåííîå vi âñòðå÷àåòñÿ â öèêëå ðàíüøå. Òîãäà çàìåíèì ïîñëåäîâàòåëüíîñòü ðåáåð (vi−1 , vi ), (vi , vi+1 )íà ðåáðî (vi−1 , vi+1 ) â èñõîäíîì ãðàôå. Ïðè ýòîì ïîëó÷èì îïÿòü öèêë,ïðîõîäÿùèé ïî âñåì âåðøèíàì. Ïîñêîëüêó âåñà óäîâëåòâîðÿþò íåðàâåíñòâó òðåóãîëüíèêà, òî ñóììàðíûé âåñ öèêëà ïðè ýòîì íå âîçðàñòåò.Åñëè â ïîëó÷åííîì öèêëå ñíîâà åñòü ïîâòîðÿþùèåñÿ âåðøèíó, òî îïÿòüâûáðîñèì îäíó âåðøèíó, îñóùåñòâèâ ñïðÿìëåíèå. Ýòîò ïðîöåññ áóäåìïîâòîðÿòü äî òåõ ïîð, ïîêà íå ïîëó÷èòñÿ öèêë C2 áåç ïîâòîðÿþùèõñÿ71âåðøèí. Òîãäà öèêë C2 áóäåò ãàìèëüòîíîâûì è d(C2 ) 6 d(C1 ) 6 2Fîïò .

Âðåçóëüòàòå ìû ïîëó÷àåì àëãîðèòì äëÿ ÇÊÍÒ ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ, êîòîðûé ÿâëÿåòñÿ 1-ïðèáëèæåííûì.5.4. Çàäà÷à î ìàêñèìàëüíîé êëèêåÂûøå áûëî äîêàçàíî, ÷òî çàäà÷à ÊËÈÊÀ ÿâëÿåòñÿ N P -ïîëíîé.Ðàññìîòðèì òåïåðü ñëåäóþùóþ çàäà÷ó ÌÊ.Âõîä: íåîðèåíòèðîâàííûé ãðàô G.Òðåáóåòñÿ: íàéòè êàêóþ-íèáóäü ìàêñèìàëüíóþ ïî ÷èñëó âåðøèíêëèêó.Òåîðåìà 5.9. Çàäà÷à î ìàêñèìàëüíîé êëèêå (ÌÊ) ÿâëÿåòñÿN P -òðóäíîé.Ïóñòü A àëãîðèòì ñ ïîëèíîìèàëüíîé ñëîæíîñòüþ äëÿ ÌÊ, è ïóñòü ïàðà (G, k) âõîä äëÿ çàäà÷è ÊËÈÊÀ. Ïðèìåíèìê G àëãîðèòì A è íàéäåì ìîùíîñòü m ïîëó÷åííîé ìàêñèìàëüíîé êëèêèâ G. Åñëè m > k , òî äëÿ ïàðû (G, k) â çàäà÷å ÊËÈÊÀ îòâåò äà, èíà÷åîòâåò íåò. Ïîëó÷àåì ïîëèíîìèàëüíûé àëãîðèòì äëÿ çàäà÷è ÊËÈÊÀ.Òàê êàê ÊËÈÊÀ N P -ïîëíà, òî èç ñóùåñòâîâàíèÿ ïîëèíîìèàëüíîãî àëãîðèòìà äëÿ ÌÊ ñëåäóåò ñóùåñòâîâàíèå ïîëèíîìèàëüíîãî àëãîðèòìà äëÿâñåõ çàäà÷ èç N P , òî åñòü ÌÊ N P -òðóäíà.Ïðåæäå, ÷åì èññëåäîâàòü ïðèáëèæåííûå àëãîðèòìû äëÿ ÌÊ, äîêàæåì ëåììó.Îïðåäåëåíèå.

Ïóñòü G = (V, E) íåîðèåíòèðîâàííûé ãðàô.Îïðåäåëèì ãðàô G2 = (V 2 , E 2 ) êàê ãðàô ñ ìíîæåñòâîì âåðøèí V 2 = V ×V = {(u, v)|u ∈ V, v ∈ V } è ìíîæåñòâîì ðåáåð E 2 = {(u1 , v1 ), (u2 , v2 )},ãäå ëèáî u1 = u2 è (v1 , v2 ) ∈ E , ëèáî (u1 , u2 ) ∈ E .Äîêàçàòåëüñòâî.k , òî â G2 åñòü êëèêà2222ðàçìåðà k . Åñëè â G åñòü êëèêà ðàçìåðà m, ãäå (k − 1) < m 6 k , òî22â G åñòü êëèêà ðàçìåðà k è â G åñòü êëèêà ðàçìåðà k .Äîêàçàòåëüñòâî. Ïóñòü â G åñòü êëèêà C = {v1 , v2 , . . .

, vk }. Òîãäàèç îïðåäåëåíèÿ ëåãêî ïðîâåðèòü, ÷òî C 2 = {(u, v)|u ∈ C, v ∈ C} êëèêà â G2 ðàçìåðà k 2 . Îáðàòíî, ïóñòü â G2 åñòü êëèêà D ðàçìåðà m.Âåðøèíàìè â D ÿâëÿþòñÿ ïàðû (u, v) ∈ V 2 . Ïóñòü V = {v1 , v2 , . . . , vn } èïóñòü Di ìíîæåñòâî âåðøèí (u, v) èç D, ó êîòîðûõ u = vi . Ïî îïðåäåëåíèþ ãðàôà G2 âåðøèíû (u, v 0 ) è (u, v 00 ) ñìåæíû â G2 òîãäà è òîëüêîòîãäà, êîãäà (v 0 , v 00 ) ∈ E . Ïîýòîìó âòîðûå êîîðäèíàòû âñåõ âåðøèí èç Diîáðàçóþò êëèêó â G. Åñëè |Di | > k õîòÿ áû äëÿ îäíîãî i, òî ïîëó÷àåìâ G êëèêó ðàçìåðà k .

 ïðîòèâíîì ñëó÷àå |Di | 6 k − 1 äëÿ âñåõ i è,ñëåäîâàòåëüíî, ÷èñëî íåïóñòûõ Di íå ìåíåå k , òàê êàê m > (k − 1)2 .Ëåììà 5.2. Åñëè âGåñòü êëèêà ðàçìåðà72Âûáåðåì â êàæäîì íåïóñòîì Di ëþáóþ âåðøèíó (vi , vdi ). Òàê êàê âñåýòè âåðøèíû ïðèíàäëåæàò îäíîé êëèêå D, òî âñå îíè ñìåæíû. Òàê êàêvi 6= vj ïðè i 6= j , òî (vi , vj ) ∈ E äëÿ âñåõ ïåðâûõ êîîðäèíàò âûáðàííûõâåðøèí ïî îïðåäåëåíèþ ãðàôà G2 . Ïîñêîëüêó ÷èñëî âûáðàííûõ âåðøèím > k , òî ïîëó÷àåì êëèêó â G ðàçìåðà k . Ïîñëåäíåå óòâåðæäåíèå ëåììûñëåäóåò èç ïåðâîãî.Ñëåäñòâèå 1. Ìîùíîñòü ìàêñèìàëüíîé êëèêè âäëÿ íåêîòîðîãî íàòóðàëüíîãîG2èìååò âèäk2k.Ñëåäñòâèå 2.

Ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì, êîòîðûéïî çàäàííîé êëèêåDìîùíîñòèmâ ãðàôåG2 ,ãäå(k − 1)2 < m 6 k 2 ,C ìîùíîñòè k â ãðàôå G.Ïóñòü màëã è mmax ìîùíîñòü êëèêè, êîòîðàÿ ñòðîèòñÿ íåêîòîðûìàëãîðèòìîì, è ìîùíîñòü ìàêñèìàëüíîé êëèêè äëÿ äàííîãî âõîäà G.Òîãäà màëã 6 mmax èñòðîèò êëèêóε=|màëã − mmax |6 1.mmaxÒåîðåìà. Åñëè äëÿ çàäà÷è ÌÊ ñóùåñòâóåò ïîëèíîìèàëüíûéε-ïðèáëèæåííûéàëãîðèòì äëÿ íåêîòîðîãîñóùåñòâóåò ïîëèíîìèàëüíûé0 < ε < 1,ε-ïðèáëèæåííûéòî äëÿ ÌÊàëãîðèòì äëÿ âñåõ0<ε < 1.Ïóñòü äëÿ çàäà÷è ÌÊ äëÿ íåêîòîðîãî 0 < ε < 1èìååòñÿ ïîëèíîìèàëüíûé ε-ïðèáëèæåííûé àëãîðèòì Aε , è ïóñòü 0 < δ <r1.

Âûáåðåì íàòóðàëüíîå r òàê, ÷òî (1 − δ)2 < 1 − ε. Òàêîå r ñóùåñòâóåò,òàê êàê 1 − δ < 1. Ðàññìîòðèì ñëåäóþùèé àëãîðèòì B . Ïóñòü íà âõîärïîñòóïàåò ãðàô G. Ñòðîèì ïîñëåäîâàòåëüíî G2 , G4 , . . . , G2 . Ïðèìåíÿåìrrê G2 àëãîðèòì Aε . Ïîëó÷àåì êëèêó Dr â G2 . Ïî êëèêå Dr ñòðîèìr−1êëèêó Dr−1 â G2 òàê, êàê â äîêàçàòåëüñòâå ëåììû. Ïî Dr−1 àíàëîãè÷íîr−2ñòðîèì êëèêó Dr−2 â G2è ò.ä. äî êëèêè D0 â G. Êëèêó D0 âûäàåìâ îòâåò.

Òàê êàê r ôèêñèðîâàíî, òî àëãîðèòì B ïîëèíîìèàëåí (ñì.ñëåäñòâèå 2). Äîêàæåì, ÷òî îí ÿâëÿåòñÿ δ -ïðèáëèæåííûì.Ïóñòü ìîùíîñòü ìàêñèìàëüíîé êëèêè â G ðàâíà k . Òîãäà ìîùíîñòürrìàêñèìàëüíîé êëèêè â G2 ðàâíà k 2 ïî ëåììå 5.2 (ñì. ñëåäñòâèå 1).2rÒàê êàê àëãîðèòì Apε ÿâëÿåòñÿ ε-ïðèáëèæåííûì, òî |Dr | > k (1 − ε).Ïîñêîëüêó |Di−1 | > |Di | äëÿ âñåõ i, òîÄîêàçàòåëüñòâî.|D0 | > k√2r1 − ε > k(1 − δ).Ñëåäîâàòåëüíî, àëãîðèòì B ÿâëÿåòñÿ δ -ïðèáëèæåííûì. Òåîðåìà äîêàçàíà.736. ÊëàññûP SP ACEèDLOGÊëàññû P è N P îïðåäåëÿëèñü ÷åðåç èñïîëüçóåìîå àëãîðèòìîìâðåìÿ ðàáîòû.

Äðóãèå êëàññû ìû ìîæåì ïîëó÷èòü, åñëè áóäåì ðàññìàòðèâàòü èñïîëüçóåìóþ ïàìÿòü.Îïðåäåëåíèå. Êëàññ PSPACE îïðåäåëÿåòñÿ êàê êëàññ âñåõ çàäà÷ðàñïîçíàâàíèÿ (ÿçûêîâ), äëÿ êîòîðûõ ñóùåñòâóåò àëãîðèòì, èñïîëüçóþùèé ïàìÿòü (íàïðèìåð, ÷èñëî ÿ÷ååê ìàøèíû Òüþðèíãà), íå ïðåâîñõîäÿùóþ p(n), ãäå n äëèíà âõîäà è p ïðîèçâîëüíûé (ôèêñèðîâàííûéäëÿ äàííîé çàäà÷è) ïîëèíîì.Î÷åâèäíî, ÷òî P ⊆ P SP ACE .N P ⊆ P SP ACE .Äîêàçàòåëüñòâî. Ïóñòü çàäà÷à ðàñïîçíàâàíèÿ R(x) ∈ N P .

Ïîîïðåäåëåíèþ êëàññà N P R(x) ïðåäñòàâèìî â âèäå:Òåîðåìà 6.1.R(x) = ∃y(|y| 6 p1 (|x|)&Q(x, y)),ãäå |x| è |y| äëèíà ñëîâ x è y , p1 íåêîòîðûé ïîëèíîì è ïðåäèêàòQ(x, y) ∈ P . Ïîêàæåì, ÷òî äëÿ âû÷èñëåíèÿ R(x) ñóùåñòâóåò àëãîðèòìñ ïîëèíîìèàëüíîé ïàìÿòüþ. Ïóñòü äàí âõîä x. Âû÷èñëÿåì äëèíó nñëîâà x. Âû÷èñëÿåì p1 (n) è îòìå÷àåì â ïàìÿòè çîíó p1 (n), íà êîòîðîéïåðåáèðàåì ïî î÷åðåäè âñå ñëîâà y äëèíû 6 p1 (n). Äëÿ êàæäîãî yâû÷èñëÿåì Q(x, y).

Åñëè ïðè âû÷èñëåíèè Q(x, y) õîòÿ áû îäèí ðàç îòâåòQ(x, y) = èñòèíà, òî âûäàåì îòâåò äà, èíà÷å âûäàåì îòâåò íåò. Òàêêàê |x|+|y| 6 n+p1 (n) è Q ∈ P , òî âðåìÿ âû÷èñëåíèÿ Q(x, y) äëÿ îäíîãîy íå ïðåâîñõîäèò íåêîòîðîãî ïîëèíîìà îò n. Íî òîãäà è èñïîëüçóåìàÿïàìÿòü íå ïðåâîñõîäèò ïîëèíîìà îò n. Òåîðåìà äîêàçàíà.Ëåììà 6.1. Åñëè çîíà ðàáîòû ìàøèíû Òüþðèíãà íà âõîäàõ äëèíûnñîäåðæèò íå áîëååp1 (n)p1 (n)íåêîòîðûé ïîëèíîì,r ñèìâîëîâ, ó ìàøèíû k ñîñòîÿíèéÿ÷ååê, ãäåâ ëåíòî÷íîì àëôàâèòå ìàøèíûè ìàøèíà îñòàíàâëèâàåòñÿ íà ëþáîì âõîäå, òî ìàêñèìàëüíîå âðåìÿðàáîòût(n)ìàøèíû íà ñëîâàõ äëèíûnóäîâëåòâîðÿåò íåðàâåíñòâó:t(n) 6 rp1 (n) p1 (n) · k 6 2p(n) ,ãäåp(n)íåêîòîðûé ïîëèíîì.Åñëè çîíà ðàáîòû ìàøèíû ñîäåðæèò íå áîëåå p1 (n) ÿ÷ååê, òî ïðè ðàáîòå ìàøèíû ìîæåò ïîðîæäàòüñÿ íå áîëåårp1 (n) p1 (n) · k ðàçëè÷íûõ êîíôèãóðàöèé, ïîñêîëüêó íà ëåíòå ìîæíî çàïèñàòü íå áîëåå rp1 (n) ðàçëè÷íûõ ñëîâ, ãîëîâêà ìîæåò îáîçðåâàòü ëþáóþ èçíå áîëåå p1 (n) ÿ÷ååê è ìàøèíà ìîæåò íàõîäèòüñÿ â ëþáîì èç k ñîñòîÿíèé.Ïîñêîëüêó ïî óñëîâèþ ïðè ëþáîì âõîäå ìàøèíà îñòàíàâëèâàåòñÿ, òî îíàÄîêàçàòåëüñòâî.74íå ìîæåò çàöèêëèòüñÿ, òî åñòü êîíôèãóðàöèÿ íå ìîæåò ïîâòîðèòüñÿ.Ïîýòîìó âðåìÿ ðàáîòû ïðè ëþáîì âõîäå íå ïðåâîñõîäèò ÷èñëà ðàçëè÷íûõêîíôèãóðàöèé.

Ïðè ýòîìlog2 (rp1 (n) p1 (n) · k) = p1 (n) · log2 r + log2 p1 (n) + log2 k 6 p(n),ãäå p(n) íåêîòîðûé ïîëèíîì. Òåîðåìà äîêàçàíà.Ñëåäñòâèå. Äëÿ ëþáîé çàäà÷è èçp(n)P SP ACE t(n) 6 2p(n) ,ãäåíåêîòoðûé ïîëèíîì.Çàäà÷à ðàñïîçíàâàíèÿ (ÿçûê) L íàçûâàåòñÿP SP ACE -ïîëíîé, åñëè:1) L ∈ P SP ACE ,2) ê L ïîëèíîìèàëüíî ñâîäÿòñÿ âñå çàäà÷è èç P SP ACE .Îïðåäåëåíèå.Óòâåðæäåíèå.

Åñëè äëÿ íåêîòîðîéùåñòâóåò àëãîðèòì ñ ïîëèíîìèàëüíîéP SP ACE -ïîëíîé çàäà÷è ñóñëîæíîñòüþ, òî P SP ACE =P.Çàäà÷à î êâàíòèôèöèðîâàííûõ áóëåâñêèõ ôîðìóëàõ (QBF).Âõîä:ôîðìóëà âèäà(Q1 x1 )(Q2 x2 ) . . . (Qm xm )[F (x1 , . . . , xm )],ãäå x1 , . . . , xm áóëåâñêèå ïåðåìåííûå, F áóëåâñêàÿ ôîðìóëà â áàçèñå{êîíúþíêöèÿ, äèçúþíêöèÿ, îòðèöàíèå}, Qi ∈ {∃, ∀} äëÿ âñåõ i.Òðåáóåòñÿ: âûÿñíèòü, èñòèííà ëè äàííàÿ ôîðìóëà.QBF ∈ P SP ACE .Äîêàçàòåëüñòâî. Ïóñòü íà âõîä ïîñòóïèëà ôîðìóëàËåììà 6.2.(Q1 x1 )(Q2 x2 ) . .

. (Qm xm )[F (x1 , . . . , xm )],äëèíû n. Òîãäà äëèíà ôîðìóëû F (x1 , . . . , xm ) íå áîëåå n, è äëÿ ëþáîãîçàäàííîãî íàáîðà (α1 , . . . , αm ) âû÷èñëåíèå F (α1 , . . . , αm ) ìîæíî âûïîëíèòü çà âðåìÿ, à çíà÷èò è ñ èñïîëüçîâàíèåì ïàìÿòè, íå áîëåå p1 (n), ãäå p1íåêîòîðûé ïîëèíîì. Åñëè çàôèêñèðîâàíû òîëüêî çíà÷åíèÿ α1 , . .

. , αkïåðåìåííûõ x1 , . . . , xk , òî ìû ïîëó÷àåì ïîäçàäà÷ó: íàéòè èñòèííîñòíîåçíà÷åíèå ôîðìóëû(Qk+1 xk+1 ) . . . (Qm xm )[F (α1 , . . . , αk , xk+1 , . . . , xm )].Ïðèìåíèì äëÿ ðåøåíèÿ èñõîäíîé çàäà÷è (è âñåõ åå ïîäçàäà÷) ñëåäóþùèéðåêóðñèâíûé àëãîðèòì:1.