В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 12
Текст из файла (страница 12)
. . djn è b̄ ∈ B ∗ , ãäå B ={dr1 , dr2 , . . . , drw }. Òîãäà óêàçàííûé â ëåììå ôàêò âûðàæàåòñÿ ôîðìóëîéÄîêàçàòåëüñòâî.F2 = y00 &z10 &x00,j1 &x01,j2 & . . . &x0n−1,jn &x0n,0 &n+q(n)00000& (&−1i=−p(n) xi,0 ) & &i=n+1 (xi,r1 ∨ xi,r2 ∨ . . . ∨ xi,rw ∨ xi,0 ) &p(n)n+q(n)−1& (&i=n+q(n)+1 x0i,0 ) & &i=n+1(x̄0i,0 ∨ x0i+1,0 ).Ïîñëåäíÿÿ ñêîáêà x̄0i,0 ∨ x0i+1,0 = x0i,0 → x0i+1,0 îçíà÷àåò, ÷òî åñëè â ÿ÷åéêåi ñòîèò ïóñòîé ñèìâîë, òî è â ñëåäóþùåé ÿ÷åéêå äîëæåí ñòîÿòü ïóñòîéñèìâîë, òî åñòü ñëîâî b̄ íå ìîæåò èìåòü ðàçðûâîâ. Ôîðìóëà F2 ÿâëÿåòñÿÊÍÔ ñ äëèíîén + 3 + p(n) + q(n) · (w + 1) + p(n) − n − q(n) + (q(n) − 1) · 2 6 p2 (n),ãäå p2 íåêîòîðûé ïîëèíîì.Ñëåäóþùåå óòâåðæäåíèå î÷åâèäíî.Ëåììà 4.18. Òîò ôàêò, ÷òî âKp(n)ñîñòîÿíèå åñòüq0 ,âûðàæà-p(n)F3 = z0 .Ðàññìîòðèì òåïåðü áîëåå ïîäðîáíî ïðîãðàììó ìàøèíû M .
Ïðåäñòàâèì åå êîìàíäû â âèäå dj qk → dϕ(j,k) qψ(j,k) R(j, k), ãäå R(j, k) = −1, 0èëè 1 ñîîòâåòñòâåííî, äëÿ ñäâèãà âëåâî, îñòàâëåíèÿ ãîëîâêè íà ìåñòå èñäâèãà âïðàâî.Ëåììà 4.19. Ïðè óñëîâèè, ÷òî íàáîð ïåðåìåííûõ xti,j , yit , zkt êîððåêòíî çàäàåò êîíôèãóðàöèè K0 , K1 , . . . , Kp(n) , òîò ôàêò, ÷òî êàæäàÿêîíôèãóðàöèÿ Kj+1 ïîëó÷àåòñÿ èç Kj ïî ïðîãðàììå ìàøèíû M , ìîæíîâûðàçèòü â âèäå ÊÍÔ F4 äëèíû íå áîëåå p4 (n), ãäå p4 íåêîòîðûéåòñÿ â âèäå ÊÍÔïîëèíîì.Äîêàçàòåëüñòâî.p(n)−1F40 = &t=0Ýòîò ôàêò âûðàæàåòñÿ ôîðìóëîép(n)lttt&i=−p(n) &mj=0 &k=0 (yi &xi,j &zk →t+1t+1→ xt+1i,ϕ(j,k) &zψ(j,k) &yi+R(j,k) ) &p(n)−1& &t=0p(n)t+1t&i=−p(n) (ȳit → &mj=0 (xi,j ≡ xi,j )).Ïåðâàÿ ÷àñòü ýòîé ôîðìóëû âûðàæàåò èçìåíåíèå èíôîðìàöèè â îáîçðåâàåìîé ÿ÷åéêå, èçìåíåíèå ñîñòîÿíèÿ è ñäâèã ãîëîâêè, âòîðàÿ ÷àñòü53âûðàæàåò òîò ôàêò, ÷òî ñèìâîëû âî âñåõ ÿ÷åéêàõ, êðîìå îáîçðåâàåìîé,íå èçìåíÿþòñÿ. Âûðàæåíèå â ïåðâîé ñêîáêå â F40 ýòî ôóíêöèÿ îò 6ïåðåìåííûõ è åå (êàê ëþáóþ ôóíêöèþ àëãåáðû ëîãèêè, îòëè÷íóþ îòêîíñòàíòû 1) ìîæíî ïðåäñòàâèòü â âèäå ÊÍÔ íåêîòîðîé äëèíû L1 .
Àíàëîãè÷íî ìîæíî ïðåäñòàâèòü â âèäå ÊÍÔ êîíñòàíòíîé äëèíû L2 ôóíêöèþîò 2m+1 ïåðåìåííûõ, ñòîÿùóþ âî âòîðîé ñêîáêå. Ïðè ýòîì F40 ïðåîáðàçóåòñÿ â ÊÍÔ K4 äëèíû p(n)·(2p(n)+1)·m·l·L1 +p(n)·(2p(n)+1)·L2 6 p4 (n),ãäå p4 íåêîòîðûé ïîëèíîì.Ïîëîæèì Fā = F1 · F2 · F3 · F4 . Òîãäà Fā ÊÍÔ è ïî ëåììàì4.16-4.19 íà íàáîðå ïåðåìåííûõ xti,j , yit , zkt îíà èñòèííà òîãäà è òîëüêî òîãäà, êîãäà ïåðåìåííûå êîððåêòíî çàäàþò íåêîòîðîå âû÷èñëåíèå ìàøèíûM , ïðèâîäÿùåå â ñîñòîÿíèå q0 = äà, äëÿ âõîäíîé ïàðû (ā, b̄), ãäå b̄ êàêîå-íèáóäü ñëîâî èç B ∗ òàêîå, ÷òî |b̄| 6 q(|ā|).
Òàêèì îáðàçîì Fāèñòèííà õîòÿ áû íà îäíîì íàáîðå (ò.å. âûïîëíèìà) â òîì è òîëüêî â òîìñëó÷àå, åñëè èñòèííà ïðàâàÿ ÷àñòü â (4.3) è, ñëåäîâàòåëüíî, åñëè ā ∈ L.Ïîëó÷àåì, ÷òî Fā èñêîìàÿ ÊÍÔ. Åå äëèíà íå ïðåâîñõîäèò íåêîòîðîãîïîëèíîìà îò n. Ïðè ýòîì íåòðóäíî ïîíÿòü, ÷òî ïî äàííîìó ñëîâó ā (èôèêñèðîâàííîé ïðîãðàììå ìàøèíû M ) ýòà ÊÍÔ Fā = F1 · F2 · F3 · F4âûïèñûâàåòñÿ çà âðåìÿ, îãðàíè÷åííîå ïîëèíîìîì îò åå äëèíû, è, ñëåäîâàòåëüíî, îãðàíè÷åííîå ïîëèíîìîì îò äëèíû ñëîâà ā. Òàêèì îáðàçîì,îòîáðàæåíèå ā → Fā ÿâëÿåòñÿ ïîëèíîìèàëüíûì ñâåäåíèåì ÿçûêà L êÿçûêó ÂÛÏ.
Ïîñêîëüêó L ïðîèçâîëüíûé ÿçûê èç N P , òî ïîëó÷àåì,÷òî ÂÛÏ N P -òðóäíàÿ çàäà÷à, à òàê êàê ÂÛÏ ∈ N P (ñì. ï. 4.5), òîÂÛÏ N P -ïîëíàÿ çàäà÷à. Òåîðåìà Êóêà äîêàçàíà.4.7. Ñëîæíîñòü çàäà÷ î âûïîëíèìîñòèÑëåäóþùàÿ òåîðåìà ïîçâîëÿåò âûâîäèòü N P -ïîëíîòó îäíèõ çàäà÷èç N P -ïîëíîòû äðóãèõ çàäà÷.Òåîðåìà 4.13. Åñëèñâîäèòñÿ ê ÿçûêóNP ,òîN P -ïîëíûé ÿçûê.Äîêàçàòåëüñòâî.
Ïóñòü L ëþáîé ÿçûê èç N P . Òàê êàê L1 N P -òðóäíûé ÿçûê, òî L ïîëèíîìèàëüíî ñâîäèòñÿ ê L1 . Ïðè ýòîì, åñëèäëèíà èñõîäíîãî ñëîâà ðàâíà n, òî ïðè ñâåäåíèè îíî ïåðåõîäèò â ñëîâîäëèíû íå áîëåå q(n), ãäå q íåêîòîðûé ïîëèíîì. Òàê êàê ïî óñëîâèþ L1ñâîäèòñÿ ê L2 çà âðåìÿ, ïîëèíîìèàëüíî çàâèñÿùåå îò äëèíû ñâîäèìîãîñëîâà, òî êîìïîçèöèÿ äâóõ ñâåäåíèé ïîëèíîìèàëüíî ñâîäèò L ê L2 . Òàêêàê L ïðîèçâîëüíûé ÿçûê èç N P , òî L2 N P -òðóäíûé ÿçûê ïîîïðåäåëåíèþ.òîL2L2 ,L1 N P -òðóäíûé ÿçûê è L1 ïîëèíîìèàëüíîL2 N P -òðóäíûé ÿçûê. Åñëè ïðè ýòîì L2 ∈54ÊÍÔ, ó êîòîðîé â êàæäîì äèçúþíêòå ðîâíî 3ðàçëè÷íûõ ëèòåðàëà, áóäåì íàçûâàòü 3-ÊÍÔ.Îïðåäåëåíèå.Çàäà÷à 3-âûïîëíèìîñòü (3-ÂÛÏ).Âõîäíîé àëôàâèò òîò æå, ÷òî è â çàäà÷å ÂÛÏ.Âîïðîñ: âåðíî ëè, ÷òî âõîäíîå ñëîâî ýòî 3-ÊÍÔ, êîòîðàÿ âûïîëíèìà.∈ N P.Äîêàçàòåëüñòâî.
Çàäà÷à 3-ÂÛÏ óäîâëåòâîðÿåò îïðåäåëåíèþ çàäà÷èç êëàññà N P . Ïðè ýòîì â êà÷åñòâå ñåðòèôèêàòà äîñòàòî÷íî âçÿòü íàáîð α̃, íà êîòîðîì äàííàÿ 3-ÊÍÔ âûïîëíèìà (åñëè òàêîé ñóùåñòâóåò),à àëãîðèòì ïðîâåðêè ñåðòèôèêàòà áóäåò ïðîâåðÿòü, äåéñòâèòåëüíî ëèâõîäíîå ñëîâî åñòü 3-ÊÍÔ è âåðíî ëè, ÷òî ýòà ÊÍÔ íà íàáîðå α̃ ðàâíà 1.Âñå ýòî ìîæíî îñóùåñòâèòü çà ïîëèíîìèàëüíîå (îò äëèíû âõîäà) âðåìÿ.Òåîðåìà 4.14. Çàäà÷à 3-ÂÛÏ N P -ïîëíà.Äîêàçàòåëüñòâî. Ñâåäåì çàäà÷ó ÂÛÏ ïîëèíîìèàëüíî ê çàäà÷å3-ÂÛÏ.
Ïóñòü A àëôàâèò îáåèõ çàäà÷. Íàì íàäî äëÿ êàæäîãî ñëîâàā ∈ A∗ çà ïîëèíîìèàëüíîå (îò äëèíû ñëîâà ā) âðåìÿ ïîñòðîèòü ñëîâîϕ(ā) òàê, ÷òîáû ϕ(ā) áûëî âûïîëíèìîé 3-ÊÍÔ òîãäà è òîëüêî òîãäà,êîãäà ā âûïîëíèìàÿ ÊÍÔ. Åñëè ā ∈ A∗ íå ÊÍÔ, òî ïîëîæèì ϕ(ā) = ā.Åñëè æå ā ÊÍÔ D1 · D2 · . . . · Ds îò ïåðåìåííûõ x1 , x2 , . . . , xn , òîïðåîáðàçóåì åå â 3-ÊÍÔ ϕ(ā) = F1 · F2 · .
. . · Fs ñëåäóþùèì îáðàçîì.Ïóñòü Y = {y1 , y2 , . . .} íåêîòîðûå ïåðåìåííûå, êîòîðûå íå âñòðå÷àþòñÿâ ÊÍÔ ā. Ðàññìîòðèì 4 ñëó÷àÿ.1) Åñëè Di = ti,1 ∨ ti,2 ∨ ti,3 , òî ïîëîæèì Fi = Di .2) Åñëè Di = ti,1 ∨ti,2 , òî ïîëîæèì Fi = (ti,1 ∨ti,2 ∨yj )·(ti,1 ∨ti,2 ∨ ȳj ),ãäå yj ∈ Y . Çàìåòèì, ÷òî Fi = 1 ⇐⇒ Di = 1.3) Åñëè Di = ti , òî ïîëîæèìÓòâåðæäåíèå. 3-ÂÛÏFi = (ti ∨ yk ∨ yl )(ti ∨ yk ∨ ȳl ) · (ti ∨ ȳk ∨ yl )(ti ∨ ȳk ∨ ȳl ),ãäå yk 6= yl . Îïÿòü Fi = 1 ⇐⇒ Di = 1.4) Ïóñòü Di = t1 ∨ t2 ∨ . .
. ∨ tm è m > 4. ÏîëîæèìFi = (t1 ∨ t2 ∨ y1 )(ȳ1 ∨ t3 ∨ y2 )(ȳ2 ∨ t4 ∨ y3 ) · . . .. . . · (ȳm−4 ∨ tm−2 ∨ ym−3 )(ȳm−3 ∨ tm−1 ∨ tm ),ãäå âñå yj ðàçëè÷íû.Ëåììà 4.20.  ñëó÷àå 4), åñëèòî ñóùåñòâóåò íàáîð çíà÷åíèéFi = 1, òî è Di = 1, à åñëè Di = 1,ïåðåìåííûõ y1 , y2 , . . . , ym−3 òàêîé, ÷òîFi = 1.55Ïóñòü α̃ = (α1 , . . . , αn )íàáîð çíà÷åíèé ïåðåìåííûõ x1 , . . .
, xn èç Di è β̃ = (β1 , . . . , βm−3 )íàáîð çíà÷åíèé ïåðåìåííûõy1 , . . . , ym−3 . Ïóñòü Fi (α̃, β̃) = 1, òî åñòü âñå ñêîáêè â Fi íà íàáîðå (α̃, β̃)ðàâíû 1. Åñëè β1 = 0, òî t1 (α̃) ∨ t2 (α̃) = 1 è Di (α̃) = 1. Åñëè βm−3 = 1,òî tm−1 (α̃) ∨ tm (α̃) = 1 è Di (α̃) = 1. Åñëè æå β1 = 1 è βm−3 = 0, òîíàéäåòñÿ k òàêîå, ÷òî βk = 1, βk+1 = 0.
Òàê êàê β̄k ∨ tk+2 (α̃) ∨ βk+1 = 1,òî â ýòîì ñëó÷àå tk+2 (α̃) = 1 è Di (α̃) = 1. Ñëåäîâàòåëüíî, åñëè Fi = 1,òî è Di = 1. Îáðàòíî ïóñòü Di (α̃) = 1. Òîãäà ñóùåñòâóåò tk òàêîå, ÷òîtk (α̃) = 1. Åñëè k = 1 èëè k = 2, òî âûáåðåì β1 = β2 = . . . = βm−3 = 0.Ïðè ýòîì Fi (α̃, β̃) = 1. Åñëè k = m − 1 èëè k = m, òî âûáåðåìβ1 = β2 = . . . = βm−3 = 1. Ïðè ýòîì îïÿòü Fi (α̃, β̃) = 1.  îñòàëüíûõñëó÷àÿõ ïîëîæèì β1 = β2 = . . . = βk−2 = 1, βk−1 = βk = . . . = βm−3 = 0.Ñíîâà ïîëó÷èì Fi (α̃, β̃) = 1.
Ëåììà äîêàçàíà.Ïðîäåëàåì óêàçàííûå âûøå â ïóíêòàõ 2)-4) çàìåíû Di íà Fi ,èñïîëüçóÿ äëÿ ðàçíûõ Di ðàçíûå ïåðåìåííûå yj . Òîãäà ïî ëåììå 4.20ïîëó÷àåì, ÷òî åñëè 3-ÊÍÔ F1 · F2 · . . . · Fs ðàâíà 1 íà êàêîì-òî íàáîðå,òî íà òîì æå íàáîðå ðàâíà 1 è ÊÍÔ D1 · D2 · . . . · Ds , è îáðàòíî, åñëèÊÍÔ D1 · D2 · . . . · Ds ðàâíà 1 íà íåêîòîðîì íàáîðå, òî ñóùåñòâóåò íàáîð,íà êîòîðîì 3-ÊÍÔ F1 · F2 · . . . · Fs òàêæå ðàâíà 1. Òàêèì îáðàçîì 3-ÊÍÔF1 · F2 · .
. . · Fs âûïîëíèìà òîãäà è òîëüêî òîãäà, êîãäà âûïîëíèìà ÊÍÔD1 · D2 · . . . · Ds , òî åñòü íàøå ïðåîáðàçîâàíèå ÿâëÿåòñÿ ñâåäåíèåì çàäà÷èÂÛÏ ê çàäà÷å 3-ÂÛÏ.Ðàñïîçíàòü, ÿâëÿåòñÿ ëè âõîäíîå ñëîâî ā ∈ A∗ ÊÍÔ ìîæíî çàïîëèíîìèàëüíîå îò äëèíû ā âðåìÿ. Ïðåîáðàçîâàòü âñå Di â Fi òàêæåìîæíî çà ïîëèíîìèàëüíîå âðåìÿ. Ïîýòîìó ìû èìååì ïîëèíîìèàëüíîåñâåäåíèå çàäà÷è ÂÛÏ ê çàäà÷å 3-ÂÛÏ. Ïîñêîëüêó çàäà÷à ÂÛÏ ÿâëÿåòñÿN P -ïîëíîé è 3-ÂÛÏ ∈ N P , òî ïî òåîðåìå 4.13 ïîëó÷àåì, ÷òî çàäà÷à3-ÂÛÏ ÿâëÿåòñÿ N P -ïîëíîé.Ïîñìîòðèì, íåëüçÿ ëè â ïîñëåäíåé òåîðåìå çàìåíèòü 3 íà 2.Îïðåäåëåíèå. ÊÍÔ, ó êîòîðîé â êàæäîì äèçúþíêòå íå áîëåå 2ëèòåðàëîâ, áóäåì íàçûâàòü 2-ÊÍÔ.Äîêàçàòåëüñòâî.Çàäà÷à 2-âûïîëíèìîñòü (2-ÂÛÏ).Âõîäíîé àëôàâèò òîò æå, ÷òî è â çàäà÷å ÂÛÏ.Âîïðîñ: âåðíî ëè, ÷òî âõîäíîå ñëîâî ýòî 2-ÊÍÔ, êîòîðàÿ âûïîëíèìà.Òåîðåìà 4.15.
Äëÿ çàäà÷è 2-ÂÛÏ ñóùåñòâóåò àëãîðèòì ñ ïîëè-∈ P ).Äîêàçàòåëüñòâî. Ïðîâåðèòü, ÿâëÿåòñÿ ëè âõîäíîå ñëîâî 2-ÊÍÔ,ìîæíî çà ïîëèíîìèàëüíîå âðåìÿ. Ïîýòîìó áóäåì ñ÷èòàòü, ÷òî íàì óæåíîìèàëüíîé ñëîæíîñòüþ (òî åñòü 2-ÂÛÏ56äàíà 2-ÊÍÔ D1 · D2 · . . . · Ds è òðåáóåòñÿ âûÿñíèòü, âûïîëíèìà ëè îíà.Ïóñòü äèçúþíêòû D0 = xi ∨ t1 è D00 = x̄i ∨ t2 èìåþò ïðîòèâîïîëîæíûåëèòåðàëû xi è x̄i (ïðè ýòîì ìîæåò áûòü t1 = ∅ èëè t2 = ∅). Òîãäà000ðåçîëüâåíòîé äèçúþíêòîâ D è D ïî xi áóäåì íàçûâàòü äèçúþíêò D =t1 ∨ t2 (åñëè t1 = t2 , òî t1 ∨ t2 = t1 ). Åñëè t1 = ∅ è t2 = ∅, òî ïîëîæèìD ≡ 0.Ëåììà 4.21. Äëÿ ëþáûõ ôîðìóëAèBâûïîëíÿåòñÿ ðàâåíñòâî(xi ∨ A)(x̄i ∨ B) = (xi ∨ A)(x̄i ∨ B)(A ∨ B).Åñëè ïðàâàÿ ÷àñòü ðàâíà 1, òî, î÷åâèäíî, è ëåâàÿ÷àñòü ðàâíà 1. Åñëè ïðàâàÿ ÷àñòü ðàâíà 0, òî ëèáî xi ∨ A = 0, ëèáîx̄i ∨B = 0, ëèáî A∨B = 0.
 ïåðâûõ äâóõ ñëó÷àÿõ ëåâàÿ ÷àñòü ðàâíà 0. Âïîñëåäíåì ñëó÷àå A = 0 è B = 0. Òîãäà ëåâàÿ ÷àñòü ðàâíà (xi ∨0)(x̄i ∨0) =xi x̄i = 0. Ëåììà äîêàçàíà.Ýòà ëåììà ïîêàçûâàåò, ÷òî äîáàâëåíèå ê 2-ÊÍÔ ðåçîëüâåíòû ëþáîé ïàðû äèçúþíêòîâ íå ìåíÿåò ôóíêöèþ, ðåàëèçóåìóþ 2-ÊÍÔ. Áóäåì ïðîñìàòðèâàòü âñå ïàðû äèçúþíêòîâ òåêóùåé 2-ÊÍÔ è ñòðîèòü èõðåçîëüâåíòû. Åñëè îêàæåòñÿ, ÷òî íåêîòîðàÿ ðåçîëüâåíòà îòñóòñòâóåò âòåêóùåé 2-ÊÍÔ, òî äîáàâèì åå è íà÷íåì ïðîñìîòð ñíà÷àëà. Òàê áóäåì äåëàòü äî òåõ ïîð, ïîêà íå îêàæåòñÿ, ÷òî âñå ðåçîëüâåíòû òåêóùåé 2-ÊÍÔóæå ñîäåðæàòñÿ â íåé. Åñëè ïðè ýòîì áóäåò ïîðîæäåíà ðåçîëüâåíòà 0,òî âûäàåì îòâåò: Èñõîäíàÿ 2-ÊÍÔ íåâûïîëíèìà, èíà÷å âûäàåì îòâåò:Èñõîäíàÿ 2-ÊÍÔ âûïîëíèìà.Äîêàçàòåëüñòâî.Ëåììà 4.22.
Àëãîðèòì îáÿçàòåëüíî îñòàíîâèòñÿ è ðàáîòàåòïîëèíîìèàëüíîå âðåìÿ.Åñëè äëèíà èñõîäíîé 2-ÊÍÔ ðàâíà n, òî â íåé íåáîëåå n ïåðåìåííûõ, èç êîòîðûõ ìîæíî ïîñòðîèòü íå áîëåå (2n + 1)2äèçúþíêòîâ ñ îäíîé èëè äâóìÿ ïåðåìåííûìè. Ïîýòîìó ïîèñê íîâûõðåçîëüâåíò áóäåò ïîâòîðÿòüñÿ íå áîëåå (2n + 1)2 ðàç, ïðè ýòîì ÷èñëîïðîñìàòðèâàåìûõ ïàð äèçúþíêòîâ íå ïðåâîñõîäèò (2n + 1)4 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
