Reducci?? (complexitat)

De Viquip??dia

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 es redu??ble a un problema B, una soluci?? per a B d??na 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.

[edita] 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 es 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 ?? b = ((a + b)² ??? a² ??? b²)/2.

Tamb?? tenim una reducci?? en l'altre 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 que nom??s podem fer servir la funci?? d'elevaci?? al quadrat un cop, i nom??s al final. En aquest cas, encara que s'ens 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'altre 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 que la multiplicaci?? ??s en general m??s dif??cil que l'elevaci?? al quadrat. Aix?? correspon a una reducci?? molts-a-un.

[edita] 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 redu??r 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.

[edita] Exemples

Per a mostrar que un problema de decisi?? P ??s indecidible hem de trobar una reducci?? des d'un problema decisional del qu?? ja coneguem 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.

[edita] Tipus i aplicacions de les reduccions

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 debils 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 redu??r un dificil-de-resoldre problema 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?? es 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.