Kas yra "P = NP?", Ir kodėl toks toks garsus klausimas?

Klausimas, ar P = NP yra bene labiausiai žinomas visuose kompiuterių moksluose. Ką tai reiškia? Ir kodėl taip įdomu?

Oi, ir už papildomą kreditą, prašome pateikti įrodymų apie tiesą ar netikrumą. :)

209
21 сент. raldi nustatė 21 sep . 2008-09-21 19:07 '08 at 7:07 pm 2008-09-21 19:07
@ 6 atsakymai

P reiškia polinominį laiką. „NP“ reiškia neaseterministinį laiką.

Apibrėžimai:

  • Polinominis laikas reiškia, kad algoritmo sudėtingumas yra O (n ^ k), kur n yra jūsų duomenų dydis (pvz., Elementų skaičius rūšiuojamajame sąraše) ir k yra konstanta.

  • Sunkumai yra nustatomi pagal laiką, kiek operacijų reikia atlikti, priklausomai nuo duomenų elementų skaičiaus.

  • Operacija yra kažkas, kas turi prasmę kaip pagrindinę konkrečios užduoties operaciją. Rūšiavimui pagrindinė operacija yra palyginimas. Matricos dauginimui pagrindinė operacija yra dviejų skaičių dauginimas.

Dabar kyla klausimas, ar tai yra deterministinė ar neterminuota priemonė. Yra abstraktus skaičiavimo modelis, įsivaizduojamas kompiuteris, vadinamas „Turing“ mašina (TM). Ši mašina turi ribotą skaičių valstybių ir begalinę juostą, kurioje yra atskiri elementai, kuriuose gali būti parašytas ir skaitomas ribotas simbolių rinkinys. Bet kuriuo metu TM yra vienoje iš jos būsenų ir žiūri į tam tikrą juostos ląstelę. Priklausomai nuo to, ką jis skaito iš šio >

Yra du TM tipai: deterministinis ir ne deterministinis. „Deterministinis“ TM turi tik vieną perėjimą nuo kiekvienos būsenos kiekvienam simboliui, kurį jis skaito iš juostos. Neterministinis TM gali turėti keletą tokių perėjimų, t.y. Geba vienu metu išbandyti kelias galimybes. Tai panaši į daugelio srautų neršimą. Skirtumas yra tas, kad ne deterministinis TM gali generuoti tiek daug „siūlų“, kiek jis nori, o tikrajame kompiuteryje gali veikti tik tam tikras skaičius (lygus CPU skaičiui). Tiesą sakant, kompiuteriai dažniausiai yra deterministiniai TM su ribinėmis juostomis. Kita vertus, nenu deterministinis TM negali būti fiziškai įgyvendinamas, išskyrus kvantinį kompiuterį.

Įrodyta, kad bet kokia problema, kurią galima išspręsti ne deterministiniu TM, gali būti išspręsta deterministiniu TM. Tačiau neaišku, kiek laiko tai užtruks. P = NP teiginys reiškia, kad jei problema laikoma ne deterministiniu TM polinomu laiku, tada galime sukurti deterministinį TM, kuris išspręstų tą pačią problemą polinominiu laiku. Kol kas niekas negalėjo įrodyti, kad tai galima padaryti, bet niekas negalėjo įrodyti, kad tai taip pat neįmanoma.

„NP-full“ problema reiškia „NP“ problemą X, todėl bet kokia „NP“ problema Y gali būti sumažinta iki X polinominiu sumažinimu. Tai reiškia, kad jei kas nors ateina į problemą, susijusią su NP-pilnu polinomu laiku, jis taip pat suteiks sprendimą su polinomu laiku bet kuriai NP problemai. Taigi tai įrodo, kad P = NP. Priešingai, jei kas nors įrodytų, kad P! = NP, tada mes būtume tikri, kad nėra jokio būdo išspręsti NP problemą įprastiniame kompiuteryje polinominiu laiku.

NP-pilnos problemos pavyzdys yra problemos, susijusios su tiesos priskyrimo problema, todėl loginė išraiška, kurioje yra n kintamųjų, yra teisinga.
Šiuo metu praktikoje bet kokia problema, kuri nulemia ne deterministinį TM polinominį laiką, gali būti atliekama tik eksponentiniu laiku deterministiniu TM arba įprastu kompiuteriu.
Pavyzdžiui, vienintelis būdas išspręsti tiesos priskyrimo problemą yra išbandyti 2 ^ n galimybes.

