Reducció (complexitat)

En teoria de la computabilitat i teoria de la complexitat computacional, una reducció és una transformació d'un problema computacional en un altre problema. Depenent de la transformació utilitzada aquesta pot ser utilitzada per a definir classes de complexitat en un conjunt de problemes.

Intuïtivament, si un problema A és reduïble a un problema B, una solució per a B dona una solució per a A. D'aquesta forma, la resolució d'A no pot ser més difícil que la resolució de B. Escrivim A ≤ B, habitualment amb una subescriptura al ≤ per a indicar el tipus de reducció que es fa servir.

Introducció

Sovint ens trobem intentant resoldre un problema que és similar a un problema que ja hem resolt. En aquests casos, sovint una forma ràpida de resoldre el nou problema és transformar cada instància del nou problema en instàncies del vell problema i resoldre aquestes fent servir la solució existent. Aquest és potser l'ús més obvi de les reduccions.

Un altre, més subtil ús és aquest: suposem que tenim un problema que hem comprovat que és difícil de resoldre, i tenim un problema similar. Podem sospitar que aquest, també, és difícil de resoldre. Ho argumentem per contradicció: suposem que el nou problema és fàcil de resoldre. Llavors, si podem veure que tota instància del vell problema pot ser resolta fàcilment transformant-la en instàncies del nou problema i resolent aquestes, tenim una contradicció. Això estableix que el nou problema és també difícil.

Un exemple molt simple de reducció és el de multiplicació a elevació al quadrat. Suposem que tots sabem com es fa per sumar, restar, elevar al quadrat i dividir entre dos. Podem fer servir aquest coneixement, combinat amb la següent fórmula, per a obtenir el producte de dos nombres qualsevol:

$a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}$

També tenim una reducció en l'altra direcció; òbviament, si podem multiplicar dos nombres, podem elevar al quadrat un nombre. Això sembla implicar que aquests dos problemes són igual de difícils. Aquest tipus de reducció es correspon a la reducció de Turing.

No obstant això, la reducció es torna molt més difícil si afegim la restricció de què només podem fer servir la funció d'elevació al quadrat un cop, i només al final. En aquest cas, encara que se'ns permet fer servir totes les operacions aritmètiques bàsiques, incloent la multiplicació, no existeix una reducció en general, perquè podem haver de computar un nombre irracional com ara ${\sqrt {2}}$ des dels nombres racionals. Anant en l'altra direcció, però, podem elevar al quadrat un nombre amb només una multiplicació, només al final. Fent servir aquesta forma limitada de reducció, hem mostrat el resultat previsible de què la multiplicació és en general més difícil que l'elevació al quadrat. Això correspon a una reducció molts-a-un.

Definicions

Donats dos subconjunts A i B de N i un conjunt de funcions F de N a N tancat per composició, A s'anomena reduïble a B sota F si

$\exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B$

Escrivim

$A\leq _{F}B$

Sigui S un subconjunt de P(N) i ≤ una reducció, llavors S s'anomena tancat sota ≤ si

$\forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Rightarrow A\in S$

Un subconjunt A de N s'anomena difícil per a S si tot problema de S es pot reduir a A:

$\forall s\in S{\mbox{ . }}s\leq A$

Un subconjunt A of N s'anomena complet per a S si A és difícil per a S i A està en S.

Exemples

• Per a mostrar que un problema de decisió P és indecidible, hem de trobar una reducció des d'un problema decisional del qual ja coneixem que és indecidible fins a P. Aquesta funció de reducció ha de ser una funció computable. En particular, sovint mostrem que un problema P és indecidible mostrant que el problema de l'aturada es redueix a P.
• Les classes de complexitat P, NP i PSPACE són tancades sota reduccions de temps polinòmic.
• Les classes de compleitat L, NL, P, NP i PSPACE són tancades sota la reducció en temps logarítmic.

Tipus i aplicacions

Com s'ha descrit a l'exemple superior, hi ha dos tipus principals de reduccions que es fan servir en complexitat computacional, la reducció molts-a-un i la reducció de Turing. Les reduccions molts-a-un donen un camí d'instàncies d'un camí a instàncies d'un altre; les reduccions de Turing computen la solució per a un problema, assumint que l'aletre problema és fàcil de resoldre. La reducció molts-a-un és més dèbil que la reducció de Turing. Les reduccions més dèbils són més efectives separant problemes, pero tenen menys potència, fent les reduccions més difícils de dissenyar.

No obstant això, per a ser útils, les reduccions han de ser fàcils. Per exemple, és bastant possible reduir un problema difícil de resoldre NP-complet com el problema de la satisfactibilitat booleana a un problema trivial com a determinar si un nombre equival a zero, tenint una màquina que redueixi el problema en temps exponencial i escrigui zero només si existeix una solució. Pero això no aconsegueix molt, perquè encara que ara podem resoldre el nou problema, fer la reducció és tan difícil com resoldre el problema vell.

Per això, la noció apropiada de reducció depèn de la classe de complexitat que s'estudiï. Quan s'estudia la classe de complexitat NP i classes més difícils, es fa servir la reducció molts-a-un de temps polinòmic. Quan definim classes en la jerarquia polinomial, es fa servir la reducció de Turing en temps polinòmic. Quan estudiem classes dintre de P com ara NC i NL, es fa servir la reducció d'espai logarítmic. La reducció es fa servir també en teoria de la computabilitat per a mostrar si els problemes són o no són resolubles per màquines; en aquest cas, les reduccions són restringides a només funcions computables.