Clase de complexitate NP (polinomial nedeterminist)

In teoria complexitatii computationale, NP sunt unele din clasele fundamentale de complexitate. Abrevierea NP inseamna timp polinomial nedeterminist. Intuitiv, NP reprezinta toate problemele de decizie pentru care instantele unde raspunsul este da au dovezi destul de verificabile ale faptului ca raspunsul este intr adevar da. Mai exact, aceste dovezi trebuie sa fie verificabile in timp polinomial de catre o masina Turing determinista. Intr-o definitie formala echivalenta, NP este setul de probleme decizionale in care instantele da pot fi acceptate in timpi polinomiali de catre o masina Turing non-determinista. Echivalenta celor doua definitii provine din faptul ca un algoritm pe un tip de masina non-determinista consta in doua faze, prima constand intr-o presupunere a solutiei, care este generata intr-un mod nondeterminist, iar a doua constand intr-un algoritm determinist care care verifica sau nu presupunerea ca solutia este valida. Clasa de complexitate P este inclusa in NP, dar NP contine multe probleme importante, cele mai grele fiind problemele NP-complete, ale caror solutii pot fi aflate cu oricare alta problema NP in timp polinomial. Cea mai importanta intrebare deschisa in teoria complexitatii, problema P=NP, se refera la faptul ca, daca algorimi in timp polinomial chiar exista pentru probleme NP-complete, si prin urmare, pentru toate problemele NP. Majoritatea considera ca nu este cazul. Definitie: Complexitatea clasei de probleme NP poate fi definita in termeni NTIME astfel:

Alternativ, NP poate fi definit folosind masini Turing deterministe pentru verificare. Un limbaj L este NP daca si numai daca exista polinomialele p si q si o masina Turing determinista M, astfel incat: Pentru oricare x si y, M ruleaza in timpul p(|x|) pentru intrarea (x,y) Pentru oricare x inclus in L, exista un sir y de lungime q(|x|) ,astfel incat M(x,y)=1 Pentru oricare x care nu este inclus in L si toate sirurile y de lungime q(|x|), M(x,y)=0

Introducere: Multe probleme naturale de informatica sunt incluse de clasa NP. In particular, versiunile de decizie ale multor probleme de cautare si optimizare sunt continute in NP. Definitie bazata pe verificare: Pentru a explica definitia NP bazata pe verificari, se considera problema sumei de subseturi:

Se presupune ca exista niste numere intregi , ca {-7,-3,-2,5,8} si se vrea sa se stie daca suma unora este 0. In acest exemplu, raspunsul este da, fiindca subsetul {-3,-2,5} corespunde sumei (-3)+(-2)+5=0. Sarcina de a decide daca un astfel de subset cu suma 0 exista se numeste problema sumei subseturilor. Pentru a raspunde daca unele dintre numerele intregi au suma 0, putem crea un algoritm care obtine toate subseturile posibile. Cum numarul de intregi pe care il introducem in algoritm devine mai mare, numarul de subseturi creste exponential si timpul computational creste. Oricum, se observa ca daca se da un anumit subset, putem verifica usor daca suma subsetului este 0, prin insumarea intregilor din subset. Daca suma este 0, acel subset este dovada dovada faptului ca raspunsul este da. Un algoritm care verifica daca un subset are suma 0 este numit verificator. O problema se spune ca este in NP daca exista un verificator pentru problema care se executa in timp polinomial. In cazul problemei sumei subsetului , verificatorul necesita doar timp polinomial, din acest motiv problema sumei subsetului este in clasa NP. Versiunea raspunsului nu a acestei probleme este: considerandu-se un set finit de intregi, are fiecare subset nevid o suma nenula?. Se remarca faptul ca definitia bazata pe verificare a NP nu necesita un certificat usor de verificat pentru raspunsul nu. Clasa de probleme cu un astfel de certificat pentru raspunsul nu se numeste clasa co-NP. De fapt, este o intrebare deschisa daca toate probleme din clasa NP au de asemenea certificate pentru raspunsul nu si acestea sunt incluse in co-NP. Definitia masinii: Echivalent definitiei bazate pe verificare este urmatoarea caracterizare: NP este un set de probleme decizionale ce pot fi rezolvate de catre o masina Turing nondeterminista care ruleaza in timp polinomial. Aceasta definitie este echivalenta cu definitia bazata pe verificare deoarece o masina Turing non-determinista ar putea rezolva o problema NP in timp polinomial prin selectarea non-determinista a unui certificat si rularea verificarii certificatului. Similar, daca o astfel de masina exista, atunci un verificator al timpului polinomial poate fi format din aceasta. Exemple: Toate probleme in clasa P( se da un certificat pentru o problema in clasa P, putem ignora certificatul si rezolva problema in timp polinomial. Alternativ, se observa ca o masina Turing determinista este de asemenea o masina Turing non-determinista care se intampla sa nu foloseasca nici un non-determinism) Versiunea problemei de decizie a problemei de factorizare a intregilor: se dau intregii n si k, exista un factor f cu 1<f<k si f divide n? Problema isomorfismului grafurilor de determinare daca 2 grafuri pot fi desenate identic. Toate problemele NP-complete, de exemplu: O varianta a problemei vanzatorului care calatoreste, unde vrem sa stim daca exista o ruta sau o lungime care trece prin toate nodurile intr-o anumita retea.

