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

. . , α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, ïðåäñòàâëåííûì â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ.

Îáðàòèìòàêæå âíèìàíèå íà òî, ÷òî â îïðåäåëåíèè çàäà÷ ðàñïîçíàâàíèÿ íà âõîäìîæåò ïîñòóïèòü ëþáîå ñëîâî â çàäàííîì àëôàâèòå A.  çàäà÷å ÂÛÏìíîãèå òàêèå ñëîâà íå ïðåäñòàâëÿþò ÊÍÔ. Ïðåäïîëàãàåòñÿ, ÷òî îòâåòîì äëÿ òàêèõ âõîäíûõ ñëîâ ÿâëÿåòñÿ íåò. Àíàëîãè÷íî ïîíèìàþòñÿ èäðóãèå çàäà÷è (íàïðèìåð, ÊËÈÊÀ èëè ÃÖ).P ⊆ NP .∗Äîêàçàòåëüñòâî.

Ïóñòü L ∈ P , è L ⊆ A . Âîçüìåì ëþáîé àëôàâèòB è q(n) = 1. Ïðåäèêàò Q(ā, b̄) ïóñòü âûðàæàåò òîò ôàêò, ÷òî ā ∈ L(íåçàâèñèìî îò b̄). Òàê êàê L ∈ P , òî ïðåäèêàò Q ðàñïîçíàåòñÿ çà âðåìÿ,ïîëèíîìèàëüíî çàâèñÿùåå îò |ā|, à çíà÷èò è îò |ā| + |b̄|, òî åñòü Q ∈ P .Ïðè ýòîì, î÷åâèäíî, ÷òî äëÿ ëþáîãî ā ∈ A∗ ñïðàâåäëèâî ñîîòíîøåíèåÒåîðåìà 4.11.ā ∈ L ⇐⇒ ∃b̄ ∈ B ∗ (|b̄| 6 1&Q(ā, b̄))(ñåðòèôèêàò b̄ çäåñü íå çàâèñèò îò ā). Òàêèì îáðàçîì, L ∈ N P . Òåîðåìàäîêàçàíà.4.6. Òåîðåìà Êóêàßçûê L (çàäà÷à ðàñïîçíàâàíèÿ) íàçûâàåòñÿN P -òðóäíûì, åñëè ëþáîé ÿçûê L1 èç N P ïîëèíîìèàëüíî ñâîäèòñÿ êL. ñîîòâåòñòâèè ñ òåîðåìîé 4.10, åñëè ÿçûê L ÿâëÿåòñÿ N P -òðóäíûìè L ∈ P , òî N P ⊆ P è, ñ ó÷åòîì òåîðåìû 4.11, P = N P .

È îáðàòíî,åñëè P 6= N P , òî L ∈/ P . Òàêèì îáðàçîì, N P -òðóäíîñòü ÿçûêà ÿâëÿåòñÿêîñâåííûì ñâèäåòåëüñòâîì òîãî, ÷òî L ∈/ P (êîñâåííûì ïîòîìó, ÷òîâåðîÿòíî P 6= N P , íî ýòî ïîêà íå äîêàçàíî è íå îïðîâåðãíóòî).Îïðåäåëåíèå. ßçûê L (çàäà÷à ðàñïîçíàâàíèÿ) íàçûâàåòñÿN P -ïîëíûì, åñëè L ∈ N P è L ÿâëÿåòñÿ N P -òðóäíûì.Åñòåñòâåííî âîçíèêàåò âîïðîñ î òîì, ñóùåñòâóþò ëè òàêèå óíèâåðñàëüíûå çàäà÷è â êëàññå N P , ê êîòîðûì ïîëèíîìèàëüíî ñâîäÿòñÿ âñåçàäà÷è èç N P . Îêàçûâàåòñÿ, ÷òî ñóùåñòâóþò.

