NP-grūtība un NP-pilnība — definīcija, TSP un piemēri

NP-grūtība, NP-pilnība un TSP skaidrojumi ar skaidriem piemēriem — saprotamas definīcijas, algoritmu izaicinājumi un praktiskas ilustrācijas stundas lasītājam.

Kas ir NP-grūtība un NP-pilnība

NP-grūta problēma parasti tiek definēta kā lēmumu (jā/nē) problēma H tāda, ka jebkura problēma no klases NP var tikt pārveidota uz H ar polinomināras laika sarežģītības pārveidojumu (reducēšanu). Citiem vārdiem, atrast algoritmu, kas atrisina H efektīvāk nekā visām NP problēmām, būtu vismaz tikpat grūti kā atrisināt jebkuru NP problēmu. Dažas NP-grūtas problēmas pieder arī klasei NP (tātad to risinājumu var ne tikai pārveidot no jebkuras citas NP problēmas, bet arī ātri pārbaudīt), bet citas NP-grūtas problēmas neatrodas NP un pat var būt nelemjamas vai ar vēl augstāku sarežģītību.

Ja NP-grūta problēma ir arī problēma no NP, tad tā tiek saukta par NP-pilnīgu. NP-pilnīgas problēmas ir tiešā nozīmē "visgrūtākās" problēmas NP — ja kāda NP-pilnīga problēma būtu atrisināma polinominārajā laikā, tad visas NP problēmas būtu atrisināmas polinominārajā laikā.

Formālā definīcija īsumā

• NP — problēmas, kuru "jā" gadījumā pastāv sertifikāts (risinājums), kuru var pārbaudīt polinominārajā laikā deterministiskā Tjuringa mašīnā.
• NP-grūta (NP-hard) — lēmumu problēma H, priekš kuras katrai L∈NP eksistē polinomināra funkcija f tāda, ka x∈L ↔ f(x)∈H. (Bieži lieto arī plašākas reducēšanas definīcijas, bet ideja ir tāda pati: H ir vismaz tikpat sarežģīta kā jebkura NP problēma.)
• NP-pilnīga (NP-complete) — problēma, kas ir gan NP, gan NP-grūta.

Ceļojošā pārdevēja problēma (TSP) — lēmuma versija un optimizācijas versija

Piemērs NP-pilnīgai lēmuma problēmai:

Ceļojošs pārdevējs vēlas apmeklēt 100 pilsētas, braucot ar automašīnu, sākot un beidzot savu ceļojumu mājās. Viņam ir ierobežotas benzīna rezerves, tāpēc viņš kopumā var nobraukt tikai 10 000 km. Jautājums (lēmuma versija): vai pastāv maršruts, kurš apmeklē visas pilsētas un kura kopējais garums nepārsniedz 10 000 km?

Šī lēmuma versija ir viegli parādāma kā NP: ja kāds sniedz konkrētu maršrutu (sertifikātu), tad ar algoritma vai vienkāršu aprēķinu var pārbaudīt jebkura ceļa garumu un pārliecināties, vai tas apmeklē visas pilsētas un vai kopējais garums ≤ 10 000 km. Tāpēc lēmuma versija ir NP. Turklāt TSP lēmuma versijas pamatvarianti ir NP-pilnīgi (atsevišķas, labi-definētas versijas — piemēram, vispārīgie grafu TSP vai simetriska TSP lēmuma forma).

Ņemiet vērā, ka optimizācijas versija — atrast īsāko iespējamo maršrutu — tiek uzskatīta par NP-grūtu (un parasti NP-grūtāka, ja runājam par tiešo optimizāciju), jo, lai to atrisinātu, būtu jāspēj risināt NP-pilnīgu lēmuma versiju daudz reižu vai izmantot citas sarežģītas metodes. Bieži optimizācijas problēmas reducē uz lēmuma problēmu formu (piem., "vai eksistē maršruts ar garumu ≤ K?").

Piemērs problēmai, kas ir NP-grūta, bet nav NP

Undecidable piemērs (apmēram raksturojums):