327
24 сент. Atsakymas Dima rugsėjo 24 d 2008-09-24 18:20 '08, 18:20 pm 2008-09-24 18:20
  • Taip arba ne problema P ( P olynominis laikas), jei atsakymas gali būti apskaičiuojamas polinominiu laiku.
  • Taip arba ne problema NP ( N esant deterministiniam P olynominiam laikui), jei atsakymas yra „taip“, galite patikrinti polinomo laiką.

Intuityviai matome, kad jei problema yra P , tai yra NP . Atsižvelgiant į galimą atsakymą į problemą P , mes galime patikrinti atsakymą tiesiog pateikdami atsakymą.

Mažiau akivaizdu ir daug sunkiau atsakyti, jei yra kokių nors problemų P.P. Ar faktas, kad galime patikrinti atsakymą polinominiu laiku, reiškia, kad galime apskaičiuoti šį atsakymą polinominiu laiku?

Yra nemažai svarbių problemų, kurios, kaip žinoma, yra „ NP“ (iš esmės, jei kuri nors iš šių problemų pasirodė esanti „ P“ , tada visos „<strong> NP problemos“ pasirodė esančios P ). Jei P = NP , visos šios problemos bus įrodyta kaip efektyvus (polinominis laikas) sprendimas.

Dauguma mokslininkų mano, kad P ! = NP . Tačiau iki šiol nebuvo nustatyta jokių įrodymų dėl P = NP arba P ! = NP . Jei kas nors įrodo hipotezę, jie laimės 1 milijoną dolerių .

75
24 сент. atsakymas Derek Park 24 sept. 2008-09-24 20:03 '08 at 8:03 pm 2008-09-24 20:03

Jei norite pateikti paprasčiausią atsakymą, galiu galvoti:

Tarkime, mes turime problemą, kuri daro tam tikrą skaičių sąnaudų ir turi įvairius galimus sprendimus, kurie gali arba gali išspręsti šių sąnaudų problemą. Loginis įspūdis galvosūkių žurnale būtų geras pavyzdys: įvestis yra sąlygos („George negyvena mėlynos arba žaliosios namuose“), o galimas sprendimas yra pareiškimų sąrašas („George gyvena geltoname name, auga žirniai ir turi šunį "). Garsus pavyzdys yra keliaujančio keleivio problema: atsižvelgiant į miestų sąrašą ir laiką, kurį reikia gauti iš bet kurio miesto į bet kurį kitą, ir laikiną apribojimą, galimas sprendimas būtų miestų sąrašas, pagal kurį pardavėjas juos aplankys, ir jis dirbtų, jei būtų laiko Ištrauka buvo mažesnė už terminą.

Tokia problema yra NP, jei galime veiksmingai patikrinti galimą sprendimą, kad pamatytume, ar jis veikia. Pvz., Turint omenyje miestų sąrašą, kurį pardavėjas turi aplankyti, mes galime pridėti laiką kiekvienai kelionei tarp miestų ir lengva pamatyti, ar tai atitinka ribą. Problema yra P, jei galime veiksmingai rasti sprendimą, jei jis yra.

(Efektyviai ji turi tikslią matematinę reikšmę. Praktiškai tai reiškia, kad didelių problemų negali būti nepagrįstai sunku išspręsti. Ieškant galimo sprendimo, neefektyvus būdas būtų išvardyti visus galimus galimus sprendimus ar kažką kito šalia jo, o efektyvus būdas reikalauja daug labiau ribotos paieškos.)

Todėl problema P = NP gali būti išreikšta taip: jei galite efektyviai išbandyti anksčiau aprašytos rūšies problemos sprendimą, ar galite efektyviai rasti sprendimą (arba įrodyti jo nebuvimą)? Akivaizdus atsakymas yra: „Kodėl turėtumėte?“, Ir tai yra gana daug, kur šis klausimas šiandien yra. Niekas negalėjo tai įrodyti ir tai kelia nerimą daugeliui matematikų ir kompiuterių mokslininkų. Štai kodėl kiekvienas, kuris gali įrodyti šį sprendimą, iš „Claypool Foundation“ sudaro milijonus dolerių.

Paprastai manome, kad P nėra lygus NP, kad nėra bendro būdo rasti sprendimus. Jei paaiškėja, kad P = NP, daug pasikeistų. Pavyzdžiui, kriptografija taptų neįmanoma, o tai būtų bet koks privatumas ar patikrinimas internete. Galų gale, mes galime efektyviai užimti šifruotą tekstą ir raktą ir sukurti šaltinio tekstą, todėl jei P = NP, galėtume efektyviai surasti raktą nežinodami to iš anksto. Slaptažodžio krekas tampa nereikšmingas. Kita vertus, galime išspręsti visas planavimo problemų ir išteklių paskirstymo problemų klases.

Galbūt girdėjote „NP-complete“ aprašą. Žinoma, NP-problema yra NP, ir turi šią įdomią savybę: jei ji yra P, tada kiekviena problema yra NP, todėl P = NP. Jei galėtumėte rasti būdą, kaip efektyviai išspręsti keliautojo pardavėjo problemą ar loginius galvosūkius iš galvosūkių žurnalų, galėtumėte efektyviai išspręsti kažką NP. NP visiškai išspręsta problema tam tikra prasme yra sunkiausia NP problema.

Taigi, jei galite rasti veiksmingą bendrąjį metodą, kaip išspręsti bet kokią NP-pilną problemą arba įrodyti, kad tai neegzistuoja, šlovė ir likimas yra tavo.

20
24 сент. David Thornley atsakymas rugsėjo 24 d 2008-09-24 19:26 '08, 19:26 pm 2008-09-24 19:26

Mano nuolankių žinių santrauka:

Yra keletas paprastų skaičiavimo problemų (pvz., Trumpiausio kelio tarp dviejų taškų grafike paieška), kurią galima apskaičiuoti gana greitai (O (n ^ k), kur n yra įvesties dydis ir k yra pastovus (grafikų atveju, viršūnių ar briaunų skaičius) )).

