Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa

I 0 flashcards i 3 preguntes més al document.

Text del document

APUNTS ESTRUCTURES DE DADES I ALGORISMES Grau en Enginyeria Informàtica Universitat Politècnica de Catalunya AprenAI 2026-2027 Apunts de Teoria de la Complexitat (EDA, FIB): problemes decisionals, classes P, NP i EXP, testimonis, verificadors, reduccions polinòmiques i problemes NP-complets.

APREN.AI Índex 1 Problemes decisionals i classes de complexitat en temps: P i EXP Definició de problemes com a objectes matemàtics Agrupació en classes segons el pitjor cas: P i EXP 2 Indeterminisme, testimonis i la classe NP Determinisme enfront d'indeterminisme Concepte i formulació del testimoni La classe NP i la jerarquia P NP EXP 3 Reduccions polinòmiques, NP-duresa i NP-completesa El concepte de reducció polinòmica Problemes NP-difícils (NP-hard) i NP-complets Exemples clàssics de problemes NP-complets 4 Resum per repassar Classes de complexitat temporals Indeterminisme i classe NP Reduccions polinòmiques i NP-completesa Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 1 1 Problemes decisionals i classes de complexitat en temps: P i EXP EN ACABAR SABRÀS Definir formalment un problema decisional com a subconjunt d'entrades. Diferenciar les classes P i EXP segons la seva tractabilitat i formulació matemàtica. PENSA-HI ABANS DE LLEGIR 1 Un ordinador pot resoldre en la pràctica qualsevol problema si disposem de prou temps?

Definició de problemes com a objectes matemàtics La teoria de la complexitat s'encarrega d'ordenar i agrupar els problemes computacionals segons la quantitat de recursos que requereixen per resoldre's. Dins d'aquest àmbit, ens centrem especialment en els problemes decisionals, que són aquells que retornen una resposta binària: SÍ o NO. Qualsevol problema que no sigui decisional es pot reformular per esdevenir-ne un.

Matemàticament, un problema decisional es representa a través del subconjunt d'entrades que compleixen una propietat sobre un conjunt global d'entrades : A partir d'aquí es distingeixen dos tipus d'entrades en el domini de dades representable per un computador: Entrades positives: elements que pertanyen a i produeixen una sortida afirmativa (SÍ). Entrades negatives: elements del conjunt , els quals produeixen una sortida negativa (NO). Mida de l'entrada: es denota com a i correspon al nombre de símbols emprats per codificar l'entrada.

Agrupació en classes segons el pitjor cas: P i EXP Un problema computacional reuneix les entrades positives, mentre que una classe de complexitat agrupa diversos problemes que comparteixen el mateix cost de resolució. Per mesurar el cost, classifiquem els algorismes segons el seu temps de decisió en el pitjor cas.

Així, definim formalment la classe com el conjunt de problemes que són decidibles en un temps com a màxim : A partir d'aquesta definició fonamental, establim les dues primeres grans famílies de problemes deterministes: A T E A = {x E T(x)} A E A x TIME(t) A t TIME(t) = {A A decidible en temps t} Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 2 Classe Definició matemàtica Comportament Tractabilitat P Temps polinòmic Tractables EXP Temps exponencial Intractables Com que qualsevol polinomi creix més lentament que una funció exponencial, se sap amb certesa que . Això implica que existeixen problemes intractables a EXP que de cap manera poden pertànyer a la classe P.

ERROR FREQÜENT Confondre un problema no decisional amb un problema intractable. Que un problema demani un valor o una optimització no vol dir que no es pugui tractar: sempre es pot transformar en una versió decisional afegint una fita o llindar a la sortida. COMPROVA-HO 2 Quina relació estricta d'inclusió hi ha entre les classes P i EXP? ESQUEMA Classes temporals bàsiques IDEES CLAU Un problema decisional només admet com a sortida SÍ o NO. La classe conté els problemes decidibles en un temps menor o igual a en el pitjor cas. La classe P conté els problemes resolubles en temps polinòmic (tractables). La classe EXP conté els problemes d'ordre exponencial (intractables), complint-se .

COMPROVA EL QUE HAS APRÈS 3. Com es defineix formalment el conjunt que representa un problema decisional? 4. Per què es diu que els problemes de la classe EXP són intractables? TIME(n ) k>0 k TIME(2 ) k>0 nk P EXP EXP (Intractables) Unió de classes exponencials P (Tractables) Unió de classes polinòmiques TIME(t) t P EXP Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 3 Test Encercla la resposta correcta. Les solucions són al final. 5. Quin tipus de sortida ofereix sempre un problema decisional? 6. Com es defineix matemàticament la classe P? 7. Quina relació és certa respecte a P i EXP? 8. Què representa "x" en l'anàlisi de complexitat?