while(true){ turpināt; }

Jautājums: ja kāds uzsāk programmu, kas vienkārši izpilda šādu ciklu, vai tā darbosies mūžīgi (t.i., nekad neapstāsies)?

Šis ir piemērs uzdevumam, kura risinājums nav pārbaudāms polinominārajā laikā un pats uzdevums var būt nelemjams (Halting problēma un tam radniecīgas problēmas). Turklāt daudzus no šādiem nelemjamajiem uzdevumiem var izmantot kā mērķi, uz kuru var reducēt jebkuru NP-problēmu, tāpēc tie ir NP-grūti (vai pat sarežģītāki par NP-grūtajiem) — taču tie neatrodas klasē NP, jo nav iespējams vienmēr pārbaudīt sertifikātu polinominārajā laikā (vai arī nav iespējams vispār viennozīmīgi atbildēt algorithmiski). Tādēļ pastāv NP-grūtas problēmas, kas nav NP, t.i., nav NP-pilnīgas.

Kā saprast reducēšanu un "grūtumu"

• Ideja par reducēšanu: ja no problēmas A var polinominārā laikā uzbūvēt instancei b no problēmas B tā, ka x∈A ↔ b∈B, tad B ir vismaz tikpat grūta kā A. Ja tas iznāk par katru A∈NP, tad B ir NP-grūta.
• Cook–Levin teorēma parāda, ka SAT (booleana formula apmierināmības problēma) ir NP-pilnīga. No SAT var reducēt daudzas citas problēmas, tāpēc SAT ir pirmais “standarta” NP-pilnīgais piemērs.

Citi svarīgi novērojumi

• P ⊆ NP: visi polinominārajā laikā atrisināmie uzdevumi (P) noteikti ir NP, jo, ja ir polinominārs algoritms, tad var uzskatīt, ka sertifikāts nav vajadzīgs. Tomēr jautājums, vai P=NP, joprojām ir neatbildēts — tas ir viens no svarīgākajiem neatrisinātajiem jautājumiem informātikā.
• Ir daudz praktisku NP-pilnīgu problēmu: SAT, 3-SAT, Clique, Hamiltonian cycle, Vertex cover, Subset sum, Graph coloring u.c. To optimizācijas versijas parasti ir NP-grūtas.
• Dažas NP-grūtas problēmas nav lēmuma problēmas vai ir nelemjamas; tās var būt pat ārpus efektivi aprēķināmu problēmu klāsta.
• Praktiskai darbībai bieži izmanto aptuvenu (approximation) algoritmus, heuristikas vai speciālas metodes (piem., branch-and-bound, metaheuristikas) NP-grūtām optimizācijas problēmām.

Kopsavilkums

Īsumā: NP-grūta nozīmē "vismaz tikpat grūta kā jebkura NP problēma (pēc reducēšanas)"; NP-pilnīga nozīmē problēma, kas ir gan NP, gan NP-grūta. Ceļojošā pārdevēja lēmuma versija (vai eksistē maršruts ar garumu ≤ K?) ir klasisks NP-pilnības piemērs; optimizācijas versija (atrast īsāko maršrutu) ir NP-grūta. Savukārt daži uzdevumi, piemēram, saistīti ar nekonstruējamu vai nelemjamu uzvedību (piem., halting tipa jautājumi), var būt NP-grūti, bet noteikti neietilpst NP, un dažkārt pat nav algoritmiski atrisināmi.

Jautājumi un atbildes

J: Kas ir NP grūtā problēma?

Vai visām NP-grūtajām problēmām var ātri pārbaudīt darba risinājumu?

J: Kā sauc kategoriju, kurā ietilpst NP-smagas problēmas, kas ir arī NP problēmas?

Vai visas NP-grūtās problēmas ir NP-pilnīgas?

J: Vai NP-grūtās problēmas ir viegli atrisināmas?

J: Vai NP-grūtu problēmu risināšana dod kādas priekšrocības?

J: Vai NP-grūtu problēmu risināšanā tiek veikti pētījumi?

Meklēt pēc burta