Ïåðâûé ðåçóëüòàò òàêîãîðîäà áûë óñòàíîâëåí Ñ. Êóêîì [12].Îïðåäåëåíèå.49Òåîðåìà 4.12ÿâëÿåòñÿ(Ñ. Êóê).Çàäà÷à ÂÛÏ (î âûïîëíèìîñòè ÊÍÔ)N P -ïîëíîé.Âûøå óæå äîêàçàíî, ÷òî ÂÛÏ ∈ N P . Ïîýòîìóíàäî äîêàçàòü, ÷òî ëþáîé ÿçûê L èç N P ïîëèíîìèàëüíî ñâîäèòñÿ êÂÛÏ. Ïóñòü L ∈ N P è L ⊆ A∗ . Ýòî îçíà÷àåò, ÷òî ñóùåñòâóþò ïîëèíîìq(n), àëôàâèò B è ïðåäèêàò Q(x, y) : A∗ × B ∗ → {èñòèíà, ëîæü }òàêèå, ÷òî Q(x, y) ∈ P è äëÿ ëþáîãî ñëîâà ā ∈ A∗ ñïðàâåäëèâîÄîêàçàòåëüñòâî.ā ∈ L ⇐⇒ ∃b̄(|b̄| 6 q(|ā|)&Q(ā, b̄)).Íàì íàäî ïîêàçàòü, ÷òî L ïîëèíîìèàëüíî ñâîäèòñÿ ê ÂÛÏ.

Ýòîîçíà÷àåò, ÷òî íàäî ïîñòðîèòü òàêîå ïðåîáðàçîâàíèå ñ ïîëèíîìèàëüíîéñëîæíîñòüþ ϕ : A∗ → C ∗ , ãäå C àëôàâèò çàäà÷è ÂÛÏ, ÷òî ā ∈ L ⇐⇒ϕ(ā) = Fā âûïîëíèìàÿ ÊÍÔ îò íåêîòîðûõ ïåðåìåííûõ.Òàê êàê Q(x, y) ∈ P , òî ñóùåñòâóåò ìàøèíà Òüþðèíãà M , êîòîðàÿðàñïîçíàåò ïðåäèêàò Q(x, y) çà âðåìÿ (÷èñëî øàãîâ), íå ïðåâîñõîäÿùååíåêîòîðîãî ïîëèíîìà p0 îò äëèíû âõîäà. Áóäåì ñ÷èòàòü, ÷òî íà÷àëüíàÿêîíôèãóðàöèÿ ìàøèíû M1 ÿâëÿåòñÿ ñòàíäàðòíîé, òî åñòü ïàðà (ā, b̄)ïðåäñòàâëÿåòñÿ íà ëåíòå äâóìÿ ñëîâàìè ā è b̄ ñ îäíîé ðàçäåëÿþùåéÿ÷åéêîé, â êîòîðîé ñòàâèòñÿ ïóñòîé ñèìâîë Λ, ãîëîâêà îáîçðåâàåò ñàìûé ëåâûé ñèìâîë ñëîâà ā è ìàøèíà íàõîäèòñÿ â íà÷àëüíîì ñîñòîÿíèèq1 .

Òîãäà âðåìÿ ðàáîòû M1 íà ïðîèçâîëüíîé ïàðå (ā, b̄) íå ïðåâûøàåòp0 (|ā| + |b̄| + 1). Áóäåì ñ÷èòàòü, ÷òî ìàøèíà M1 îñòàíàâëèâàåòñÿ òîëüêîâ îäíîì èç äâóõ çàêëþ÷èòåëüíûõ ñîñòîÿíèé, ïðè÷åì çàêëþ÷èòåëüíîåñîñòîÿíèå q0 ìàøèíû M1 ñîîòâåòñòâóåò îòâåòó äà (êàêîå ñîñòîÿíèåñîîòâåòñòâóåò îòâåòó íåò äëÿ íàñ áóäåò íå âàæíî).Ïóñòü äàíî ā ∈ A∗ è |ā| = n. Òîò ôàêò, ÷òî ā ∈ L, ðàâíîñèëåí âñîîòâåòñòâèè ñ () òîìó, ÷òî íàéäåòñÿ ñëîâî b̄ ∈ B ∗ ñ äëèíîé |b̄| 6 q(n)òàêîå, ÷òî ìàøèíà M1 , íà÷àâ ðàáîòó íà ïàðå (ā, b̄), ïðèäåò â ñîñòîÿíèåq0 = äà. Ïðè ýòîì âðåìÿ ðàáîòû M1 íà ïàðå (ā, b̄) íå ïðåâîñõîäèòp0 (n+q(n)+1) = p(n), ãäå p íåêîòîðûé ïîëèíîì.