De ce unele probleme NP sunt greu de rezolvat? Din cauza multor probleme importante din aceaste clasa, s-au facut eforturi mari de gasire a unor algoritmi de timp polinomial pentru problemele din NP. Oricum, ramane un numar mare de probleme care par sa necesite un timp super polinomial. Daca aceste probleme chiar nu pot fi rezolvate in timp polinomial este una dintre cele mai mare intrebari in informatica (P=NP) O notiune importanta in aceste context este setul de probleme decisionale NPcomplete, care este un subset al NP si poate fi descris ca cea mai grea problema din clasa NP. Daca ar fi un algoritm in timp polinomial pentru fiecare din acestea, atunci ar fi un algoritm in timp polinomial pentru toate probleme din NP. Din acest motiv, si din cauza ca cercetarile au esuat sa gaseasca un algoritm polinomial pentru oricare problema NP-complete, odata ce o problema a fost demonstrata ca fiind NPcomplete este considerat ca un semn ca un algoritm polinomial pentru aceasta problema este putin posibil sa existe. Oricum, in practica, in locul consumarii de resurse informatice pentru gasirea unei solutii optime, o solutie suficient de buna poate fi des gasita in timpul polinomial. De asemenea, aplicatiile din viata reala a unora dintre probleme sunt mai simple decat echivalentele teoretice. Echivalenta definitiilor: Cele 2 definitii ale NP ca o clasa de probleme rezolvabile de catre o masina Turing non-determinista in timp polinomia si clasa de probleme verificabile de catre o masina Turing determinista in timp polinomial sunt echivalente. Pentru a arata aceasta, in primul rand se presupune ca avem un verificator determinist. O masina non-determinista poate rula in mod non-determinist verificatorul pe toate sirurile dovada posibile. Daca oricare dovada este valida, unele cai o vor accepta, daca nu, sirul nu este in limbajul potrivit si va fi respins. In schimb, presupunem ca avem o masina Turing nondeterminista numinta A care accepta un limbaj L. Trebuie sa existe cel putin o cale acceptate si un sir ce descrie aceasta cale este dovada furnizata catre verificator. Verificatorul poate atunci simula determinist A, urmand numai calea acceptata, si verificand ca este acceptata la final. Daca A respinge intrarea, nu exista nicio cale acceptabila si verificatorul nu o va accepta niciodata. Relatii cu alte clase: NP contine toate probleme din P, intrucat una poate verifica orice instanta a problemei prin a ignora dovada si a o rezolva. NP este continut in PSPACE- pentru a demonstra aceasta este suficient sa construim o masina PSPACE care trece peste toate sirurile de dovezi si ofera pe fiecare unui verificator de timp polinomial. Intrucat o masina de timp polinomial poate doar sa citeasca polinomial multi biti, nu poate folosi mai mult decat spatiu polinomial, nici nu poate citi un ir de dovezi care ocup mai mult decat spaiu polinomial. NP este de asemenea continut in EXPTIME, intrucat acelasi algoritm opereaza in timp exponential. Complementul clasei NP, NP-co, contine acele probleme care au o simpla dovada pentru instanta nu, uneori numita contraexemple.
3

NP este definit utilizand doar masini deterministe. Daca permitem verificatorului sa fie probabilistic, obtinem clasa MA rezolvabila utilizand un protocol Arthur-Merlin fara comunicare de la Merlin la Arthur. NP este o clasa de probleme decizionale; analog clasa de probleme de functionare este FNP. Alte caracterizari: Privind teoria complexitatii descriptiva , NP corespunde exact setului de limbaje definibile prin logica existentiala de ordin 2(teorema lui Fagin). NP poate fi vazut ca un sistem foarte simplu de dovedire interactiva, unde unde doveditorul vine cu certificatul doveditor si verificatorul este o masina determinista in timp polinomial care o verifica. Este complet deoarece sirul dovada corect o sa-l faca sa-l accepte daca exista unul, si este corect pentru ca verificatorul nu poate accepta daca nu exista un astfel de sir. Un rezultat major al teoriei complexitatii este ca NP poate fi caracterizat ca probleme rezolvabile prin dovezi verificabile probabilistic unde verificatorul foloseste O(log n) biti aleatori si examineaza numai un numar constant de biti din sirul dovada. Informal, asta inseamna ca verificatorul NP descris mai sus poate fi inlocuit cu unul care verifica prin sondaj cateva locuri din sirul dovada si folosind un numar limitat de aruncari de moneda poate determina raspunsul corect cu o probabilitate mare. Acest lucru permite cateva rezultate legate de greutatea algoritmilor de aproximare de verificat. Exemplu: Versiunea decizionala a problemei vanzatorului ce calatoreste este in NP. Dandu-se ca intrare o matrice de distante intre n orase, problema este de a determina daca exista o ruta care viziteaza toate orasele cu o distanta totala mai mica decat k. Un certificat de dovada poate fi o lista a oraselor. Atunci verificarea poate fi evident executata in timp polinomial de catre o masina Turing deteriminista. Adauga intrarile matricei corespunzatoare rutelor dintre orase. O masina Turing nedeterminista poate gasi o ruta astfel: La fiecare oras vizitat ghiceste orasul urmator de vizitat, pana le-a vizitat pe fiecare. Daca se blocheaza, se opreste imediat. La sfarsit verifica daca ruta pe care a luat-o e mai mica decat k in timpul O(n). Se poate considera fiecare banuiala ca bifurcarea unei noi masini Turing care urmeaza toate rutele posibile, si daca macar o masina gaseste o ruta cu o distanta mai mica decat k, acea masina accepta intrarea. Cautarea binara pe spatiul distantelor posibile poate converti versiunea deciziei problemei vanzatorului ce calatoreste la versiunea optimizata, prin apelarea versiunii deciziei in mod repetat.