2 Indeterminisme, testimonis i la classe NP EN ACABAR SABRÀS Comprendre el concepte de testimoni i el funcionament d'un verificador polinòmic. Explicar les relacions d'inclusió entre P, NP i EXP i els escenaris oberts de la teoria. PENSA-HI ABANS DE LLEGIR 9 És igual de difícil resoldre un trencaclosques des de zero que comprovar si una solució que et donen feta és correcta? Determinisme enfront d'indeterminisme Un algorisme determinista segueix una trajectòria única de còmput des de l'estat inicial fins a la solució. En canvi, un algorisme indeterminista pot ramificar-se i explorar múltiples camins de càlcul simultàniament.

L'execució d'un algorisme polinòmic indeterminista es pot desglossar conceptualment en dues fases: Una llista ordenada a) SÍ o NO b) Un enter positiu c) Un valor òptim d) Unió de TIME( ) per k major que 0 a) nk Unió de TIME( ) per k major que 0 b) 2nk Intersecció de TIME( ) amb EXP c) nk Problemes amb temps no polinòmic d) EXP és un subconjunt estricte de P a) No tenen cap relació d'inclusió b) P és un subconjunt estricte d'EXP c) P és igual a EXP d) El nombre de sortides possibles a) El nombre de símbols per codificar l'entrada b) El valor absolut del resultat c) El temps d'execució de l'algorisme d) Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 4 Concepte i formulació del testimoni Un testimoni és una estructura d'informació que permet verificar que una entrada pertany al problema (és a dir, comprovar la certesa de ).

La mida d'un testimoni mai no serà més gran que la de l'entrada: Formalment, per tal que un problema decisional sigui decidible en temps polinòmic indeterminista, han d'existir un algorisme verificador polinòmic i un polinomi tals que compleixin les condicions següents: Si per a algun testimoni amb . Si per a tot testimoni amb . Així doncs, la definició formal del testimoni és: La classe NP i la jerarquia P NP EXP La classe NP agrupa tots els problemes decidibles en temps polinòmic indeterminista: Per situar un problema dins de la classe NP cal cobrir dos passos: trobar la forma dels testimonis i definir un verificador polinòmic adequat.

Relació entre classes Diferència fonamental pel que fa als testimonis P enfront de NP A P, els testimonis es poden trobar i verificar en temps polinòmic. A NP, els testimonis només es garanteix que es puguin verificar en temps polinòmic. Com que tot problema de P es verifica trivialment, tenim . NP enfront d'EXP Els problemes de NP tenen testimonis verificables polinòmicament. En canvi, els problemes d'EXP poden requerir testimonis exponencialment llargs. Existeix un algorisme estàndard exponencial que cerca i verifica tots els testimonis possibles, d'on s'obté . De tot plegat se'n deriva la cadena d'inclusions: Actualment no se sap del cert si o si .

Malgrat això, atès que és un fet demostrat que , és segur afirmar que almenys una de les dues inclusions ha de ser estricta: Càlcul o generació del testimoni: fase no determinista on s'obté una possible prova o certificat. 1 Càlcul determinista: fase on un algorisme convencional comprova si la prova aportada valida la propietat.

2 y x A T(x) y x A V p(n) x A V (x, y) = SI ˊ y E y p( x ) x / A V (x, y) = NO y E y p( x ) y x A V (x, y) = SI ˊ NP = {A A decidible en temps polin mic indeterminista} o ˋ P NP NP EXP P NP EXP P = NP NP = EXP P = EXP Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 5 Això obre tres únics escenaris possibles de resolució teòrica: ERROR FREQÜENT Pensar que «NP» significa «no polinòmic». En realitat fa referència a «Polinòmic No- determinista». Molts problemes a NP podrien acabar sent polinòmics deterministes si es demostrés que P = NP. COMPROVA-HO 10 Què diferencia bàsicament la classe P de la classe NP pel que fa a la manipulació de solucions?