Îòìåòèì, ÷òî ìîæíîñ÷èòàòü, ÷òî âî âñåõ ïîëèíîìàõ âñå êîýôôèöèåíòû íåîòðèöàòåëüíû.Òîãäà p(n) > n + 1 + q(n).Íåñêîëüêî ìîäèôèöèðóåì ïðîãðàììó ìàøèíû M1 . À èìåííî, åñëèìàøèíà M1 íàõîäèòñÿ â íåêîòîðîì çàêëþ÷èòåëüíîì ñîñòîÿíèè è ãîëîâêàîáîçðåâàåò íåêîòîðûé ñèìâîë, òî ïóñòü ìàøèíà M1 îñòàâëÿåò â ÿ÷åéêåòîò æå ñèìâîë, ãîëîâêà íèêóäà íå ñäâèãàåòñÿ è ìàøèíà îñòàåòñÿ â òîì æåñîñòîÿíèè.

Òî åñòü ðåàëüíî íè÷åãî íå ïðîèñõîäèò, íî ôîðìàëüíî ìàøèíàïðîäîëæàåò ðàáîòàòü áåñêîíå÷íî. Ïîëó÷åííóþ ìàøèíó îáîçíà÷èì M .50Òîãäà äëÿ ñëîâà ā ∈ A∗ äëèíû |ā| = n èìååì:ā ∈ L ⇐⇒ ∃b̄ ∈ B ∗ (|b̄| 6 q(n) è ìàøèíà M,çàïóùåííàÿ íà ïàðå (ā, b̄), â ìîìåíò âðåìåíè p(n)áóäåò íàõîäèòüñÿ â ñîñòîÿíèè q0 = äà ).(4.2)Íàøà äàëüíåéøàÿ öåëü çàïèñàòü ïðàâóþ ÷àñòü â ýòîé ðàâíîñèëüíîñòè â âèäå ÊÍÔ Fā (x1 , .

. . , xm ) îò íåêîòîðûõ ïåðåìåííûõ, òàê ÷òîáûôîðìóëà Fā áûëà âûïîëíèìà òîãäà è òîëüêî òîãäà, êîãäà ýòà ïðàâàÿ÷àñòü èñòèííà. Ïåðåïèøåì (4.2) áîëåå ïîäðîáíî:ā ∈ L ⇐⇒ ∃b̄ ∈ B ∗ ∃K0 , K1 , . . . , Kp(n) (|b̄| 6 q(n) èK0 , K1 , . . . , Kp(n) êîíôèãóðàöèè ìàøèíû M òàêèå,÷òî K0 íà÷àëüíàÿ êîíôèãóðàöèÿ äëÿ ïàðû (ā, b̄),ñîñòîÿíèå â Kp(n) åñòü q0 è äëÿ êàæäîãîj = 0, 1, . . . , p(n) − 1 êîíôèãóðàöèÿ Kj+1 ïîëó÷àåòñÿèç Kj ïî ïðîãðàììå ìàøèíû M ).(4.3)Ïóñòü ÿ÷åéêè ëåíòû â M çàíóìåðîâàíû öåëûìè ÷èñëàìè ñëåâàíàïðàâî è ÿ÷åéêà, ñ êîòîðîé ãîëîâêà íà÷èíàåò ðàáîòàòü (è ñ êîòîðîéíà÷èíàåòñÿ ñëîâî ā), èìååò íîìåð 0.

