С.С. Марченков - Избранные главы дискретной математики (1124120), страница 21
Текст из файла (страница 21)
. , vs ) = (v1 ∨ . . . ∨ vs ) &&i6=j(v̄i ∨ v̄j ) .Äëèíà ÊÍÔ ýòîé ôóíêöèè (÷èñëî âõîæäåíèé ïåðåìåííûõ) ðàâíà s2 . Ñïîìîùüþ ôóíêöèè h âûðàçèì óñëîâèå (4.16) â âèäå ÊÍÔ:F1 =&((06t6p(n)&−p(n)6i6p(n)h(xti,0 , xti,1 , . . . , xti,k ))&ttt&h(y−p(n), y−p(n)+1, . . . , yp(n)) & h(z0t , z1t , . . . , zrt )).Ó÷èòûâàÿ ñëîæíîñòü ÊÍÔ ôóíêöèè h, ïîëó÷àåì, ÷òî äëèíà ÊÍÔ ôîðìóëû F1 ðàâíà(p(n) + 1)((2p(n) + 1)(k + 1)2 + (2p(n) + 1)2 + (r + 1)2 ),ò.å.
ÿâëÿåòñÿ ïîëèíîìîì îò n (k è r ñóòü êîíñòàíòû, çàâèñÿùèå òîëüêîîò ìàøèíû M).Ïåðåéäåì ê óñëîâèþ 2. Áóäåì ïðåäïîëàãàòü, ÷òî íàáîð ïåðåìåííûõtxi,j , yit , zlt êîððåêòíî çàäàåò êîíôèãóðàöèþ K0 . Ïóñòü ā = aj1 aj2 . . . ajn .Òîãäà óñëîâèå 2 ìîæíî âûðàçèòü ñëåäóþùåé ÊÍÔ:F2 = x00,j1 & x01,j2 & . . . & x0n−1,jn &&−p(n)6i6−1Ôîðìóëà F2 èìååò ñëîæíîñòü 2p(n) + 3.97 x0i,0 &&n6i6p(n)x0i,0 & y00 & z10 .p(n)Óñëîâèå 3 âûðàæàåòñÿ ÊÍÔ èç îäíîé ïåðåìåííîé: z0 .Ðàññìîòðèì óñëîâèå 4.
Êîìàíäû ìàøèíû M ïðåäñòàâèì â âèäåaj ql → {aσ(j,l) D(j, l)qτ (j,l) },ãäå ïîñðåäñòâîì aσ(j,l) D(j, l)qτ (j,l) îáîçíà÷åíà ¾îáùàÿ¿ ïðàâàÿ ÷àñòü êîìàíäû ñ ëåâîé ÷àñòüþ aj ql (íàïîìíèì, ÷òî ìàøèíà M íåäåòåðìèíèðîâàííà) è D(j, l) = −1, 0, 1 â çàâèñèìîñòè îò äâèæåíèÿ ãîëîâêè ìàøèíûM íà ëåíòå. Ñ÷èòàÿ, ÷òî íàáîð ïåðåìåííûõ xti,j , yit , zlt êîððåêòíî çàäàåòêîíôèãóðàöèè K0 , K1 , .
. . , Kp(n) , çàïèøåì óñëîâèå 4 â âèäå ñëåäóþùåéôîðìóëû:F40 =&&& & ((x & y & z ⇒) & (ȳ ⇒ & (x ∼ x ))),06t6p(n)−1 −p(n)6i6p(n) 06j6k 06l6rt+1t+1∨xt+1i,σ(j,l) & yi+D(j,l) & zτ (j,l)ti06j6kti,jtit+1i,jtlti,jãäå äèçúþíêöèÿ âî âòîðîé ñòðîêå ôîðìóëû áåðåòñÿ ïî âñåì êîìàíäàì,èìåþùèì ëåâóþ ÷àñòü aj ql . Ïåðâàÿ èìïëèêàöèÿ ýòîé ôîðìóëû ïîêàçûâàåò, êàêèìè â ìîìåíò t + 1 áóäóò ñèìâîëû íà ëåíòå, äâèæåíèå ãîëîâêèè íîâîå ñîñòîÿíèå, âòîðàÿ ÷òî ñèìâîëû âî âñåõ îñòàëüíûõ êëåòêàõîñòàþòñÿ áåç èçìåíåíèÿ. Ïåðâàÿ èìïëèêàöèÿ çàâèñèò íå áîëåå ÷åì îò3((k + 1)(r + 1) + 1) ïåðåìåííûõ, âòîðàÿ îò 2k + 3 ïåðåìåííûõ. Êàæäóþ èç íèõ ìîæíî ïðèâåñòè ê ÊÍÔ, ñóììàðíàÿ ñëîæíîñòü C ýòèõ ÊÍÔáóäåò çàâèñåòü òîëüêî îò k, r.
 ðåçóëüòàòå ôîðìóëà F40 ïðåîáðàçóåòñÿ âÊÍÔ F4 äëèíûCp(n)(2p(n) + 1)(k + 1)(r + 1).ÏîëîæèìFā = F1 & F2 & F3 & F4 .Òîãäà Fā ÊÍÔ, êîòîðàÿ íà íàáîðå ïåðåìåííûõ ({xti,j }, {yit }, {zlt }) ïðèíèìàåò çíà÷åíèå 1 òîãäà è òîëüêî òîãäà, êîãäà äëÿ âõîäíîãî ñëîâà ā íàáîðçíà÷åíèé ïåðåìåííûõ êîððåêòíî îïðåäåëÿåò âû÷èñëåíèå íà ìàøèíå M,ïðèâîäÿùåå ê çàêëþ÷èòåëüíîìó ñîñòîÿíèþ q0 . Äëèíà ôîðìóëû Fā îãðàíè÷åíà ñâåðõó íåêîòîðûì ïîëèíîì îò n (íàïîìíèì, ÷òî n = |ā|). Ïðèýòîì íåòðóäíî çàìåòèòü, ÷òî ñàìà ôîðìóëà Fā ýôôåêòèâíî îïðåäåëÿåòñÿïî ïðîãðàììå ìàøèíû M è âûïèñûâàåòñÿ çà âðåìÿ, îãðàíè÷åííîå ïîëèíîìîì îò åå äëèíû, ò.å.