PROCÉS Fases d'un algorisme polinòmic indeterminista 1 Entrada x Dada del problema amb mida "x" 2 Generació del testimoni Fase indeterminista que produeix y 3 Verificació determinista Algorisme V comprova en temps polinòmic 4 Decisió Retorna SÍ o NO segons la validesa IDEES CLAU Un algorisme indeterminista explora múltiples camins de decisió generant un candidat i verificant-lo. Un testimoni permet certificar en temps polinòmic que una entrada pertany al llenguatge ( ). Es compleix la relació d'inclusió . Com que , necessàriament o bé . COMPROVA EL QUE HAS APRÈS 11. Quins dos requisits són necessaris per classificar un problema dins de la classe NP? 12.

Quines són les tres possibilitats teòriques respecte a les inclusions de P, NP i EXP? P = NP NP = EXP P NP EXP P = NP EXP P NP = EXP y x P NP EXP P = EXP P = NP NP = EXP Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 6 Test Encercla la resposta correcta. Les solucions són al final. 13. Quina condició sobre la mida "y" ha de complir el testimoni d'una entrada x? 14. Quina propietat assegura que P està inclòs dins de NP? 15. Per què sabem del cert que P = NP i NP = EXP no poden donar-se alhora? 16. Què fa el verificador polinòmic V(x, y) quan l'entrada x NO pertany al problema A?

3 Reduccions polinòmiques, NP-duresa i NP- completesa EN ACABAR SABRÀS Definir el concepte de reducció polinòmica i aplicar les seves propietats. Distingir amb precisió entre problemes NP, NP-hard i NP-complets. Descriure la importància de SAT i CNF-SAT com a problemes de referència en NP-completesa. PENSA-HI ABANS DE LLEGIR 17 Si trobéssim una manera ràpida de resoldre el problema més difícil de NP, què li passaria a la resta de problemes de NP?

Sempre és més gran que "x" a) No té cap límit de mida b) La seva mida és exponencial c) La seva mida és "y" <= "x" d) Tot problema d'EXP té verificador exponencial a) P conté tots els algorismes exponencials b) Els algorismes indeterministes no tenen testimonis c) Tot problema de P es resol i verifica en temps polinòmic d) Perquè està demostrat que P != EXP a) Perquè tot algorisme és determinista b) Perquè NP és una classe buida c) Perquè la mida dels testimonis és constant d) Retorna SÍ per algun testimoni a) Retorna NO per a tot testimoni possible b) Entra en un bucle infinit c) Genera un nou camí indeterminista d) Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 7 El concepte de reducció polinòmica La reducció és una eina per resoldre un problema a partir d'un altre.

Si disposem d'un problema que volem solucionar i comptem amb un algorisme per resoldre un segon problema , podem resoldre canalitzant les seves instàncies cap a l'algorisme de . Això és particularment potent quan no es coneix cap mètode directe per resoldre en temps polinòmic, però en canvi sí que es disposa d'un procediment eficient per a . Formalment, siguin i problemes decisionals amb conjunts d'entrades i respectivament. Diem que A es redueix a B en temps polinòmic (denotat ) si existeix un algorisme polinòmic tal que preserva exactament les sortides: Aquesta transformació compleix tres propietats bàsiques: Reflexivitat: , ja que mitjançant la identitat.

Transitivitat: si mitjançant i mitjançant , aleshores mitjançant la composició . Propagació de polinomialitat: per a tot , si i , aleshores A P. L'algorisme compost per resoldre és . Problemes NP-difícils (NP-hard) i NP-complets A partir de la reducció es defineix la dificultat relativa dels problemes de NP: NP-difícil (NP-hard): un problema és NP-difícil si qualsevol problema de la classe NP es pot reduir a ell en temps polinòmic: Això indica que és tan o més complex com el més difícil dels problemes de NP. Cal tenir en compte que un problema NP-difícil pot no pertànyer a NP.

NP-complet: un problema és NP-complet si pertany a NP i alhora és NP-difícil: Diagrama de la relació entre P, NP, NP-complet i NP-hard. Aquesta categoria representa els problemes més complexos de la classe NP.

Per aquest motiu, tenen una importància crítica per determinar si : A B A B A B A B E E A p B F : E E F : E E (x A F (x) B) (x / A F (x) / B) A p B A p A x A F (x) = x A A p B F B p C G A p C G F A, B A p B B P A F B A B NP, B p A A s NP-dif cil e ˊ ı ˊ A A A NP-hard A NP A s NP-complet e ˊ P = NP Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 8 PER RECORDAR-HO Sigui un problema qualsevol que sigui NP-complet: Si s'arriba a trobar un algorisme de temps polinòmic determinista per a un sol problema NP- complet, aleshores automàticament tots els problemes de NP tindran resolució polinòmica determinista.

