NP yra kalbų, turinčių daugianario laiko tikrintuvus, klasė
Klasė NP, kuri reiškia "nedeterministinį daugianario laiką", yra pagrindinė skaičiavimo sudėtingumo teorijos sąvoka, teorinės kompiuterių mokslo poskyris. Norint suprasti NP, pirmiausia reikia suvokti sprendimo problemų, kurios yra klausimai, kurių atsakymas yra taip arba ne, sąvoką. Kalba šiame kontekste reiškia eilučių rinkinį tam tikroje abėcėlėje, kur kiekviena eilutė koduoja sprendimo problemos atvejį.
Sakoma, kad kalba (L) yra NP, jei yra (L) daugianario laiko tikrintuvas. Tikriklis yra deterministinis algoritmas (V), kuriam reikia dviejų įvesčių: egzemplioriaus (x) ir sertifikato (y). Pažymėjimas (y) taip pat žinomas kaip „liudytojas“ arba „įrodymas“. Tikrintojas (V) patikrina, ar sertifikatas (y) patvirtina, kad (x) priklauso kalbai (L). Formaliai kalba (L) yra NP, jei egzistuoja daugianario laiko algoritmas (V) ir polinomas (p(n)), kad kiekvienai eilutei (x L) yra eilutė (y) su ( |y|. leq p(|x|)) ir (V(x, y) = 1). Ir atvirkščiai, kiekvienai eilutei (x ne L) nėra tokios eilutės (y), kuri (V(x, y) = 1).
Norėdami išsiaiškinti šią sąvoką, apsvarstykite gerai žinomą „Bulio patenkinimo“ (SAT) problemą. SAT problema klausia, ar tam tikroje Būlio formulėje yra tiesos reikšmių priskyrimas kintamiesiems taip, kad formulė būtų įvertinta kaip teisinga. SAT problema yra NP, nes, atsižvelgiant į Būlio formulę ( phi ) ir tiesos verčių priskyrimą ( alfa ) jos kintamiesiems, polinominiu laiku galima patikrinti, ar ( alfa ) tenkina ( phi ). Čia egzempliorius ( x ) yra Būlio formulė ( phi ), o sertifikatas ( y ) yra priskyrimas ( alfa ). Tikriklis ( V ) patikrina, ar ( alfa ) padaro ( phi ) teisingą, o tai galima padaryti daugianario laiku, atsižvelgiant į ( phi ) dydį.
Kitas iliustruojantis pavyzdys yra „Hamiltono kelio“ problema. Ši problema klausia, ar duotame grafike yra kelias, kuris aplanko kiekvieną viršūnę tiksliai vieną kartą. Hamiltono kelio problema taip pat yra NP, nes, atsižvelgiant į grafiką ( G ) ir viršūnių seką ( P ), galima patikrinti daugianario laiku, ar ( P ) yra Hamiltono kelias ( G ). Šiuo atveju pavyzdys ( x ) yra grafikas ( G ), o sertifikatas ( y ) yra viršūnių seka ( P ). Tikriklis ( V ) patikrina, ar ( P ) sudaro Hamiltono kelią, o tai galima padaryti daugianario laiku, atsižvelgiant į ( G ) dydį.
Polinominio laiko patikrinimo sąvoka yra svarbi, nes ji suteikia galimybę apibūdinti problemas, kurias galima efektyviai patikrinti, net jei sprendimo rasti skaičiavimais neįmanoma. Tai veda prie garsiojo klausimo, ar (P = NP), kuris klausia, ar kiekviena problema, kurios sprendimas gali būti patikrintas daugianario laiku, gali būti išspręstas ir daugianario laiku. Klasė ( P ) susideda iš sprendimų problemų, kurias daugianario laiku galima išspręsti deterministine Tiuringo mašina. Jei ( P = NP ), tai reikštų, kad kiekviena problema su daugianario laiko tikrintuvu taip pat turi daugianario laiko sprendiklį. Šis klausimas išlieka viena iš svarbiausių atvirų kompiuterių mokslo problemų.
Viena iš pagrindinių NP savybių yra tai, kad jis yra uždarytas polinominio laiko sumažinimo metu. Polinominio laiko redukcija iš kalbos ( L_1 ) į kalbą ( L_2 ) yra daugianario laiko apskaičiuojama funkcija ( f ), kad ( x L_1 ) tada ir tik tada ( f(x) L_2 ). Jei egzistuoja daugianario laiko redukcija nuo ( L_1 ) iki ( L_2 ) ir ( L_2 ) yra NP, tada ( L_1 ) taip pat yra NP. Ši savybė yra naudinga tiriant NP užbaigtumą, kuris nustato „sunkiausias“ NP problemas. Problema yra NP-baigta, jei ji yra NP ir kiekviena NP problema gali būti sumažinta iki jos daugianario laiku. SAT problema buvo pirmoji problema, įrodyta, kad ji yra NP pilna, ir ji yra pagrindas įrodyti kitų problemų NP išsamumą.
Norėdami toliau iliustruoti daugianario laiko patikrinimo sąvoką, apsvarstykite „pogrupio sumos“ problemą. Ši problema klausia, ar egzistuoja tam tikro sveikųjų skaičių rinkinio poaibis, kuris sumuojasi į nurodytą tikslinę vertę. Poaibių sumos problema yra NP, nes, atsižvelgiant į sveikųjų skaičių aibę ( S ), tikslinę reikšmę ( t ) ir ( S ) poaibį ( S' ), galima per polinominį laiką patikrinti, ar elementų suma ( S' ) lygus ( t ). Čia pavyzdys ( x ) yra pora ( (S, t) ), o sertifikatas ( y ) yra poaibis ( S' ). Tikriklis ( V ) patikrina, ar ( S' ) elementų suma yra lygi ( t ), o tai galima padaryti daugianario laiku, atsižvelgiant į ( S ) dydį.
Polinominio laiko patikrinimo svarba neapsiriboja teoriniais svarstymais. Praktiškai tai reiškia, kad dėl NP problemų, jei pateikiamas pasiūlytas sprendimas (sertifikatas), jis gali būti efektyviai patikrintas. Tai turi reikšmingų pasekmių kriptografiniams protokolams, optimizavimo problemoms ir įvairioms sritims, kuriose svarbu patikrinti sprendimo teisingumą.
Apibendrinant galima pasakyti, kad klasė NP apima sprendimų problemas, kurių pasiūlytas sprendimas gali būti patikrintas daugianario laiku deterministiniu algoritmu. Ši koncepcija yra skaičiavimo sudėtingumo teorijos pagrindas ir turi didelę reikšmę tiek teoriniams, tiek praktiniams kompiuterių mokslo aspektams. NP, daugianario laiko patikrinimo ir susijusių sąvokų, tokių kaip NP išsamumas, tyrimas ir toliau yra gyvybinga ir svarbi tyrimų sritis.
Kiti naujausi klausimai ir atsakymai apie sudėtingumas:
- Ar PSPACE klasė nėra lygi EXPSPACE klasei?
- Ar P sudėtingumo klasė yra PSPACE klasės poaibis?
- Ar galime įrodyti, kad Np ir P klasės yra vienodos, rasdami veiksmingą daugianario sprendimą bet kuriai NP užbaigtai problemai deterministinėje TM?
- Ar NP klasė gali būti lygi EXPTIME klasei?
- Ar PSPACE yra problemų, kurioms nėra žinomo NP algoritmo?
- Ar SAT problema gali būti visiška NP problema?
- Ar problema gali būti NP sudėtingumo klasėje, jei yra nedeterministinė tiūro mašina, kuri ją išspręs daugianario laiku
- Ar iš tikrųjų P ir NP yra ta pati sudėtingumo klasė?
- Ar P sudėtingumo klasėje kiekviena kalba be konteksto?
- Ar yra prieštaravimas tarp NP apibrėžimo kaip sprendimų problemų klasės, naudojant daugianario laiko tikrintuvus, ir to, kad P klasės uždaviniai taip pat turi daugianario laiko tikrintuvus?
Peržiūrėkite daugiau klausimų ir atsakymų skyriuje „Sudėtingumas“.