1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 19
Текст из файла (страница 19)
Ïîíÿòèå îá NPïîëíûõ ïðîáëåìàõ107áóäåì óïîòðåáëÿòü ñëîâà ìíîæåñòâî è ïðîáëåìà êàê ñèíîíèìû.Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî A ⊆ A∗ ïîëèíîìèàëüíî ñâîäèòñÿ êB ⊆ B∗ , ãäå A, B êîíå÷íûå àëôàâèòû, åñëè ñóùåñòâóþò ïîëèíîì p(x)ñ íàòóðàëüíûìè êîýôôèöèåíòàìè è ìàøèíà Òüþðèíãà M ïåðåðàáàòûâàþùàÿ êàæäîå ñëîâî w ∈ A∗ çà íå áîëåå, ÷åì p(|w|) øàãîâ â ñëîâî w0òàêîå, ÷òî w ∈ A ⇔ w0 ∈ B .Èçâåñòíî, ÷òî ñóùåñòâóþò ìíîæåñòâà èç NP, ê êîòîðûì ïîëèíîìèàëüíî ñâîäèòñÿ ëþáûå ìíîæåñòâà èç NP.
Òàêèå ìíîæåñòâà íàçûâàþòñÿNPïîëíûìè. Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî âñå îíè ïîëèíîìèàëüíî ñâîäÿòñÿ äðóã ê äðóãó. Â íàñòîÿùåå âðåìÿ íåèçâåñòíî, ñóùåñòâóåò ëè ïîëèíîìèàëüíûé àëãîðèòì äëÿ ðåøåíèÿ òàêèõ çàäà÷. Ýòî îäíà èç âàæíåéøèõ íåðåøåííûõ ïðîáëåì ñîâðåìåííîé ìàòåìàòèêè, êîòîðàÿ íàçûâàåòñÿïðîáëåìîé ïåðåáîðà èëè ïðîáëåìîé P=NP?.Âàæíîñòü ïîèñêà ðåøåíèÿ ýòîé ïðîáëåìû ìîæíî ïðîäåìîíñòðèðîâàòü íà ñëåäóþùåì ïðèìåðå. Ïðåäïîëîæèì, ÷òî ìû ïåðåäàåì ïî êîìïüþòåðíîé ñåòè íåêîòîðóþ âàæíóþ çàøèôðîâàííóþ èíôîðìàöèþ (íàïðèìåð, ôèíàíñîâóþ).
Äëÿ ðàñøèôðîâêè ýòîé èíôîðìàöèè ìû èñïîëüçóåìíåêîòîðûé êëþ÷, êîòîðûé ÿâëÿåòñÿ ñëîâîì íàä àëôàâèòîì èç äâóõ ñèìâîëîâ äëèíû, ñêàæåì, 100. Ðàñïîëàãàÿ ýòèì êëþ÷îì, ìû ìîæåì î÷åíüáûñòðî ðàñøèôðîâàòü ýòó èíôîðìàöèþ. Çëîóìûøëåííèê, æåëàþùèéâîñïîëüçîâàòüñÿ ýòîé èíôîðìàöèåé, â ïðèíöèïå ìîã áû ïîïûòàòüñÿ ðàñøèôðîâàòü ýòî ñîîáùåíèå, ïåðåáðàâ 2100 âàðèàíòîâ êëþ÷åé. Ýòà çàäà÷ààëãîðèòìè÷åñêè ðàçðåøèìà, íî åñëè äàæå çëîóìûøëåííèê áóäåò ïåðå2100áèðàòü îäèí âàðèàíò â ñåêóíäó, åìó ïîòðåáóåòñÿ äëÿ ýòîãî 60·60·24·365ëåò, ÷òî ðàâíÿåòñÿ âåëè÷èíå ïîðÿäêà 1022 ëåò.
Îòñþäà ñëåäóåò, ÷òî âåðîÿòíîñòü òîãî, ÷òî îí âîñïîëüçóåòñÿ íàøåé èíôîðìàöèåé íè÷òîæíî ìàëà. Åñëè æå áóäåò âîçìîæíî ðåøàòü ïîäîáíûå çàäà÷è íå ïåðåáîðîì, àêàêèìòî äðóãèì ñïîñîáîì, çà ïîëèíîìèàëüíîå âðåìÿ, òî ó íàñ ïîÿâèòñÿïîâîä äëÿ ñåðüåçíîãî áåñïîêîéñòâà.Íåòðóäíî âèäåòü, ÷òî åñëè õîòÿ áû äëÿ îäíîé èç NPïîëíûõ ïðîáëåìóäàñòñÿ íàéòè àëãîðèòì, ðåøàþùèé ýòó ïðîáëåìó çà ïîëèíîìèàëüíîåâðåìÿ, òî áóäåò âåðíî ðàâåíñòâî P=NP, è âñå îñòàëüíûå ïðîáëåìû èçýòîãî êëàññà òîæå áóäóò ðåøàòüñÿ çà ïîëèíîìèàëüíîå âðåìÿ.Ìíîãèå èç ýòèõ ïðîáëåì èìåþò åñòåñòâåííóþ ôîðìóëèðîâêó, è íàõîæäåíèå õîðîøèõ àëãîðèòìîâ äëÿ èõ ðåøåíèÿ ÿâëÿåòñÿ èñêëþ÷èòåëüíî âàæíûì äëÿ ïðàêòèêè.  íàñòîÿùåå âðåìÿ èçâåñòíî óæå äîñòàòî÷íîìíîãî NPïîëíûõ ïðîáëåì.
Ìû çäåñü óêàæåì íåêîòîðûå èç ýòèõ ïðîáëåì áåç äîêàçàòåëüñòâà. Âî âñåõ ýòèõ ïðîáëåìàõ ìû ïðåäïîëàãàåì, ÷òîçàäàíà íåêîòîðàÿ åñòåñòâåííàÿ êîäèðîâêà èñõîäíûõ äàííûõ ñëîâàìè íàäíåêîòîðûì àëôàâèòîì.5.4. Ëèòåðàòóðà äëÿ äàëüíåéøåãî èçó÷åíèÿ109Ïðîáëåìà ðàñïîçíàâàíèÿ ãàìèëüòîíîâûõ ãðàôîâ Çàäàíî ìíîæå-ñòâî òî÷åê {1, . . . , n}. Íåêîòîðûå èç ýòèõ òî÷åê ñîåäèíÿþòñÿ ìåæäóñîáîé äóãàìè.
Íåîáõîäèìî îïðåäåëèòü, èìååòñÿ ëè ïóòü ïî äóãàì,ïðîõîäÿùèé ÷åðåç âñå âåðøèíû è ïðè ýòîì ðîâíî ïî îäíîìó ðàçó,ó êîòîðîãî íà÷àëî ñîâïàäàåò ñ êîíöîì.Ïðîáëåìà âûïîëíèìîñòè áóëåâûõ ôîðìóë Ïî çàäàííîé ôîðìóëå,ñîñòàâëåííîé èç ïåðåìåííûõ ñ ïîìîùü ëîãè÷åñêèõ ñâÿçîê &, ∨, ¬,→ îïðåäåëèòü, áóäåò ëè îíà èñòèííà õîòÿ áû ïðè îäíîì íàáîðåçíà÷åíèé èñòèííîñòè ýòèõ ïåðåìåííûõ.Ïðîáëåìà ñóùåñòâîâàíèÿ êîíå÷íîãî ïîêðûòèÿ Çàäàíî êîíå÷íîå ìíîæåñòâî U è ñåìåéñòâî S åãî ïîäìíîæåñòâ.
Òðåáóåòñÿ âûÿñíèòü, ñóùåñòâóåò ëè ïîäñåìåéñòâî S 0 ⊆ S , êîòîðîå ÿâëÿåòñÿ ðàçáèåíèåìU.5.4 Ëèòåðàòóðà äëÿ äàëüíåéøåãî èçó÷åíèÿÌîíîãðàôèÿ [1] íà àíãëèéñêîì ÿçûêå ÿâëÿåòñÿ óâëåêàòåëüíûì ââåäåíèåì â îñíîâíûå ïîíÿòèÿ òåîðèè àëãîðèòìîâ íàïèñàííûì ñ íåñêîëüêî äðóãèõ ïîçèöèé.
Ñ îñíîâàìè òåîðèè íóìåðàöèé ìîæíî ïîçíàêîìèòüñÿ ïî[6]. Äëÿ äàëüíåéøåãî ÷òåíèÿ ìîæíî ïîðåêîìåíäîâàòü êíèãè [2], [3] è [4].Äîâîëüíîòàêè ñëîæíàÿ ìîíîãðàôèÿ [5], ðàññ÷èòàííàÿ ñêîðåå íà ïðîôåññèîíàëüíûõ ìàòåìàòèêîâ, ïîçâîëèò îùóòèòü ãëóáèííóþ ñâÿçü âû÷èñëèìîñòè ñ òåîðèåé ìíîæåñòâ è îñíîâàíèÿìè ìàòåìàòèêè.110Ãëàâà 5. Ââåäåíèå â ñëîæíîñòü àëãîðèòìîâËèòåðàòóðà[1] H. R. Lewis, C. H. Papadimitrou.Elements of the Theory ofComputation.
PretenceHall Inc., Upper Saddie River, New Jersey, 1998.[2] À. È. Ìàëüöåâ. Àëãîðèòìû è ðåêóðñèâíûå ôóíêöèè. Íàóêà, Ìîñêâà,2å èçä., 1981.[3] Õ. Ðîäæåðñ. Òåîðèÿ ðåêóðñèâíûõ ôóíêöèé è ýôôåêòèâíàÿ âû÷èñëèìîñòü. Ìèð, Ìîñêâà, 1972.[4] Ð. È. Ñîàð. Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà è ñòåïåíè. Êàçàíñêîå ìàòåìàòè÷åñêîå îáùåñòâî, Êàçàíü, 2000.[5] Þ. Ë. Åðøîâ. Îïðåäåëèìîñòü è Âû÷èñëèìîñòü. Ñèáèðñêàÿ øêîëààëãåáðû è ëîãèêè. Íàó÷íàÿ êíèãà, Íîâîñèáèðñê, 1996.[6] Þ. Ë.
Åðøîâ. Òåîðèÿ íóìåðàöèé. Íàóêà, Ìîñêâà, 1977.111Ïðåäìåòíûé óêàçàòåëüPrime (x), 59Ïðîãð (x), 63|α|, 16æe , 68DEC I,n, 46INC I, 46ZERO I, 49[i]→[j],(k), 50sg (x), 56sg (x), 57x−̇1, 57x−̇y , 57(x)i , 620(x), 52A ∩ B , 10A ∪ B , 10A \ B , 11A ⊂ B , 10A × B , 12APk (x1 , . . . , xk ), 46An , 13F (x) ↓, 15F (x) ↑, 15F : A 99K B , 15F : A → B , 15n (x , . . . , x ), 52Im1nR−1 , 14R0 ◦ R1 , 13T (A), 23Tk (e, x1 , .
. . ,xk , y), 67U , 66Wn , 95Êîì (x), 63Λ, 16α → β , 38Γ∗α → β , 38Γα → •β , 77M (îïåðàòîð ìèíèìèçàöèè), 53R (îïåðàòîð ïðèìèòèâíîé ðåêóðñèè), 52S(îïåðàòîðñóïåðïîçèöèè), 52TS A, 10S A, 10x∈A Bx , 15ct (e, x, n), 63dom (F ), 15div (x, y), 59ex (i, x), 60∈h , i8xy , 59lh (x), 61A(w), 78F([i1 ],...,[ik ])→[j], 50µyR(y, x̄), 59µy(g(y, x̄) = 0), 53A, 11πn , 95range (F ), 15rg (e, x, n), 63seq (x), 62112Ïðåäìåòíûé óêàçàòåëüstop (e, x, n), 67⊆, 9∅, 9{e}(x1 , . . . ,xk ), 68f (x̄) ' g(x̄), 46pi , 60s(x), 52v ⇒M w, 72v VM w, 73A+ , 16A∗ , 16Êëàññû P è NP, 104Ìàøèíà Òüþðèíãàïîëèíîìèàëüíî îãðàíè÷åííàÿ,102ïîëèíîìèàëüíîå ðàñïîçíàâàíèå ÿçûêà, 103ðàñïîçíàâàíèå ÿçûêà, 102àëôàâèò, 16àëãîðèòìè÷åñêàÿ ïðîáëåìàíàä íóìåðîâàííûì ìíîæåñòâîì,83íåðàçðåøèìàÿ, 83ðàçðåøèìàÿ, 83àâòîìàòñî ñâîéñòâîì âàõò¼ðà, 28àâòîìàò êîíå÷íûéäåòåðìèíèðîâàííûé, 21íåäåòåðìèíèðîâàííûé, 24äåêàðòîâî ïðîèçâåäåíèå, 12äîïîëíåíèå ìíîæåñòâà, 11ýêâèâàëåíòíîñòüíóìåðàöèîííàÿ, 81ôîðìàëüíàÿ ãðàììàòèêà, 35ôóíêöèèïîäîáíûå, 89ôóíêöèè ïðîñòåéøèå, 51ôóíêöèÿ, 14÷àñòè÷íî ðåêóðñèâíàÿ, 53ãðàôèê ôóíêöèè, 98113õàðàêòåðèñòè÷åñêàÿ, 57îáùåðåêóðñèâíàÿ, 54ïðàâèëüíî âû÷èñëèìàÿ íà ìàøèíå Òüþðèíãà, 73ïðèåìëåìàÿ, 88ïðèìèòèâíî ðåêóðñèâíàÿ, 53ðåêóðñèâíàÿ, 54âû÷èñëèìàÿ íà ìàøèíå ؼíôèëäà, 47âû÷èñëèìàÿ ñ ïîìîùüþ íîðìàëüíîãî àëãîðèôìà Ìàðêîâà, 78ãðàôèê ôóíêöèè, 98ãðàììàòèêàêîíòåêñòíîñâîáîäíàÿ, 39íåóêîðà÷èâàþùàÿ, 39íîðìàëüíàÿ, 35ðåãóëÿðíàÿ, 39êîäèðîâàíèåêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé,61ìàøèí ؼíôèëäà, 63âû÷èñëåíèé íà ìàøèíå ؼíôèëäà, 66êîìïîçèöèÿ îòíîøåíèé, 13êîìïîçèöèÿ îòîáðàæåíèé, 15êîíêàòåíàöèÿñëîâ, 16ÿçûêîâ, 17ëåììàî ìíîæåñòâåííîñòè, 90î íàêà÷èâàíèè, 31î ñîâìåñòíîé ðåêóðñèè, 62î âàõòåðå, 28ìàêðîìàøèíà, 48ìàêðîïðîãðàììà, 48ìàêðîñû äëÿ ìàøèíû ؼíôèëäà, 47ìàøèíàؼíôèëäà, 45114Òüþðèíãà, 70äåòåðìèíèðîâàííàÿ, 102íåäåòåðìèíèðîâàííàÿ, 102ìíîæåñòâî, 7íóìåðîâàííîå, 81ñïîñîáû çàäàíèÿ, 8âû÷èñëèìî ïåðå÷èñëèìîå (â.ï.),93íîðìàëüíûå àëãîðèôìû Ìàðêîâà, 77íóìåðàöèÿ, 81Êëèíè âñåõ â.ï.
ìíîæåñòâ, 95íåãàòèâíàÿ, 82îäíîçíà÷íàÿ, 82ïîçèòèâíàÿ, 81ðàçðåøèìàÿ, 81âû÷èñëèìàÿ, 95îáúåäèíåíèå, 10îïåðàöèÿ, 15áèíàðíàÿ, 15òåðíàðíàÿ, 15óíàðíàÿ, 15îïåðàòîðìèíèìèçàöèè, 53ïðèìèòèâíîé ðåêóðñèè, 52ñóïåðïîçèöèè, 52îòíîøåíèå, 13àíòèñèììåòðè÷íîå, 14÷àñòè÷íîãî ïîðÿäêà, 14ýêâèâàëåíòíîñòè, 14ëèíåéíîãî ïîðÿäêà, 14îáðàòíîå, 14ðåôëåêñèâíîå, 13ðåêóðñèâíîå, 57ñèììåòðè÷íîå, 13òðàíçèòèâíîå, 14îòîáðàæåíèå, 14÷àñòè÷íîå, 14íà, 15îáëàñòü îïðåäåëåíèÿ, 15Ïðåäìåòíûé óêàçàòåëüîáëàñòü çíà÷åíèÿ, 15ðàçíîçíà÷íîå, 15âçàèìíîîäíîçíà÷íîå, 15ïåðåñå÷åíèå, 10ïîäìíîæåñòâî, 9ïîäñëîâî, 17ïîëèíîìèàëüíàÿ ñâîäèìîñòü ïðîáëåì, 107ïîëèíîìèàëüíîå ðàñïîçíàâàíèå ÿçûêà, 103ïðîáëåìàïåðåáîðà, 107ïîëèíîìèàëüíàÿ ñâîäèìîñòü,107ðàñïîçíàâàíèÿ ãàìèëüòîíîâûõãðàôîâ, 109ñóùåñòâîâàíèÿ êîíå÷íîãî ïîêðûòèÿ, 109âûïîëíèìîñòè áóëåâûõ ôîðìóë, 109NPïîëíûå, 107P=NP, 107ïðîáëåìà îñòàíîâêè, 83ïðîäóêöèÿ, 36ïóñòîå ìíîæåñòâî, 9ðàâåíñòâî ìíîæåñòâ, 8ðàçáèåíèå ìíîæåñòâà, 11ðàçíîñòü ìíîæåñòâ, 11ðåãèñòðû, 45ðåãóëÿðíîå âûðàæåíèå, 33ñ÷¼ò÷èê êîìàíä, 45ñëîâî, 16ïóñòîå, 16ñâîäèìîñòü íóìåðàöèé, 84òåîðåìàÊëèíè î íîðìàëüíîé ôîðìå,67Ïîñòà, 97Ðàéñà, 87î ãðàôèêå, 98Ïðåäìåòíûé óêàçàòåëüî íåïîäâèæíîé òî÷êå, 86î ïàðàìåòðèçàöèè, 68î ðàçáèåíèè, 14î ñîîòíîøåíèè ÿçûêîâ, çàäàâàåìûõ ðåãóëÿðíûìè ãðàììàòèêàìè è àâòîìàòíûõÿçûêîâ, 40î ñóùåñòâîâàíèè âû÷èñëèìîãî ïîëèíîìèàëüíî íåðàñïîçíàâàåìîãî ÿçûêà, 105îá ýêâèâàëåíòíûõ îïðåäåëåíèÿõ â.ï.
ìíîæåñòâ, 94îá ýëèìèíàöèè ìàêðîñîâ, 48îá óíèâåðñàëüíîé ôóíêöèè,68îá ýêâèâàëåíòíîñòè äåòåðìèíèðîâàííûõ è íåäåòåðìèíèðîâàííûõ àâòîìàòîâ, 25smn, 68òåçèñ ×¼ð÷à, 79óïîðÿäî÷åííûå nêè, 12óïîðÿäî÷åííûå ïàðû, 11âõîæäåíèåñàìîå ëåâîå, 17ñëîâà â ïîäñëîâî, 17ÿçûêàâòîìàòíûé, 23ôîðìàëüíûé, 16êîíòåêñòíîñâîáîäíûé, 39ïîðîæäàåìûé ãðàììàòèêîé,39ðàñïîçíàâàåìûé êîíå÷íûì àâòîìàòîì, 23ðåãóëÿðíûé, 33ÿçûê ïîëèíîìèàëüíî ðàñïîçíàâàåìûé, 103çâ¼çäî÷êà Êëèíè, 17NPïîëíûå ïðîáëåìû, 107115.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