Kitos problemos, pavyzdžiui, rasti kelią, kuris kerta kiekvieną viršūnę grafike, arba gauti RSA slaptą raktą iš viešojo rakto, yra sunkiau (O (e ^ n)).

Tačiau CS sako, kad problema yra ta, kad mes negalime „konvertuoti“ į deterministinę Turingo mašiną į deterministinę, tačiau mes galime konvertuoti ne deterministines būsenos mašinas (pvz., Reguliarios išraiškos analizatorius) į deterministinį (gerai, tačiau mašinos vykdymo laikas bus daug laiko). Tai reiškia, kad turėtume išbandyti visus galimus būdus (dažniausiai protingi CS profesoriai gali pašalinti kai kuriuos iš jų).

Tai įdomu, nes niekas net nežino apie šį sprendimą. Kai kurie sako, kad tai tiesa, kai kurie sako, kad tai melas, tačiau nėra sutarimo. Kitas įdomus dalykas: sprendimas bus žalingas viešojo ir privataus rakto šifravimui (pavyzdžiui, RSA). Juos galite sugadinti taip pat lengvai, kaip RSA raktą.

Ir tai yra gana įkvepianti problema.

9
21 сент. atsakymas į terminą 21 rugsėjis 2008-09-21 19:14 '08 at 7:14 pm 2008-09-21 19:14

Aš negaliu pridėti ką ir kodėl P =? NP klausimo dalis, bet su įrodymais. Ne tik įrodymas turėtų kainuoti papildomą kreditą, bet ir išspręsti vieną iš Tūkstantmečio iššūkių . Neseniai buvo atlikta įdomi apklausa, o paskelbti rezultatai (PDF) tikrai nusipelno dėmesio įrodymų dalykui.

6
24 сент. atsakymas pateikiamas rjzii 24 sep . 2008-09-24 18:26 '08 18:26 pm 2008-09-24 18:26

