P pret NP: vai ātri pārbaudāmās problēmas var ātri atrisināt?

Precizējumi

Piemēram, ja jums ir uzdevums un kāds saka: "Jūsu uzdevuma atbilde ir skaitļu kopa 1, 2, 3, 4, 5", dators var ātri noteikt, vai atbilde ir pareiza vai nepareiza, bet datoram var paiet ļoti ilgs laiks, līdz viņš pats var atrast "1, 2, 3, 4, 5". Cits piemērs ir pirmskaitļu atrašana. Ir viegli pārbaudīt, vai skaitlis ir pirmskaitlis, bet ir ļoti grūti šos skaitļus atrast. Dažiem interesantiem, praktiskiem šāda veida jautājumiem mums trūkst jebkāda veida, kā ātri atrast atbildi, bet, ja mums tiek sniegta atbilde, ir iespējams ātri pārbaudīt - tas ir, pārbaudīt - atbildi. Šādā veidā NP problēmas var uzskatīt par līdzīgām mīklām: var būt grūti uzminēt mīklas atbildi, bet, tiklīdz uzzinām atbildi, tā šķiet acīmredzama. Šajā salīdzinājumā (analoģijā) pamatjautājums ir šāds: vai mīklas patiešām ir tik grūtas, kā mums šķiet, vai arī mēs kaut ko palaižam garām?

Tā kā šāda veida P pret NP jautājumi ir tik praktiski svarīgi, daudzi matemātiķi, zinātnieki un programmētāji vēlas pierādīt vispārīgo apgalvojumu, ka katru ātri pārbaudāmu problēmu var atrisināt ātri. Šis jautājums ir pietiekami svarīgs, lai Klejas Matemātikas institūts piešķirtu 1 000 000 ASV dolāru ikvienam, kurš veiksmīgi sniegs pierādījumu vai pamatotu skaidrojumu, kas to atspēko.

Iedziļinoties nedaudz dziļāk, redzam, ka visas P problēmas ir NP problēmas: ir viegli pārbaudīt, vai risinājums ir pareizs, atrisinot problēmu un salīdzinot divus risinājumus. Tomēr cilvēki vēlas zināt par pretējo: Vai ir kādas NP problēmas, kas nav P problēmas, vai arī visas NP problēmas ir tikai P problēmas? Ja NP problēmas patiešām nav tas pats, kas P problēmas (P ≠ NP), tas nozīmētu, ka nevar pastāvēt nekādi vispārēji, ātri risināšanas veidi šīm NP problēmām, lai arī cik cītīgi mēs meklētu. Tomēr, ja visas NP problēmas ir P problēmas (P = NP), tas nozīmētu, ka pastāv jaunas, ļoti ātras problēmu risināšanas metodes. Mēs vienkārši vēl neesam tās atraduši.

Tā kā zinātnieku un matemātiķu pūliņi vēl nav atraduši vispārējas, vienkāršas NP problēmu risināšanas metodes, daudzi cilvēki uzskata, ka pastāv NP problēmas, kas nav P problēmas (tas ir, ka P ≠ NP ir taisnība). Arī lielākā daļa matemātiķu uzskata, ka tas ir taisnība, taču pašlaik neviens to nav pierādījis ar stingru matemātisku analīzi. Ja izdotos pierādīt, ka NP un P ir viens un tas pats (P = NP ir taisnība), tas ļoti ietekmētu daudzus ikdienas dzīves aspektus. Šā iemesla dēļ jautājums par P pret NP ir svarīgs un plaši pētīts temats.

Piemērs

Pieņemsim, ka kāds vēlas uzbūvēt divus torņus, sakraujot dažādu masu akmeņus. Kāds vēlas nodrošināt, lai katram no torņiem būtu tieši vienāda masa. Tas nozīmē, ka akmeņi būs jāsaliek divās kaudzēs, kuru masa ir vienāda. Ja kāds nojauš akmeņu sadalījumu, kas, pēc viņa domām, derēs, viņam būs viegli pārbaudīt, vai viņam ir taisnība. (Lai pārbaudītu atbildi, var sadalīt akmeņus divās kaudzēs un tad ar svariem pārbaudīt, vai to masa ir vienāda.) Tā kā šo problēmu, ko datorzinātnieki dēvē par "sadalīšanu", ir viegli pārbaudīt - vieglāk nekā to atrisināt, kā redzēsim, - tā nav P problēma. ^[]

