Apunts d’Estructures de Dades i Algorismes: Les classes de problemes P i NP

Classes de problemes – P i NP

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:

1. Que acabi – si acaba, vinga entra en el bucle i no acaba → contradicció.
2. Que no acabi – si no acaba, vinga acaba → contradicció.

Així doncs, no es pot solucionar el problema de l'aturada.