Òîãäà çà p(n) òàêòîâ ãîëîâêà íå ìîæåò ïîïàñòü â ÿ÷åéêè ñ íîìåðàìè ìåíüøå −p(n) è áîëüøå p(n). Ïîýòîìóìîæíî ñ÷èòàòü, ÷òî êîíôèãóðàöèè K0 , K1 , . . . , Kp(n) îïðåäåëåíû òîëüêîíà çîíå [−p(n), p(n)] ëåíòû.Ïóñòü ìàøèíà M èìååò ëåíòî÷íûé àëôàâèò D = {d0 , d1 , . . . , dm },ãäå d0 = Λ, ïðè ýòîì A ⊆ D è B ⊆ D.

Ïóñòü W = {q0 , q1 , . . . , ql } ìíîæåñòâî âñåõ ñîñòîÿíèé ìàøèíû M , ïðè÷åì q1 íà÷àëüíîå ñîñòîÿíèå è q0 = äà. Ââåäåì áóëåâñêèå ïåðåìåííûå xti,j , yit , zkt , ãäå i =−p(n), −p(n)+1, . . . , p(n); j = 0, 1, . . . , m; k = 0, 1, . . . , l; t = 0, 1, . . . , p(n)è ïðèäàäèì èì ñëåäóþùèé ñìûñë:xti,j = èñòèíà ⇐⇒ â i-é ÿ÷åéêå â êîíôèãóðàöèè Kt íàõîäèòñÿñèìâîë dj ;yit = èñòèíà ⇐⇒ â êîíôèãóðàöèè Kt ãîëîâêà îáîçðåâàåò ÿ÷åéêóñ íîìåðîì i;zkt = èñòèíà ⇐⇒ â êîíôèãóðàöèè Kt ñîñòîÿíèå qk .Èñêîìóþ ôîðìóëó Fā ìû áóäåì ñòðîèòü êàê ÊÍÔ îò âñåõ ýòèõïåðåìåííûõ Fā ({xti,j }, {yit }, {zkt }) ïðè÷åì òàê, ÷òîáû îíà áûëà âûïîëíèìàòîãäà è òîëüêî òîãäà, êîãäà ïðàâàÿ ÷àñòü â (4.3) èñòèííà.

Äëÿ ýòîãîäîñòàòî÷íî, ÷òîáû ÊÍÔ Fā áûëà èñòèííà íà íåêîòîðîì íàáîðå òîãäà èòîëüêî òîãäà, êîãäà:511)ýòîòíàáîð êîððåêòíî çàäàåò íàáîð êîíôèãóðàöèéK0 , K1 , . . . , Kp(n) ìàøèíû M ;2) ïðè ýòîì êîíôèãóðàöèÿ K0 ÿâëÿåòñÿ ïðàâèëüíîé íà÷àëüíîéêîíôèãóðàöèåé äëÿ ïàðû (ā, b̄), ãäå ā çàäàííîå ñëîâî è b̄ ∈ B ∗ êàêîå-íèáóäü ñëîâî äëèíû íå áîëåå q(n);3) â êîíôèãóðàöèè Kp(n) ñîñòîÿíèå q0 = äà;4) äëÿ êàæäîãî j = 0, 1, .