Cik grūti to ir atrisināt, atklāti? Ja sākumā ir tikai 100 akmeņi, tad ir 2^{100-1}-1 = 633 825 300 114 700 748 351 602 687 jeb aptuveni 6,3 x 10^{29} iespējamo veidu (kombināciju), kā šos akmeņus sadalīt divās kaudzēs. Ja katru dienu varētu pārbaudīt vienu unikālu akmeņu kombināciju, tas prasītu 1,3 x 10^{22} jeb 1 300 000 000 000 000 000 000 000 000 000 000 gadu pūļu. Salīdzinājumam - fiziķi uzskata, ka Visums ir aptuveni 1,4 x 10^{10} gadu vecs (450 000 000 000 000 000 000 000 jeb aptuveni 4,5 x 10^{17} sekunžu jeb aptuveni viena triljondaļa no laika, kas būtu nepieciešams mūsu akmeņu krāvuma veidošanas darbiem. Tas nozīmē, ka, ņemot vērā visu laiku, kas pagājis kopš Visuma pirmsākumiem, katru sekundi būtu jāpārbauda vairāk nekā divi triljoni (2 000 000 000 000 000) dažādu akmeņu sadalīšanas veidu, lai pārbaudītu visus dažādos veidus.

Ja ieprogrammētu jaudīgu datoru, lai pārbaudītu visus šos akmeņu sadalīšanas veidus, ar pašreizējām sistēmām varētu pārbaudīt 1 , 000 , 000 {\displaystyle 1,000,000} kombināciju sekundē. Tas nozīmē, ka joprojām būtu vajadzīgi 2 , 000 , 000 {\displaystyle 2,000,000} ļoti jaudīgi datori, kas darbojas kopš Visuma rašanās, lai pārbaudītu visus iežu sadalīšanas veidus.

Tomēr, iespējams, ir iespējams atrast metodi, kā sadalīt akmeņus divās vienādās kaudzēs, nepārbaudot visas kombinācijas. Jautājums "Vai P ir vienāds ar NP?" ir saīsinājums, lai jautātu, vai šāda metode var pastāvēt.

Kāpēc tas ir svarīgi

Ir daudz svarīgu NP problēmu, kuras cilvēki nezina, kā atrisināt ātrāk, nekā pārbaudot visas iespējamās atbildes. Lūk, daži piemēri:

• 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. Viņš vēlas zināt, vai viņš var apmeklēt visas pilsētas, neiztērējot benzīnu.
• Skolā ir 100 dažādas klases, un skolotājam ir jāizvēlas viena stunda katras klases noslēguma eksāmenam. Lai novērstu krāpšanu, visiem skolēniem, kuri apmeklē klasi, eksāmens par šo klasi jākārto vienlaicīgi. Ja skolēns mācās vairāk nekā vienā klasē, tad visiem šiem eksāmeniem jābūt citā laikā. Skolotājs vēlas uzzināt, vai viņš var ieplānot visus eksāmenus vienā dienā, lai katrs skolēns varētu kārtot eksāmenu par katru klasi.
• Lauksaimnieks vēlas nogādāt tirgū 100 dažādas masas arbūzus. Viņai arbūzi jāsaiņo kastēs. Katrā kastē var ievietot tikai 20 kilogramus, nesabojājot to. Lauksaimniecei ir jāzina, vai ar 10 kastēm pietiks, lai aizvestu visus 100 arbūzus uz tirgu. (Tas ir triviāli, ja ne vairāk kā viens arbūzs sver vairāk kā 2 kg, tad katrā no kastēm var ievietot jebkurus 10, ja ne vairāk kā desmit arbūzi sver vairāk kā 2 kg, tad katrā kastē var ievietot pa vienam utt. ātram risinājumam; novērošana būs atslēga jebkuram ātram risinājumam, piemēram, šim vai skaitļu kopas uzdevumam).
• Lielā mākslas galerijā ir daudz istabu, un katru sienu klāj daudz dārgu gleznu. Galerijas īpašnieks vēlas iegādāties kameras, lai novērotu šīs gleznas, ja kāds zaglis mēģinātu kādu no tām nozagt. Viņš vēlas zināt, vai viņam pietiks ar 100 kamerām, lai nodrošinātu, ka katru gleznu var redzēt vismaz ar vienu kameru.
• Kliķes problēma: Skolas direktoram ir saraksts ar skolēniem, kuri draudzējas cits ar citu. Viņa vēlas atrast 10 % skolēnu grupu, kurā visi skolēni draudzējas viens ar otru.

Eksponenciālais laiks

Iepriekš minētajā piemērā redzam, ka, ja ir 100 {\displaystyle 100} akmeņi, ir 2 100 {\displaystyle 2^{100} veidu, kā sadalīt akmeņu kopu. Ar n {\displaystyle n} akmeņiem ir 2 n {\displaystyle 2^{n}} kombināciju. Funkcija f ( n ) = 2 n {\displaystyle f(n)=2^{n}} ir eksponenciāla funkcija. Tā ir svarīga NP, jo tā modelē sliktākajā gadījumā nepieciešamo aprēķinu skaitu, lai atrisinātu problēmu, un tādējādi arī sliktākajā gadījumā nepieciešamo laiku.

Un līdz šim sarežģīto problēmu risināšanai ir bijuši nepieciešami 2 n {\displaystyle 2^{n}} aprēķini. Jebkurai konkrētai problēmai cilvēki ir atraduši veidus, kā samazināt nepieciešamo aprēķinu skaitu. Var atrast veidu, kā veikt tikai 1 % no sliktākā gadījuma aprēķinu skaita, un tas ietaupa daudz aprēķinu, bet tas joprojām ir 0,01 × ( 2 n ) {\displaystyle 0,01\ reizes (2^{n})} aprēķinu. Un katrs papildu akmens joprojām dubulto problēmas atrisināšanai nepieciešamo aprēķinu skaitu. Pastāv atziņas, kas var radīt metodes, lai veiktu vēl mazāk aprēķinu, radot modeļa variācijas: piemēram, 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. . Taču, pieaugot n {\displaystyle n}, eksponenciālā funkcija joprojām dominē.

Apskatiet eksāmenu plānošanas problēmu (aprakstīta iepriekš). Bet pieņemsim, ka ir 15000 studentu. Ir datorprogramma, kas sastāda visu 15000 studentu grafikus. Tā darbojas stundas laikā un sagatavo eksāmenu grafiku tā, lai visi studenti varētu nokārtot eksāmenus vienas nedēļas laikā. Tas atbilst daudziem noteikumiem (nav eksāmenu, kas notiek viens otram sekojoši, nav vairāk kā 2 eksāmeni 28 stundu laikā, ...), lai ierobežotu eksāmenu nedēļas stresu. Programma darbojas vienu stundu semestra starpbrīdī, un katrs zina savu eksāmenu grafiku, un viņam ir pietiekami daudz laika, lai sagatavotos.

Taču nākamajā gadā skolēnu skaits ir par 10 lielāks. Ja tā pati programma darbojas uz tā paša datora, tad viena stunda pārvērtīsies par 2 10 {\displaystyle 2^{10}} stundām, jo katrs papildu students dubulto aprēķinus. Tas ir 6 {\displaystyle 6} nedēļas! Ja būtu vēl 20 skolēni, tad

2 20 {\displaystyle 2^{20}} stundas = 1048576 {\displaystyle 1048576}stundas ~ 43691 {\displaystyle 43691} dienas ~ 113 {\displaystyle 113} gadi

Tādējādi 15000 {\displaystyle 15000} skolēnu tas aizņem vienu stundu. 15020 {\displaystyle 15020} studentiem tas aizņem 113 {\displaystyle 113} gadus.

Kā redzat, eksponenciālās funkcijas aug ļoti ātri. Lielākā daļa matemātiķu uzskata, ka visgrūtāko NP problēmu risināšanai nepieciešams eksponenciāls laiks.

NP-pilnīgas problēmas

Matemātiķi var pierādīt, ka ir dažas NP problēmas, kas ir NP-pilnas. NP-kompleta problēma ir vismaz tikpat grūti atrisināma kā jebkura cita NP problēma. Tas nozīmē, ka, ja kāds atrastu metodi, kā ātri atrisināt jebkuru NP-kompleta problēmu, viņš varētu izmantot šo pašu metodi, lai ātri atrisinātu jebkuru NP problēmu. Visas iepriekš uzskaitītās problēmas ir NP-pilnīgas, tāpēc, ja pārdevējs atrastu veidu, kā ātri saplānot savu ceļojumu, viņš to varētu pastāstīt skolotājai, un viņa šo pašu metodi varētu izmantot, lai plānotu eksāmenus. Lauksaimnieks varētu izmantot to pašu metodi, lai noteiktu, cik daudz kastu viņai vajag, un sieviete varētu izmantot to pašu metodi, lai atrastu veidu, kā uzcelt savus torņus.

Tā kā metode, kas ātri atrisina vienu no šīm problēmām, var atrisināt visas, ir daudz cilvēku, kas vēlas atrast šādu metodi. Tomēr, tā kā ir tik daudz dažādu NP-pabeigtu problēmu un neviens līdz šim nav atradis veidu, kā ātri atrisināt kaut vienu no tām, lielākā daļa ekspertu uzskata, ka NP-pabeigtu problēmu ātra atrisināšana nav iespējama.

Pamatīpašības

Sarežģītības teorijā sarežģītības klase NP-pilnība (saīsināti NP-C vai NPC) ir problēmu klase, kurai piemīt divas īpašības:

• Tā ir NP (nedeterministisko polinomiālā laika) problēmu kopa: Jebkuru dotās problēmas risinājumu var pārbaudīt ātri (polinomālā laikā).
• Tā ir arī NP-grūto problēmu sarakstā: Tās ir vismaz tikpat grūtas kā vissarežģītākās NP problēmas. NP grūtajām problēmām nav obligāti jābūt NP elementiem; patiesībā tās var pat nebūt atrisināmas.

Formāls pārskats

NP-komplekts ir NP apakškopa, visu tādu lēmumu pieņemšanas problēmu kopa, kuru risinājumus var pārbaudīt polinoma laikā; NP var līdzvērtīgi definēt kā tādu lēmumu pieņemšanas problēmu kopu, kuras mašīna atrisina polinoma laikā. Problēma p no NP ir arī NPC tad un tikai tad, ja katru citu problēmu no NP var pārveidot uz p polinoma laikā. NP-pilnīgs bija jālieto kā īpašības vārds: NP-pilnīgs klases problēmas bija kā NP+pilnīgas problēmas.

NP-pilnīgās problēmas tiek pētītas, jo šķiet, ka spēja ātri pārbaudīt problēmas risinājumus (NP) korelē ar spēju ātri atrisināt problēmu (P). Ir konstatēts, ka ikviena NP problēma ir ātri atrisināma - tā tiek saukta par P = NP: problēmu kopu. Viena problēma NP-komplektā tiek atrisināta ātri, ātrāk nekā katra problēma NP arī ātri atrisināta, jo NP-komplektās problēmas definīcija nosaka, ka katrai NP problēmai jābūt ātri reducējamai uz katru NP-komplektā problēmu (tā tiek reducēta polinomālā laikā). [1]

Piemēri

Ir zināms, ka Boolea apmierināmības problēma ir NP pilnīga. 1972. gadā Ričards Karps formulēja 21 problēmu, par kurām ir zināms, ka tās ir NP-pilnīgas. Tās ir pazīstamas kā 21 NP-komplektās problēmas. Tās ietver tādas problēmas kā integrālo skaitļu programmēšanas problēma, kurā lineārās programmēšanas paņēmieni tiek piemēroti veseliem skaitļiem, knapsaka problēma vai virsotņu seguma problēma.