Pirma, kai kurie apibrėžimai:

  • Speciali problema P yra, jei galite apskaičiuoti sprendimą laiko atžvilgiu mažiau nei n^k kai kuriems k , kur n yra įvesties dydis. Pavyzdžiui, rūšiavimas gali būti atliekamas n log n , kuris yra mažesnis nei n^2 , todėl rūšiavimas yra polinomo laikas.

  • Problema yra NP, jei yra k , kad yra ne didesnio nei n^k dydžio dydžio sprendimas, kurį galite patikrinti ne daugiau kaip n^k . Paimkite 3 spalvų grafikus: atsižvelgiant į grafiką, 3 spalvų lentelė yra (viršūnių, spalvų) porų, kurių dydis yra O(n) , sąrašas ir galite patikrinti O(m) (arba O(n^2) ) laiku, Ar visi kaimynai turi skirtingų spalvų? Taigi grafikas yra 3 spalvų tik tada, jei yra trumpas ir lengvai patikrinamas sprendimas.

Lygiavertis NP apibrėžimas yra „problemos, kurias galima išspręsti ne deterministiniu Turingo aparatu polinominiu laiku“. Nors jis nurodo, iš kur kilo vardas, jis nesuteikia jums tokio pat intuityvaus NP problemų supratimo.

Atkreipkite dėmesį, kad P yra NP pogrupis: jei galite rasti sprendimą polinominiu laiku, yra sprendimas, kuris gali būti išbandytas polinominiu laiku - tik įsitikinkite, kad šis sprendimas yra toks pat, kaip galite rasti.

Kodėl klausimas P =? NP įdomus P =? NP P =? NP ? Jei norite atsakyti į šį klausimą, pirmiausia turite sužinoti, kokios yra problemos, susijusios su „NP-complete“. Paprasčiau tariant,

  • Užduotis L yra NP-užbaigta, jei (1) L yra P ir (2) L išsprendžiamasis algoritmas gali būti naudojamas bet kuriai problemai L 'išspręsti NP; tai yra, atsižvelgiant į „L“ egzempliorių, galite sukurti „L“ egzempliorių, turintį sprendimą, jei ir tik tuo atveju, jei „L“ pavyzdys turi sprendimą. Formaliai kalbant, kiekviena „NP“ problema L sumažėja iki L.

Atkreipkite dėmesį, kad L atvejis turi būti polinominis skaičiuojamas laikas ir jo polinomo dydis yra L '; Taigi, išsprendžiant NP-pilną problemą polinominiu laiku, mes galime išspręsti polinominį laiką visoms NP problemoms.

Štai pavyzdys: tarkime, kad žinome, kad trijų spalvų grafikai yra NP sunki problema. Mes norime įrodyti, kad Būlio formulių patenkinamumo problema taip pat yra NP sunki problema.

Kiekvienai vertex v vertei yra du loginiai kintamieji v_h ir v_l ir reikalavimas (v_h arba v_l): kiekviena pora gali turėti tik reikšmes {01, 10, 11}, kurias mes galime laikyti 1, 2 ir 3 spalvomis.

Kiekvienam kraštui (u, v) privalome: (u_h, u_l)! = (V_h, v_l). Tai yra

not ((u_h and not u_l) and (v_h and not v_l) or ...) išvardijamos tos pačios konfigūracijos ir sąlygos, kurių nė vienas iš jų nebuvo įvykdytas.

AND „kartu visi šie suvaržymai suteikia Būlio formulę, turinčią polinomo dydį ( O(n+m) ). Galite patikrinti, ar skaičiavimui taip pat reikalingas polinomasis laikas: kiekvienam viršūnei ir kiekvienam kraštui sukuriate paprastą O(1) medžiagą.

Jei galite išspręsti loginę formulę, kurią sukūriau, taip pat galite išspręsti grafiko spalvą: kiekvienai kintamųjų porai v_h ir v_l leiskite spalvai v atitikti šių kintamųjų reikšmes. Pagal formulę, kaimynai neturės tų pačių spalvų.

Todėl, jei grafikų 3 spalvos yra NP-užbaigtos, tada tinkamumas yra loginė formulė.

Žinome, kad 3 spalvų grafikai yra NP-užbaigti; tačiau, istoriškai, mes sužinojome, kad pirmiausia parodydami loginio schemos vykdymo NP pilnumą, ir tada mes jį sumažiname iki 3 spalvų (vietoj priešingos).

5
11 февр. Atsakymą pateikė Jonas Kölker , vasario 11 d. 2009-02-11 10:26 '09 10:26 am. 2009-02-11 10:26