С.С. Марченков - Избранные главы дискретной математики (1124120), страница 20
Текст из файла (страница 20)
Ïîýòîìó ïðåæäå ÷åì ïðèñòóïèòü ñîáñòâåííî ê ðàñïîçíàâàíèþ âûïîëíèìîñòè ôîðìóëû, ìàøèíå Òüþðèíãà ñëåäóåò îïðåäåëèòü,ÿâëÿåòñÿ ëè çàïèñàííîå ñëîâî êîäîì íåêîòîðîé ÊÍÔ. Íåòðóäíî âèäåòü,÷òî ýòó ïðîâåðêó ìîæíî âûïîëíèòü äåòåðìèíèðîâàííûì îáðàçîì è çàïîëèíîìèàëüíîå âðåìÿ.Ïðåäïîëîæèì, ÷òî íà ëåíòå ìàøèíû Òüþðèíãà ïîìèìî çàïèñè ôîðìóëû F èìååòñÿ íåêîòîðûé íàáîð (a1 , . . .
, am ) çíà÷åíèé åå ïåðåìåííûõ.Äîêàçàòåëüñòâî.92Ïîíÿòíî, ÷òî â ýòîì ñëó÷àå ñðàâíèòåëüíî ïðîñòî (äåòåðìèíèðîâàííî è çàïîëèíîìèàëüíîå âðåìÿ) ìîæíî ïðîâåðèòü, âûïîëíÿåò ëè íàáîð (a1 , . . . ,am ) ôîðìóëó F . Òàêèì îáðàçîì, çàäà÷à ñâîäèòñÿ ê òîìó, ÷òîáû íåäåòåðìèíèðîâàííî ¾óãàäàòü¿ íàáîð, âûïîëíÿþùèé ôîðìóëó F . Çàìåòèì, ÷òîòàêîãî íàáîðà ìîæåò è íå áûòü.Èòàê, ÍÌÒ, èñïîëüçóÿ çàïèñü ôîðìóëû F , ñíà÷àëà äåòåðìèíèðîâàííî ¾îòìåðÿåò¿ m êëåòîê íà ëåíòå äëÿ çàïèñè ïðåäïîëàãàåìîãî íàáîðà(a1 , . . .
, am ). Çàòåì, ïðîõîäÿ ïî ýòîìó ìàññèâó èç m (ïóñòûõ) êëåòîê, çàïèñûâàåò òàì ïðîèçâîëüíûå ñèìâîëû 0 è 1. Ýòî åäèíñòâåííûé ýòàïâ ðàáîòå ÍÌÒ, êîãäà ïî ñóùåñòâó íåîáõîäèìî âîñïîëüçîâàòüñÿ íåäåòåðìèíèðîâàííîñòüþ ìàøèíû. Çäåñü íà êàæäîì øàãå äâèæåíèÿ ïî ìàññèâóèç m êëåòîê ìàøèíà íåäåòåðìèíèðîâàííî çàïèñûâàåò â êëåòêó îäèí èçñèìâîëîâ 0 èëè 1. Çàêîí÷èâ ýòîò íåäåòåðìèíèðîâàííûé ýòàï, ìàøèíà ïåðåõîäèò ê ïðîâåðêå âûïîëíèìîñòè ôîðìóëû F íà âûïèñàííîì äâîè÷íîìíàáîðå. Óòâåðæäåíèå äîêàçàíî. êà÷åñòâå ñëåäóþùåé çàäà÷è ðàññìîòðèì çàäà÷ó ÊËÈÊÀ.: ïðîèçâîëüíûé íåîðèåíòèðîâàííûé ãðàô G è íàòóðàëüíîå ÷èñëî k .: ñóùåñòâóåò ëè â ãðàôå G êëèêà ðàçìåðà k (ò.å. ïîëíûé ïîäãðàô ñ k âåðøèíàìè).ÂõîäÂîïðîñ ýòîé çàäà÷å â êà÷åñòâå êîäèðóþùåãî àëôàâèòà ìîæíî âçÿòü, íàïðèìåð, àëôàâèò A = {0, 1, ; }, ãðàô G ìîæíî çàäàòü ìàòðèöåé ñìåæíîñòè,à çàòåì çàïèñàòü ìàòðèöó îäíèì ñëîâîì, îòäåëÿÿ ñòðîêè ðàçäåëèòåëåì;.
×èñëî k çàäàåòñÿ ñâîèì äâîè÷íûì ïðåäñòàâëåíèåì.Îñíîâíàÿ ÷àñòü ðàáîòû ÍÌÒ ñâîäèòñÿ ê íåäåòåðìèíèðîâàííîìó ôîðìèðîâàíèþ ñïèñêà èç k âåðøèí ãðàôà G è ïîñëåäóþùåé ïðîâåðêè òîãî,÷òî äàííûå âåðøèíû îáðàçóþò ïîëíûé ïîäãðàô ãðàôà G.Áëèçêîé ê çàäà÷å ÊËÈÊÀ ÿâëÿåòñÿ çàäà÷à ÃÀÌÈËÜÒÎÍΠÖÈÊË.: ïðîèçâîëüíûé íåîðèåíòèðîâàííûé ãðàô G.: ñóùåñòâóåò ëè â ãðàôå G ãàìèëüòîíîâ öèêë (ò.å. öèêë, ïðîõîäÿùèé ÷åðåç êàæäóþ âåðøèíó ãðàôà ðîâíî îäèí ðàç).ÂõîäÂîïðîñÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî ñëåäóþùèå ìíîæåñòâà ïðèíàäëåæàò êëàññó P:1) ìíîæåñòâî çíà÷åíèé ïðîèçâîëüíîãî ïîëèíîìà p(x) ñ íàòóðàëüíûìèêîýôôèöèåíòàìè (÷èñëà íà ëåíòå ìàøèíû Òüþðèíãà ïðåäñòàâëÿþòñÿ âäâîè÷íîé çàïèñè);12.932) ìíîæåñòâî ðåøåíèé óðàâíåíèÿ p1 (x1 , . .
. , xn ) = p2 (x1 , . . . , xn ) â îáëàñòè N n , ãäå p1 , p2 ïîëèíîìû ñ íàòóðàëüíûìè êîýôôèöèåíòàìè.3) ìíîæåñòâî çíà÷åíèé ôóíêöèè cx , ãäå c íàòóðàëüíîå ÷èñëî, áîëüøåå 1;4) ìíîæåñòâî êâàäðàòíûõ (0,1)-ìàòðèö ñ îïðåäåëèòåëåì, ðàâíûì 1(ñëîæåíèå ýëåìåíòîâ âûïîëíÿåòñÿ ïî ìîäóëþ 2).13. Äîêàçàòü ïðèíàäëåæíîñòü êëàññó P ñëåäóþùèõ ìíîæåñòâ:1) ìíîæåñòâî íåëèíåéíûõ áóëåâûõ ôóíêöèé, çàäàííûõ òàáëèöàìè ñâîèõ çíà÷åíèé;2) ìíîæåñòâî íåìîíîòîííûõ áóëåâûõ ôóíêöèé, çàäàííûõ òàáëèöàìèñâîèõ çíà÷åíèé ëèáî ïîëèíîìàìè Æåãàëêèíà;3) ìíîæåñòâî íåñàìîäâîéñòâåííûõ áóëåâûõ ôóíêöèé, çàäàííûõ òàáëèöàìè ñâîèõ çíà÷åíèé ëèáî ñîâåðøåííûìè ÄÍÔ.14. Äîêàçàòü, ÷òî êëàññó NP ïðèíàäëåæàò ñëåäóþùèå çàäà÷è:1) ñóùåñòâîâàíèå äâîè÷íîãî íàáîðà, íà êîòîðîì çàäàííàÿ ÄÍÔ îáðàùàåòñÿ â íóëü;2) íåëèíåéíîñòü áóëåâîé ôóíêöèè, çàäàííîé â âèäå ÄÍÔ;3) íåìîíîòîííîñòü áóëåâîé ôóíêöèè, çàäàííîé â âèäå ÄÍÔ;4) íåñàìîäâîéñòâåííîñòü áóëåâîé ôóíêöèè, çàäàííîé â âèäå ÄÍÔ.15.
Äîêàçàòü ïðèíàäëåæíîñòü êëàññó NP ñëåäóþùèõ çàäà÷:1) ÂÅÐØÈÍÍÎÅ ÏÎÊÐÛÒÈÅ.: ãðàô G = (V, E) è íàòóðàëüíîå ÷èñëî l.: ñóùåñòâóåò ëè òàêîå òàêîå ìíîæåñòâî R ⊆ V , ÷òî |R| 6 l èêàæäîå ðåáðî ãðàôà G èíöèäåíòíî íåêîòîðîé âåðøèíå èç R.2) ÏÎÊÐÛÒÈÅ ÌÍÎÆÅÑÒÂ.: ñåìåéñòâî F = {S1 , . . . , Sm } ïîäìíîæåñòâ ìíîæåñòâà S , ãäå S1 ∪.
. . ∪ Sm = S , è íàòóðàëüíîå ÷èñëî h.: ñóùåñòâóåò ëè òàêîå òàêîå ïîäñåìåéñòâî T ⊆ S , ÷òî |T | 6 hè ∪Sj = S , ãäå îáúåäèíåíèå áåðåòñÿ ïî âñåì ìíîæåñòâàì Sj èç T .3) ÐÀÑÊÐÀÑÊÀ.: ãðàô G = (V, E) è íàòóðàëüíîå ÷èñëî k .: ñóùåñòâóåò ëè òàêàÿ ôóíêöèÿ χ : V → {1, 2, . . . , k}, ÷òîχ(u) 6= χ(v) äëÿ ëþáîãî ðåáðà (u, v) èç E .ÂõîäÂîïðîñÂõîäÂîïðîñÂõîäÂîïðîñ 7. NP-ïîëíîòà.
Òåîðåìà ÊóêàÍåòðóäíî âèäåòü, ÷òî èìååò ìåñòî âêëþ÷åíèå P ⊆ NP. ßâëÿåòñÿ ëèýòî âêëþ÷åíèå ñîáñòâåííûì? Ýòîò âîïðîñ ïðåäñòàâëÿåò ñîáîé îäíó èç94íàèáîëåå èíòåðåñíûõ ïðîáëåì ñîâðåìåííîé òåîðèè ñëîæíîñòè âû÷èñëåíèé. Íåñìîòðÿ íà ìíîãî÷èñëåííûå ïîïûòêè ðåøèòü ñôîðìóëèðîâàííóþïðîáëåìó, ïðåäïðèíÿòûå â òå÷åíèå áîëåå ÷åì 40 ëåò, ñêîëüêî-íèáóäü ñóùåñòâåííûõ ïðîäâèæåíèé â ýòîì íàïðàâëåíèè ïîêà íå ïîëó÷åíî. Áîëüøèíñòâî ñïåöèàëèñòîâ ñêëîíÿþòñÿ ê ìíåíèþ, ÷òî P 6= NP.  ñâÿçè ñ ýòèìâûçûâàåò èíòåðåñ îïðåäåëåíèå â êëàññå NP íåêîòîðûõ ¾êëþ÷åâûõ¿ çàäà÷ çàäà÷, êîòîðûå ¾ñîäåðæàò¿ â ñåáå âñå çàäà÷è èç NP. Èñïîëüçóÿ ïîíÿòèåP-ñâîäèìîñòè, ìû õîòèì äëÿ ýòèõ öåëåé ââåñòè ïîíÿòèå NP.Íàçîâåì ìíîæåñòâî L NP, åñëè ëþáîå ìíîæåñòâî èç êëàññàNP P-ñâîäèòñÿ ê ìíîæåñòâó L.
Íàçîâåì ìíîæåñòâî L NP, åñëèL NPè L ∈ NP.Âîçíèêàåò âîïðîñ: ñóùåñòâóþò ëè âîîáùå NP-ïîëíûå ìíîæåñòâà? Îòâåò íà ýòîò âîïðîñ äàåò ñëåäóþùàÿ òåîðåìà Ñ. Êóêà [?, ?].òðóäíûìòðóäíîÒåîðåìà 4.3.ïîëíîòûïîëíûìÇàäà÷à ÂÛÏ ÿâëÿåòñÿ NP-ïîëíîé.Âêëþ÷åíèå ÂÛÏ ∈ NP óñòàíîâëåíî â óòâåðæäåíèè 4.2. Ïîýòîìó îñòàåòñÿ ïîêàçàòü, ÷òî ëþáîå ìíîæåñòâî L èç NP ïîëèíîìèàëüíî ñâîäèòñÿ ê ìíîæåñòâó ÂÛÏ.Ïóñòü L åñòü ìíîæåñòâî ñëîâ â àëôàâèòå A1 = {a1 , . . . , ak } è L ∈ NP.Òîãäà íàéäóòñÿ òàêàÿ íåäåòåðìèíèðîâàííàÿ ìàøèíà Òüþðèíãà M è ïîëèíîì p ñ íàòóðàëüíûìè êîýôôèöèåíòàìè, ÷òî ìàøèíà M ðàñïîçíàåòìíîæåñòâî L çà âðåìÿ p(n).
Èíûìè ñëîâàìè, åñëè ā ∈ L è ñëîâî ā èìååò äëèíó n, òî äëÿ ā ñóùåñòâóåò äîïóñêàþùåå âû÷èñëåíèå ìàøèíû Mäëèíû íå áîëåå p(n). Åñëè æå ā ∈/ L, òî äîïóñêàþùåãî âû÷èñëåíèÿ äëÿñëîâà ā íå ñóùåñòâóåò.Ïîêàæåì, ÷òî ìíîæåñòâî L P-ñâîäèòñÿ ê ìíîæåñòâó ÂÛÏ. Ïóñòü B àëôàâèò çàäà÷è ÂÛÏ. Íàì íåîáõîäèìî îïðåäåëèòü òàêóþ ïîëèíîìèàëüíî âû÷èñëèìóþ ôóíêöèþ ϕ : A∗1 → B ∗ (çíà÷åíèåì êîòîðîé âñåãäàÿâëÿåòñÿ ÊÍÔ), ÷òîÄîêàçàòåëüñòâî.ā ∈ L ⇔ ϕ(ā) = Fā − âûïîëíèìàÿ ÊÍÔ.Áóäåì ïðåäïîëàãàòü, ÷òî â íà÷àëüíûé ìîìåíò âðåìåíè íà ëåíòå ìàøèíû M çàïèñàíî ñëîâî ā (îñòàëüíàÿ ÷àñòü ëåíòû çàïîëíåíà ñèìâîëàìèa0 ), ìàøèíà íàõîäèòñÿ â ñîñòîÿíèè q1 è ãîëîâêà ìàøèíû óñòàíîâëåíà íàïåðâóþ áóêâó ñëîâà ā.
Ïóñòü n = |ā|. Òîãäà â ñëó÷àå ā ∈ L ó ìàøèíûM èìååòñÿ âû÷èñëåíèå, ïðèâîäÿùåå â çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 çàíå áîëåå ÷åì p(n) øàãîâ. Åñëè æå ā ∈/ L, òî íèêàêîå âû÷èñëåíèå ìàøèíûM íå ïåðåâîäèò åå â çàêëþ÷èòåëüíîå ñîñòîÿíèå.95Ïðåîáðàçóåì ìàøèíó M òàêèì îáðàçîì, ÷òîáû ïîñëå ïîïàäàíèÿ âçàêëþ÷èòåëüíîå ñîñòîÿíèå îíà îñòàâàëàñü áû òàì ïîñòîÿííî, íå ìåíÿÿñîäåðæèìîãî ëåíòû è íå ñäâèãàÿ ãîëîâêó. Ôîðìàëüíî ïî äîñòèæåíèèçàêëþ÷èòåëüíîãî ñîñòîÿíèÿ ìàøèíà M ïðîäîëæàåò ðàáîòó áåñêîíå÷íîäîëãî. Òîãäà äëÿ ëþáîãî ñëîâà ā ∈ A∗1 äëèíû n áóäåì èìåòüā ∈ L ⇔ ìàøèíà M, íà÷èíàÿ ðàáîòó íà ñëîâå ā, â ìîìåíò âðåìåíè p(n)áóäåò íàõîäèòüñÿ â ñîñòîÿíèè q0 .(4.14)Íàøà öåëü çàïèñàòü ïðàâóþ ÷àñòü ýêâèâàëåíòíîñòè (4.14) â âèäåÊÍÔ Fā òàê, ÷òîáû ôîðìóëà Fā áûëà âûïîëíèìîé â òîì è òîëüêî òîìñëó÷àå, êîãäà èñòèííà ïðàâàÿ ÷àñòü ýòîé ýêâèâàëåíòíîñòè.Íàïîìíèì, ÷òî êîíôèãóðàöèåé ìàøèíû M â ìîìåíò âðåìåíè t ìûíàçâàëè òðîéêó, ñîñòîÿùóþ èç ñëîâà, çàïèñàííîãî íà ëåíòå â ìîìåíò t,ñîñòîÿíèÿ ìàøèíû M â ìîìåíò t è ïîëîæåíèÿ åå ãîëîâêè â ýòîò ìîìåíòâðåìåíè.
Ïóñòü Kt îáîçíà÷àåò êîíôèãóðàöèþ ìàøèíû M â ìîìåíò t.Çàïèøåì ýêâèâàëåíòíîñòü (4.14) â áîëåå ïîäðîáíîé ôîðìå:ā ∈ L ⇔ (∃K0 )(∃K1 ) . . . (∃Kp(n) )(K0 íà÷àëüíàÿ êîíôèãóðàöèÿ ìàøèíûM äëÿ ñëîâà ā, êîíôèãóðàöèÿ Kp(n) ñîäåðæèò çàêëþ÷èòåëüíîå ñîñòîÿíèåq0 è äëÿ âñÿêîãî j (0 6 j 6 p(n) − 1) êîíôèãóðàöèÿ Kj+1 ïîëó÷àåòñÿ èçêîíôèãóðàöèè Kj çà îäèí òàêò ðàáîòû ìàøèíû M).(4.15)Ïóñòü êëåòêè íà ëåíòå ìàøèíû M çàíóìåðîâàíû öåëûìè ÷èñëàìèñëåâà íàïðàâî, ïðè÷åì êëåòêà, â êîòîðîé ìàøèíà M íàõîäèòñÿ â íà÷àëüíûé ìîìåíò âðåìåíè, èìååò íîìåð 0.
Òîãäà çà p(n) øàãîâ ðàáîòûìàøèíû M ãîëîâêà ìîæåò ïîáûâàòü òîëüêî â êëåòêàõ ñ íîìåðàìè îò−p(n) äî p(n). Ïîýòîìó â êîíôèãóðàöèÿõ K0 , K1 , . . . , Kp(n) áóäóò ó÷èòûâàòüñÿ òîëüêî ýòè êëåòêè.Ââåäåì áóëåâû ïåðåìåííûå xti,j , yit , zlt , ãäå−p(n) 6 i 6 p(n),0 6 j 6 k,0 6 l 6 r,0 6 t 6 p(n).Ñîäåðæàòåëüíî ýòèì ïåðåìåííûì ìû ïðèäàäèì ñëåäóþùèé ñìûñë:(xti,j = 1) ⇔ i-ÿ êëåòêà êîíôèãóðàöèè Kt ñîäåðæèò áóêâó aj ;(yit = 1) ⇔ â êîíôèãóðàöèè Kt ãîëîâêà ìàøèíû îáîçðåâàåò êëåòêó ñíîìåðîì i;(zlt = 1) ⇔ êîíôèãóðàöèÿ Kt ñîäåðæèò ñîñòîÿíèå ql .Èñêîìàÿ ôîðìóëà Fā áóäåò çàâèñåòü îò âñåõ ïåðåìåííûõ xti,j , yit , zlt .Ìû õîòèì, ÷òîáû ôîðìóëà Fā ïðèíèìàëà çíà÷åíèå 1 íà íåêîòîðîì äâîè÷íîì íàáîðå òîãäà è òîëüêî òîãäà, êîãäà961) äàííûé íàáîð êîððåêòíî çàäàåò ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèéK0 , K1 , .
. . , Kp(n) ìàøèíû Òüþðèíãà M;2) êîíôèãóðàöèÿ K0 ÿâëÿåòñÿ ïðàâèëüíîé íà÷àëüíîé êîíôèãóðàöèåéäëÿ ñëîâà ā;3) êîíôèãóðàöèÿ Kp(n) ñîäåðæèò ñîñòîÿíèå q0 ;4) äëÿ âñÿêîãî j (0 6 j 6 p(n) − 1) êîíôèãóðàöèÿ Kj+1 ïîëó÷àåòñÿ èçêîíôèãóðàöèè Kj ñîãëàñíî ïðîãðàììå ìàøèíû M çà îäèí òàêò ðàáîòû.Ðàññìîòðèì óñëîâèå 1.
Íåòðóäíî âèäåòü, ÷òî åãî ìîæíî âûðàçèòü ñëåäóþùèì îáðàçîì: ïðè ëþáîì t (0 6 t 6 p(n))äëÿ ëþáîãî i ðîâíî îäíà èç ïåðåìåííûõ xti,j ïðèíèìàåò çíà÷åíèå 1,ðîâíî îäíà èç ïåðåìåííûõ yit ïðèíèìàåò çíà÷åíèå 1,ðîâíî îäíà èç ïåðåìåííûõ zlt ïðèíèìàåò çíà÷åíèå 1.(4.16)Îáîçíà÷èì ÷åðåç h(v1 , . . . , vs ) áóëåâó ôóíêöèþ, ïðèíèìàþùóþ çíà÷åíèå 1 òîëüêî íà íàáîðàõ ñ îäíîé åäèíè÷íîé êîìïîíåíòîé. Èìååìh(v1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