. . , p(n)−1 êîíôèãóðàöèÿ Kj+1 ïîëó÷àåòñÿèç Kj ïî ïðîãðàììå ìàøèíû M .Ðàññìîòðèì ñâîéñòâî 1). Åñëè çàäàíà êîíôèãóðàöèÿ Kt , òî ïî íåéîäíîçíà÷íî îïðåäåëÿþòñÿ çíà÷åíèÿ ïåðåìåííûõ xti,j , yit , zkt ïðè äàííîì t.Îáðàòíîå íåâåðíî, ïîñêîëüêó, íàïðèìåð, åñëè ñðàçó 2 ïåðåìåííûå xti,j1è xti,j2 èñòèííû, òî ýòî îçíà÷àåò, ÷òî â êîíôèãóðàöèè Kt â ÿ÷åéêå iäîëæíû íàõîäèòüñÿ è ñèìâîë dj1 è ñèìâîë dj2 . Ëåãêî ïîíÿòü, ÷òî óñëîâèåêîððåêòíîãî çàäàíèÿ êîíôèãóðàöèé âûðàæàåòñÿ ñëåäóþùèì îáðàçîì:ïðè êàæäîì t äëÿ êàæäîãî i ðîâíî îäíà èç ïåðåìåííûõ xti,j =èñòèíà; ïðè êàæäîì t ðîâíî îäíà èç ïåðåìåííûõ yit = èñòèíàè ïðè êàæäîì t ðîâíî îäíà èç ïåðåìåííûõ zkt = èñòèíà.Ïóñòü H(v1 , . .

. , vs ) ôóíêöèÿ àëãåáðû ëîãèêè, ðàâíàÿ 1 òîãäà èòîëüêî òîãäà, êîãäà ñðåäè v1 , . . . , vs ðîâíî 1 åäèíèöà.Ëåììà 4.15. ÔóíêöèþH(v1 , . . . , vs )ìîæíî ïðåäñòàâèòü â âèäå2ÊÍÔ ñ äëèíîé (÷èñëîì ëèòåðàëîâ) íå áîëåå s .Äîêàçàòåëüñòâî.Ëåãêî ïðîâåðèòü, ÷òîH(v1 , . . . , vs ) = (v1 ∨ v2 ∨ . . . ∨ vs )&(&i6=j (v̄i ∨ v̄j )).s(s−1)· 2 = s2 .2Ëåììà 4.16. Òîò ôàêò, ÷òî íàáîð ïåðåìåííûõÄëèíà ýòîé ÊÍÔ ðàâíà s +xti,j , yit , zktêîð-K0 , K1 , . . .

, Kp(n) , ìîæíî âûðàçèòü â âèäåÊÍÔ F1 äëèíû íå áîëåå p1 (n), ãäå p1 íåêîòîðûé ïîëèíîì.Äîêàçàòåëüñòâî. Ýòîò ôàêò âûðàæàåòñÿ ôîðìóëîéðåêòíî çàäàåò êîíôèãóðàöèèp(n)p(n)F10 = &t=0 &i=−p(n) H(xti,0 , xti,1 , . . . , xti,m ) &p(n)p(n)ttt& &t=0 H(y−p(n), y−p(n)+1, . . . , yp(n)) & &t=0 H(z0t , z1t , . . .

, zlt ).Ïðåäñòàâëÿÿ êàæäóþ ôóíêöèþ H ñ ïîìîùüþ ÊÍÔ â ñîîòâåòñòâèè ñëåììîé 4.15, ïîëó÷èì ÊÍÔ F1 äëèíû(p(n)(2p(n)+1)(m+1)2 +(p(n)+1)(2p(n)+1)2 +(p(n)+1)(l +1)2 6 p1 (n),ãäå p1 (n) íåêîòîðûé ïîëèíîì.52x0i,j , yi0 , zk0Ëåììà 4.17. Ïðè óñëîâèè, ÷òî íàáîð ïåðåìåííûõðåêòíî çàäàåò êîíôèãóðàöèþK0 ,òîò ôàêò, ÷òîK0êîð-ÿâëÿåòñÿ ïðà-âèëüíîé íà÷àëüíîé êîíôèãóðàöèåé äëÿ ïàðû (ā, b̄), ãäå ā çàäàííîå∗ñëîâî è b̄ ∈ B êàêîå-íèáóäü ñëîâî äëèíû íå áîëåå q(n), ìîæíîâûðàçèòü â âèäå ÊÍÔF2äëèíû íå áîëååp2 (n),ãäåp2 íåêîòîðûéïîëèíîì.Ïóñòü ā = dj1 dj2 .