Classes de problemes – P i NP
Entrades | Problemes | Classes de problemes (no excloents) | |
[latex]x[/latex] | [latex]\pi[/latex] | P | Coneixem algorismes amb temps pitjor polinomial (o millor) per a decidir el problema. |
NP | Coneixem algorismes en temps polinòmic indeterminista per a verificar si una solució és correcta. |
Exemples de problemes que estan en NP:
- HAM – és difícil trobar un cicle Hamiltonià en un graf (backtracking), però donada una sentència de vèrtexs és fàcil comprovar si és una solució.
- Element mínim.
- TSP (problema del viatjant de comerç).
- Colorabilitat.
- Quadrat llatí.
- Sudoku.
Teorema
[latex]P \subseteq NP[/latex]
Queda una pregunta clau: [latex]P = NP[/latex]?
Reducció
Siguin [latex]L_1 \le E_1[/latex] i [latex]L_2 \le E_2[/latex] dos problemes decisionals. Diem que [latex]L_1[/latex] es redueix a [latex]L_2[/latex] en temps polinòmic si podem trobar un algorisme polinòmic [latex]A: L_1 \rightarrow L_2[/latex], és a dir, que converteixi tota solució a [latex]E_1[/latex] en una solució d'[latex]E_2[/latex].
En altres paraules, una reducció en temps polinòmic d'[latex]L_1[/latex] a [latex]L_2[/latex] és un algorise [latex]R: E_1 \rightarrow E2 / \forall x \in E_1: x \in L1 \Leftrightarrow R(x) \in L_2[/latex].
Podem reduir, per exemple, el problema del graf hamiltonià (HAM) al problema del viatjant de comerç (TSP).
Teorema: Si [latex]L_1 \le_p L_2[/latex] i [latex]L_2 \in P[/latex], llavors [latex]L_1 \in P[/latex].
Un problema decisional [latex]L[/latex] és NP-hard si tot problema en NP es pot reduir a ell en temps polinòmic. [latex]L \in \text{NP-hard} \Leftrightarrow \forall L' \in NP, L' \le_p L[/latex].
Un problema és NP-complet si és NP-hard i es troba en NP.
Teorema:
[latex]L \in NP-hard, L \in P \Leftrightarrow P = NP[/latex].
Teorema:
[latex]\left\{\begin{array}{l}L_1 \in \text{NP-C} \\ L_2 \in NP \\ L_1 \hookrightarrow L_2\end{array}\right\} L_2 \in NP-C[/latex]
Teorema de Cook (~1970)
[latex]\small\text{CIRCUIT-SAT} \normalsize\in \small\text{NP-C}[/latex] (va ser el primer problema NP-complet).
El problema decisional CIRCUIT-SAT pren com a entrada un circuit amb [latex]n[/latex] entrades booleanes, una sortida i portes AND, OR i NOT i el que pregunta és, «hi ha alguna entrada del circuit que faci que la sortida sigui 1?».
Nota: Una possible solució donada per justificar que un problema decisional té solució s'anomena testimoni.
Solucions pràctiques per a problemes NP
- Heurístiques.
- Aproximacions.
- Paral·lelisme, ordinadors quàntics…
El problema de l'aturada
A part de les classes de problemes P, NP i NP-C n'hi ha moltes d'altres, i una d'elles que cal mencionar és la dels problemes irresolubles: aquells que l'ordinador (o millor dit, una màquina de Turing) no pot solucionar.
Un exemple de problema irresoluble és el de l'aturada: donada la descripció d'un programa i el seu estat inicial, determinar si el programa, si l'executem, arribarà a completar-se o bé funcionarà fins la fi de l'eternitat. Podem veure-ho amb el següent programa d'exemple:
typedef String Programa; typedef String Entrada; // Funció que retorna cert si el programa p, donada l'entrada // x, arriba a aturar-se bool acaba(Programa p, Entrada x); void vinga(Programa p) { // Entra en un bucle infinit si el programa p, donant-li com a entrada // el mateix codi del programa, arriba a aturar-se if (acaba(p, p)) while (true); } |
Si analitzem aquest programa i executem vinga(vinga) veiem que pot haver-hi dos casos:
- Que acabi – si acaba, vinga entra en el bucle i no acaba → contradicció.
- Que no acabi – si no acaba, vinga acaba → contradicció.
Així doncs, no es pot solucionar el problema de l'aturada.
You are reading: Apunts d'Estructures de Dades i Algorismes
- Apunts d'Estructures de Dades i Algorismes: Càlcul de costs
- Apunts d'Estructures de Dades i Algorismes: Dividir i Vèncer
- Apunts d'Estructures de Dades i Algorismes: Diccionaris
- Apunts d’Estructures de Dades i Algorismes: Grafs
- Apunts d'Estructures de Dades i Algorismes: Cerca exhaustiva
- Apunts d'Estructures de Dades i Algorismes: Les classes de problemes P i NP
- Apunts d'Estructures de Dades i Algorismes: Programació dinàmica