ïîëèíîìîì îò äëèíû ñëîâà ā. Òàêèì îáðàçîì,îòîáðàæåíèå ā → Fā îïðåäåëÿåò ïîëèíîìèàëüíîå ñâåäåíèå ìíîæåñòâàL ê ìíîæåñòâó ÂÛÏ. Çíà÷èò, ÂÛÏ NP-òðóäíàÿ çàäà÷à. À ïîñêîëüêó98ÂÛÏ ∈ NP, ïðèõîäèì ê çàêëþ÷åíèþ, ÷òî ÂÛÏ NP-ïîëíàÿ çàäà÷à.Òåîðåìà äîêàçàíà.Êîíúþíêòèâíóþ íîðìàëüíóþ ôîðìó, ó êîòîðîé ëþáàÿ äèçúþíêöèÿñîäåðæèò íå áîëåå òðåõ ñëàãàåìûõ, íàçîâåì 3-ÊÍÔ. Çàäà÷à 3-ÂÛÏÎËÍÈÌÎÑÒÜ (ñîêðàùåííî 3-ÂÛÏ) ïðåäñòàâëÿåò ñîáîé âàðèàíò çàäà÷èÂÛÏÎËÍÈÌÎÑÒÜ, êîãäà ìíîæåñòâî ðàññìàòðèâàåìûõ ÊÍÔ îãðàíè÷åíî 3-ÊÍÔ.Òåîðåìà 4.4.Çàäà÷à 3-ÂÛÏ ÿâëÿåòñÿ NP-ïîëíîé.Ââèäó óòâåðæäåíèÿ 4.2 çàäà÷à 3-ÂÛÏ ïðèíàäëåæèò êëàññó NP.
Ìû ïîêàæåì, ÷òî çàäà÷à ÂÛÏ P-ñâîäèòñÿ ê çàäà÷å 3ÂÛÏ. Òîãäà â ñèëó òåîðåìû 4.3 è òðàíçèòèâíîñòè P-ñâîäèìîñòè ëþáîåìíîæåñòâî èç êëàññà NP áóäåò P-ñâîäèòñÿ ê ìíîæåñòâó 3-ÂÛÏ, ò.å. çàäà÷à 3-ÂÛÏ îêàæåòñÿ NP-ïîëíîé.Ïîêàæåì, êàê ïî ïðîèçâîëüíîé ÊÍÔ K ìîæíî ýôôåêòèâíî è ïîëèíîìèàëüíî (ïî âðåìåíè) îïðåäåëèòü 3-ÊÍÔ ϕ(K) òàê, ÷òî áóäåò ñïðàâåäëèâà ýêâèâàëåíòíîñòüÄîêàçàòåëüñòâî.K âûïîëíèìà ⇔ ϕ(K) âûïîëíèìà.Ïóñòü K = D1 &. . .&Ds , ãäå D1 , . .
. , Ds äèçúþíêöèè îò ïåðåìåííûõx1 , . . . , xn . Åñëè äèçúþíêöèÿ Di ñîäåðæèò íå áîëåå òðåõ ïåðåìåííûõ, òîîñòàâëÿåì åå áåç èçìåíåíèÿ. Ïóñòü òåïåðü Di = t1 ∨ t2 ∨ . . . ∨ tm , ãäåt1 , . . . , tm ëèòåðàëû è m > 4. ÏîëîæèìFi = (t1 ∨ t2 ∨ y1 ) & (ȳ1 ∨ t3 ∨ y2 ) & (ȳ2 ∨ t4 ∨ y3 ) & . . .. . . & (ȳm−4 ∨ tm−2 ∨ ym−3 ) & (ȳm−3 ∨ tm−1 ∨ tm ),ãäå y1 , . . .
, ym−3 ïåðåìåííûå, îòëè÷íûå îò ïåðåìåííûõ x1 , . . . , xn . Çàìåòèì, ÷òî ñëîæíîñòü ÊÍÔ Fi íå áîëåå ÷åì â òðè ðàçà ïðåâîñõîäèò ñëîæíîñòü äèçúþíêöèè Di .Ïîêàæåì, ÷òî èç ðàâåíñòâà Fi = 1 ñëåäóåò ðàâåíñòâî Di = 1. ÏóñòüFi (ã, b̃) = 1, ãäå ã = (a1 , . . . , an ), b̃ = (b1 , . . . , bm−3 ). Åñëè b1 = 0, òît1 (ã) ∨ t2 (ã) = 1 è, ñëåäîâàòåëüíî, Di (ã) = 1. Åñëè bm−3 = 1, òî tm−1 (ã) ∨tm (ã) = 1 è, çíà÷èò, âíîâü Di (ã) = 1.Ïóñòü b1 = 1 è bm−3 = 0. Òîãäà íàéäåòñÿ òàêîå k , ÷òî bk = 1 è bk+1 = 0.Òàê êàê äîëæíî áûòü b̄k ∨tk+2 (ã)∨bk+1 = 1, òî ïîëó÷àåì, ÷òî tk+2 (ã) = 1.Îòêóäà Di (ã) = 1.Îáðàòíî, ïóñòü Di (ã) = 1. Òîãäà ñóùåñòâóåò òàêîå k , ÷òî tk (ã) = 1.Åñëè k = 1 èëè k = 2, òî âûáèðàåì b1 = b2 = .
. . = bm−3 = 0 è ïîëó÷àåì99Fi (ã, b̃) = 1. Åñëè k = m − 1 èëè k = m, òî âûáèðàåì b1 = b2 = . . . =bm−3 = 1 è âíîâü ïðèõîäèì ê ðàâåíñòâó Fi (ã, b̃) = 1.  îñòàëüíûõ ñëó÷àÿõäëÿ äîñòèæåíèÿ ðàâåíñòâà Fi (ã, b̃) = 1 ïîëàãàåì b1 = b2 = . . . = bk−2 = 1è bk = . . . = bm−3 = 0.Ïðè ïîñòðîåíèè 3-ÊÍÔ Fi äëÿ ðàçëè÷íûõ i èñïîëüçóåì ðàçëè÷íûåíàáîðû ïåðåìåííûõ ỹ .  ðåçóëüòàòå îïèñàííûõ ïîñòðîåíèé ÊÍÔ K çàïîëèíîìèàëüíîå ÷èñëî øàãîâ áóäåò ïðåîáðàçîâàíà â 3-ÊÍÔ F1 & . .
. & Fs ,êîòîðàÿ è áóäåò óäîâëåòâîðÿòü òðåáîâàíèÿì òåîðåìû.Ïî àíàëîãèè ñ 3-ÊÍÔ è 3-ÂÛÏÎËÍÈÌÎÑÒÜÞ ââîäèì ïîíÿòèÿ 2ÊÍÔ è 2-ÂÛÏÎËÍÈÌÎÑÒÈ.Òåîðåìà 4.5.Çàäà÷à 2-ÂÛÏ ïîëèíîìèàëüíî ðàçðåøèìà, ò.å. ïðè-íàäëåæèò êëàññó P.ðåçîëüâåíòîéÍàçîâåìäèçúþíêòîâ xi ∨ t1 è x̄i ∨ t2äèçúþíêò D = t1 ∨ t2 (â ñëó÷àå îòñóòñòâèÿ îäíîãî èç ëèòåðàëîâ t1 , t2äèçúþíêò D ñîâïàäàåò ñî âòîðûì ëèòåðàëîì; â ñëó÷àå îòñóòñòâèÿ îáîèõëèòåðàëîâ t1 , t2 äèçúþíêò D ñ÷èòàåòñÿ ïóñòûì).Ëåãêî ïðîâåðÿåòñÿ, ÷òî äëÿ ëþáûõ ôîðìóë A, B ñïðàâåäëèâî ðàâåíñòâîÄîêàçàòåëüñòâî.(xi ∨ A) & (x̄i ∨ B) = (xi ∨ A) & (x̄i ∨ B) & (A ∨ B).Òàêèì îáðàçîì, äîáàâëåíèå ê 2-ÊÍÔ ðåçîëüâåíòû ëþáîé ïàðû äèçúþíêòîâ íå ìåíÿåò ôóíêöèþ, ðåàëèçóåìóþ äàííîé 2-ÊÍÔ.Ïóñòü çàäàíà 2-ÊÍÔ K . Áóäåì ïðîñìàòðèâàòü â K âñå ïàðû äèçúþíêòîâ è äîáàâëÿòü (êîíúþíêòèâíî) ê K èõ ðåçîëüâåíòû.
Ýòó ïðîöåäóðó áóäåì ïîâòîðÿòü äî òåõ ïîð, ïîêà íå ïåðåñòàíóò ïîÿâëÿòüñÿ íîâûåäèçúþíêòû. Åñëè ïðè ýòîì áóäåò ïîðîæäåí ïóñòîé äèçúþíêò (êîòîðûéïîÿâëÿåòñÿ òîëüêî èç ïàðû äèçúþíêòîâ âèäà xi è x̄i ), òî, î÷åâèäíî, èñõîäíàÿ 2-ÊÍÔ K íåâûïîëíèìà.  ïðîòèâíîì ñëó÷àå, êàê ìû óñòàíîâèìíèæå, îíà âûïîëíèìà.Îöåíèì ïðåæäå âñåãî òðóäîåìêîñòü ïðåäëîæåííîãî àëãîðèòìà. Åñëèäëèíà èñõîäíîé 2-ÊÍÔ ðàâíà n, òî îíà ñîäåðæèò íå áîëåå n ïåðåìåííûõ,èç êîòîðûõ ìîæíî ïîñòðîèòü íå áîëåå (2n + 1)2 äèçúþíêòîâ ñ îäíîéèëè äâóìÿ ïåðåìåííûìè.
Ïîýòîìó ïîðîæäåíèå íîâûõ ðåçîëüâåíò áóäåòïðîèñõîäèòü íå áîëåå (2n+1)2 ðàç. Ïðè ýòîì ÷èñëî ïðîñìàòðèâàåìûõ ïàðäèçúþíêòîâ íå ïðåâîñõîäèò (2n + 1)4 . Ñëåäîâàòåëüíî, îïèñàííûé âûøåàëãîðèòì ïîëèíîìèàëåí.Èòàê, ïðåäïîëîæèì, ÷òî 2-ÊÍÔ K íå ñîäåðæèò ïóñòûõ äèçúþíêòîâè çàìêíóòà îòíîñèòåëüíî îïåðàöèè âçÿòèÿ ðåçîëüâåíò. Ïîêàæåì, ÷òî â100ýòîì ñëó÷àå îíà âûïîëíèìà. Äîêàçàòåëüñòâî ïðîâåäåì ïî ÷èñëó n ïåðåìåííûõ, âõîäÿùèõ â K .: n = 1.
Òîãäà K = xi èëè K = x̄i , è óòâåðæäåíèåòðèâèàëüíî âåðíî.Ïóñòü óòâåðæäåíèå âåðíî äëÿ âñåõ 2-ÊÍÔ ñn < m ïåðåìåííûìè è ïóñòü 2-ÊÍÔ K ñîäåðæèò m ïåðåìåííûõ. Ïðåäñòàâèì K â âèäå (äëÿ óïðîùåíèÿ çàïèñè çíàê & îïóñêàåì)Áàçèñ èíäóêöèèÈíäóêòèâíûé ïåðåõîä.K = (xm ∨t1 )(xm ∨t2 ) . . .
(xm ∨tk )(x̄m ∨t01 )(x̄m ∨t02 ) . . . (x̄m ∨t0l )·C1 ·C2 ·. . .·Cr ,ãäå ti , t0j ëèòåðàëû ëèáî 0, à C1 · C2 · . . . · Cr 2-ÊÍÔ îò ïåðåìåííûõx1 , . . . , xm−1 , çàìêíóòàÿ îòíîñèòåëüíî îïåðàöèè âçÿòèÿ ðåçîëüâåíò. Ïîïðåäïîëîæåíèþ èíäóêöèè ñóùåñòâóåò íàáîð ã = (a1 , .
. . , am−1 ), íà êîòîðîì ÊÍÔ C1 · . . . · Cr ðàâíà 1. Åñëè ñóùåñòâóþò òàêèå ëèòåðàëû ti , t0j , ÷òîti (ã) = t0j (ã) = 0, òî òàêæå ti (ã) ∨ t0j (ã) = 0. Îäíàêî ti ∨ t0j ðåçîëüâåíòàäèçúþíêòîâ xm ∨ ti è x̄m ∨ t0j . Ïîýòîìó äèçúþíêò ti ∨ t0j ñîäåðæèòñÿ ñðåäè äèçúþíêòîâ C1 , . . . , Cr . Ïîëó÷àåì, ÷òî äëÿ íåêîòîðîãî v âûïîëíÿåòñÿðàâåíñòâî Cv (ã) = 0, ÷òî íåâîçìîæíî.Òàêèì îáðàçîì, ëèáî t1 (ã) = . . . = tk (ã) = 1, ëèáî t01 (ã) = . .
. = t0l (ã) =1.  ïåðâîì ñëó÷àå ÊÍÔ K âûïîëíèìà íà íàáîðå (ã, 0), âî âòîðîì íàíàáîðå (ã, 1). Òåîðåìà äîêàçàíà.ÓÏÐÀÆÍÅÍÈßÄîêàçàòü NP-ïîëíîòó ñëåäóþùèõ çàäà÷:1) çàäà÷à ÊËÈÊÀ;2) çàäà÷à ÂÅÐØÈÍÍÎÅ ÏÎÊÐÛÒÈÅ (ñì. çàäà÷ó 15.1).17. Äîêàçàòü NP-ïîëíîòó ñëåäóþùèõ çàäà÷:1) ñóùåñòâîâàíèå äâóõ ïðîòèâîïîëîæíûõ íàáîðîâ, íà êîòîðûõ ÄÍÔîáðàùàåòñÿ â íóëü;2) ðàñïîçíàâàíèå íåëèíåéííîñòè áóëåâîé ôóíêöèè, çàäàííîé â âèäåÄÍÔ;3) ðàñïîçíàâàíèå íåìîíîòîííîñòè áóëåâîé ôóíêöèè, çàäàííîé â âèäåÄÍÔ;4) ðàñïîçíàâàíèå íåñàìîäâîéñòâåííîñòè áóëåâîé ôóíêöèè, çàäàííîé ââèäå ÄÍÔ.16.101 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