Exemples clàssics de problemes NP-complets Fins ara no s'ha trobat cap algorisme polinòmic per resoldre cap problema NP-complet. Dos dels problemes de referència fonamentals són: SAT: . Es diu que una fórmula booleana és satisfactible si existeix alguna assignació de variables que faci que avaluï a 1 (cert). CNF-SAT: . La forma normal conjuntiva (CNF) expressa el problema com una conjunció de clàusules (disjuncions de literals). ERROR FREQÜENT Invertir el sentit de la reducció. Si volem provar que A és NP-difícil a partir d'un problema B conegut com a NP-complet, cal reduir B cap a A ( ), i no a l'inrevés. Reduir A a B només demostraria que A no és més difícil que B.

COMPROVA-HO 18 Quines dues condicions han de concórrer perquè un problema decisional sigui considerat NP- complet? ESQUEMA Classificació de problemes de complexitat A P = NP A P {F F s una f rmula booleana satisfactible} e ˊ o ˊ {F F s una f rmula booleana satisfactible en CNF} e ˊ o ˊ B p A NP-hard Tan o més difícils que qualsevol problema de NP NP-complet Intersecció: pertanyen a NP i són NP-hard NP Decidibles en temps polinòmic indeterminista P Subconjunt resoluble en temps polinòmic Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 9 IDEES CLAU Una reducció polinòmica transforma instàncies d'A en instàncies de B preservant el resultat de sortida.

Si i , aleshores es conclou que . Un problema NP-difícil és com a mínim tan complex com qualsevol problema de NP. Els problemes NP-complets són la intersecció entre NP i NP-hard; si un sol d'ells pertany a P, aleshores . SAT i CNF-SAT són exemples fonamentals de problemes NP-complets basats en la satisfactibilitat de fórmules booleanes. COMPROVA EL QUE HAS APRÈS 19. Per què un problema NP-difícil no és necessàriament NP-complet? 20. Què expressa una fórmula booleana en forma normal conjuntiva (CNF)? Test Encercla la resposta correcta. Les solucions són al final. 21. Si A es redueix a B en temps polinòmic i B és a P, què podem deduir? 22. Què caracteritza un problema NP-difícil (NP-hard)? 23.

Què passaria si es trobés un algorisme determinista polinòmic per a SAT? 24. Com es defineix el problema CNF-SAT?

4 Resum per repassar A p B A p B B P A P P = NP Que A pertany a P a) Que B és NP-complet b) Que A és NP-difícil c) Que P és igual a EXP d) Es resol sempre en temps polinòmic a) Sempre pertany a la classe P b) Tots els de NP s'hi redueixen c) Només té entrades negatives d) Tots els problemes esdevindrien intractables a) Es demostraria que P = NP b) Es provaria que NP = EXP c) SAT deixaria de ser decisional d) Algorismes deterministes per a arbres binaris a) Fórmules satisfactibles en forma normal conjuntiva b) Fórmules amb sortida estrictament negativa c) Fórmules booleanes no satisfactibles en disjunció d) Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 10 Classes de complexitat temporals Concepte Definició i significat Problema decisional Problema amb resposta binària (SÍ o NO), formalitzat com el conjunt de les entrades positives.

Conjunt de problemes que es poden decidir en un temps menor o igual a en el pitjor dels casos. Classe P Unió de per a ; problemes resolubles en temps polinòmic determinista (tractables). Classe EXP Unió de per a ; problemes d'ordre temporal exponencial determinista (intractables). Indeterminisme i classe NP Concepte Definició i significat Algorisme indeterminista Algorisme que pot bifurcar-se i explorar simultàniament múltiples camins de computació fins a la solució. Testimoni ( ) Certificat de mida acotada ( ) que permet verificar de forma determinista i polinòmica que .

Classe NP Conjunt de problemes decidibles en temps polinòmic indeterminista (verificables en temps polinòmic determinista). Jerarquia P, NP i EXP Cadena d'inclusions ; com que , és cert que . Reduccions polinòmiques i NP-completesa Concepte Definició i significat Reducció polinòmica ( ) Funció polinòmica que preserva la pertinença ( ); és reflexiva i transitiva. Propagació de polinomialitat Propietat segons la qual si i , aleshores necessàriament . NP-difícil (NP-hard) Problema al qual es redueixen en temps polinòmic tots els problemes de la classe NP ( ).

A = {x E T(x)} TIME(t) t TIME(n ) k k > 0 TIME(2 ) nk k > 0 y y x x A P NP EXP P EXP P = NP NP = EXP A p B F x A F (x) B A p B B P A P A B NP, B p A Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 11 Concepte Definició i significat NP-complet Problema que pertany a NP i alhora és NP-difícil; si un sol NP-complet té solució polinòmica, aleshores . SAT i CNF-SAT Problemes NP-complets clàssics que determinen la satisfactibilitat de fórmules booleanes generals o en forma normal conjuntiva. P = NP Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 12 Solucions de les preguntes de repàs 1.

No sempre de manera viable: els problemes amb complexitat exponencial (EXP) creixen tan ràpidament que esdevenen intractables fins i tot per a entrades moderades. 2. La classe P és un subconjunt estricte d'EXP ( ), de manera que tot problema tractable és exponencial, però existeixen problemes a EXP que mai es podran resoldre en temps polinòmic. 3. Com el conjunt , format exclusivament per les entrades positives que verifiquen la propietat . 4. Perquè el seu temps de resolució en el pitjor cas creix de forma exponencial respecte a la mida de l'entrada ( ), fent-los inviables per a entrades grans. 5. b) SÍ o NO.

Els problemes decisionals es caracteritzen exclusivament per tenir com a resposta un resultat binari de SÍ o NO. 6. a) Unió de TIME( ) per k major que 0. La classe P és la unió de totes les classes de complexitat temporal polinòmiques per a tot k major que zero. 7. c) P és un subconjunt estricte d'EXP. Està demostrat que P està contingut estrictament dins d'EXP, per tant P no és igual a EXP. 8. b) El nombre de símbols per codificar l'entrada. La mida "x" és el nombre de símbols necessaris per codificar l'entrada en un ordinador. 9. Comprovar solucions sol ser molt més fàcil que cercar-les: precisament aquesta asimetria fonamenta la diferència intuïtiva entre les classes P i NP. 10.

A P una solució o testimoni es pot trobar i verificar en temps polinòmic, mentre que a NP només es requereix poder verificar la solució candidata en temps polinòmic. 11. Cal identificar l'estructura dels testimonis per a les entrades positives i trobar un algorisme verificador polinòmic capaç de comprovar-los. 12. Les tres opcions són: que totes dues inclusions siguin estrictes ( ), que , o bé que . 13. d) La seva mida és "y" <= "x". La mida del testimoni mai no serà major que la de l'entrada, complint "y" <= "x". 14. d) Tot problema de P es resol i verifica en temps polinòmic.

Com que els problemes de P es poden trobar i verificar en temps polinòmic, compleixen directament la condició de ser verificables en NP. 15. a) Perquè està demostrat que P != EXP. Com que se sap amb seguretat que P és un subconjunt estricte d'EXP, no poden coincidir simultàniament les tres classes. 16. b) Retorna NO per a tot testimoni possible. Per definició formal, si x no pertany a A, el verificador ha de retornar NO per a qualsevol testimoni y vàlid. 17. Gràcies a les reduccions polinòmiques, tots els altres problemes de NP quedarien automàticament resolts de manera ràpida, fent que P fos igual a NP. 18.

Ha de complir dues condicions simultànies: pertànyer a la classe NP ( ) i ser NP-difícil ( ). 19. Perquè pot ser tan o més difícil que els problemes de NP sense pertànyer ell mateix a la classe NP (podria requerir més recursos o fins i tot no ser verificable en temps polinòmic). 20. Expressa la fórmula com una conjunció de clàusules (és a dir, una sèrie de clàusules unides per operadors «I» lògics). P EXP A = {x E T(x)} T 2nk nk P NP EXP P = NP EXP P NP = EXP A NP B NP, B p A Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 13 21. a) Que A pertany a P. La propietat de propagació garanteix que en resoldre B polinòmicament, també resolem A en temps polinòmic. 22.

c) Tots els de NP s'hi redueixen. Per definició, un problema és NP-difícil si qualsevol problema pertanyent a NP es pot reduir a ell en temps polinòmic. 23. b) Es demostraria que P = NP. Com que SAT és NP-complet, trobar una solució a P per a ell implicaria immediatament que P = NP. 24. b) Fórmules satisfactibles en forma normal conjuntiva. CNF-SAT és el conjunt de fórmules booleanes satisfactibles expressades específicament com una conjunció de clàusules. Teoria de la Complexitat: Classes P, NP, EXP i NP-completesa 14