Diagrama de clases de complexidá pal casu en que P ≠ NP. La esistencia de problemes fuera tantu de P como de NP-completos, foi determinada por Richard Y. Ladner.^[1]

La rellación ente les clases de complexidá P y NP ye una entruga que la teoría de la complexidá computacional entá nun pudo responder. N'esencia, la entruga ¿ye P = NP ? significa: si ye posible "verificar" rápido soluciones positives a un problema del tipu SI/NON (onde "rápido" significa "en tiempu polinómico"), ¿ye qu'entós tamién se pueden "llograr" les respuestes rápido?

Los recursos comúnmente estudiaos en complexidá computacional son:

– El tiempu: por aciu un aproximamientu al númberu de pasos d'execución qu'un algoritmu emplega pa resolver un problema.

– El espaciu: por aciu un aproximamientu a la cantidá de memoria utilizada pa resolver el problema.

Los problemes clasificar en conxuntos o clases de complexidá (L, NL, P, PCompleto, NP, NP-Completu, NP Duru...). Esti artículu va centrar nes clases P y NP.

Considérase'l problema más importante nesti campu, el Clay Mathematics Institute ufiertó un premiu d'un millón de dólares d'Estaos Xuníos para quien desenvuelva la primer demostración correuta.

Exemplu

Consideremos, por casu, el Problema de la suma de subconxuntos, que ye un exemplu d'un problema fácil de verificar, pero que la so respuesta se cree (pero nun foi demostráu) ye malo de calcular/topar. Dau un conxuntu de númberos enteros, ¿Esiste un subconxuntu non vacíu d'ellos onde la suma de los sos elementos ye igual a 0? por casu, ¿Esiste un subconxuntu del conxuntu {−2, −3, 15, 14, 7, −10} tal que la suma de los sos elementos seya 0? La respuesta ye SI, magar puede llevar dalgún tiempu atopar un subconxuntu que satisfai'l requerimientu, según cual sía'l tamañu del conxuntu y subconxuntu. Per otra parte, si daquién afirma que la respuesta ye: «sí, porque la suma de {−2, −3, −10, 15} ye igual a cero», entós podemos comprobar en forma bien rápida y por aciu unes poques cuentes. Verificar que la suma del subconxuntu ye cero ye un procesu muncho más rápido qu'atopar el subconxuntu. La información necesaria pa verificar un resultáu positiva/afirmativu ye llamada un certificáu. Polo que podemos concluyir que dau los certificaos apropiaos, ye posible verificar rápido les respuestes afirmatives del nuesu problema (en tiempu polinomial) y ye ésta la razón pola que'l problema atópase en NP. Una respuesta a la entruga P = NP sería determinar si en problemes del tipu SUMA-SUBCONXUNTU ye tan fácil topar la solución como verificala. Si s'atopa que P nun ye igual a NP, ello significa que dellos problemes NP seríen significativamente más difíciles de topar la so solución que verificar la mesma. La respuesta sería aplicable a tou esti tipu de problemes, non solo al exemplu específicu de SUMA-SUBCONXUNTU.

La restricción a problemes de tipu SI/NON realmente nun ye importante; entá si déxense respuestes más complicaes, el problema resultante resulta equivalente (esto ye si FP = FNP).como esta por casu (m×q)×(n×p) esta de aqui si ye colos sos valores m=-2 n=5 p=-7 q=-10

Contestu del problema

La rellación ente les clases de complexidá P y NP ye estudiada pola teoría de la complexidá computacional, la parte de la teoría de la computación que trata de los recursos riquíos mientres el cálculu pa resolver un problema dau. Los recursos más avezaos son tiempu (¿cuántos pasos son necesarios pa resolver un problema?) y espaciu (¿cuánta memoria ye necesaria pa resolver un problema?).

Nesti tipu d'analís, ríquese un modelu del ordenador pa la que desea estudiar el requerimientu en términos de tiempu. Típicamente, dichos modelos suponen que l'ordenador ye determinista (dau l'estáu actual del ordenador y les variables d'entrada, esiste una única aición posible que l'ordenador puede tomar) y secuencial (realiza les aiciones una dempués de la otra). Estos camientos son afeches pa representar el comportamientu de tolos ordenadores esistentes, entá inclúi a les máquines con computación en paralelu.

Nesta teoría, la clase P consiste de toos aquellos problemes de decisión que pueden ser resueltos nuna máquina determinista secuencial nun periodu de tiempu polinomial en proporción a los datos d'entrada. Na teoría de complexidá computacional, la clase P ye una de les más importantes; la clase NP consiste de toos aquellos problemes de decisión que les sos soluciones positives/afirmatives pueden ser verificaes en tiempu polinómico a partir de ser alimentaes cola información apropiada, o en forma equivalente, que la so solución puede ser topada en tiempu polinómico nuna máquina non determinista. Poro, la principal entruga entá ensin respuesta na teoría de la computación ta referida a la rellación ente estos dos clases:

¿Ye P igual a NP?

Nuna encuesta realizada nel 2002 ente 100 investigadores, 61 creíen que la respuesta yera NON, 9 creíen que la respuesta yera SI, 22 nun taben seguros, y 8 creíen que la entruga podía ser independiente de los axomes anguaño aceptaos, y polo tanto imposible de demostrar pol SI o pol NON.^[2]

Definiciones formales

Más precisamente, un problema de decisión ye un problema qu'especifica una cadena de calteres de datos d'entrada y rique como solución una respuesta pol SI o pol NON. Si esiste un algoritmu (por casu una máquina de Turing, o un programa en llinguaxes Lisp o Pascal con memoria irrestricta) que ye capaz d'apurrir la respuesta correuta pa toa cadena de datos de llargor n n'a lo sumo ${\displaystyle c\cdot n^{k}}$ pasos, onde k y c son constantes independientes del conxuntu de datos, entós dizse que'l problema puede ser resueltu en tiempu polinómico y clasificar como perteneciente a la clase P. En forma intuitiva, consideramos que los problemes conteníos en P son aquellos que pueden ser resueltos en forma razonablemente rápida.

P suel ser la clase de problemes computacionales que son “eficientemente resolubles” o “tratables”, anque haya clases potencialmente más grandes que tamién se consideren tratables, como RP Y BPP. Anque tamién esisten problemes en P que nun son tratables en términos práuticos; por casu, unos riquen siquier ${\displaystyle n^{1000000}}$ operaciones.

En forma intuitiva, puede pensase que NP ye un problema de decisión que ye malo de resolver si nun se tener nengún otru datu o información adicional. Sicasí, si recibe la información adicional llamada un certificáu, entós el problema puede ser resueltu fácilmente. Por casu, si dásenos el númberu 323 y preguntar si 323 ye un númberu factorizable, ensin danos nengún datu o información adicional, tendríamos d'analizar tolos númberos enteros positivos mayores que 2 pero menores que 323 pa estudiar si dalgunu d'ellos estrema esautamente al 323. Sicasí, si dásenos el númberu 17, podemos estremar 323 por 17 y rápido verificar que 323 ye factorizable. El númberu 17 ye llamáu un certificáu. El procesu de división pa verificar que 323 ye factorizable ye n'esencia una máquina Turing y nesti casu ye denomináu'l verificador pa 323. Téunicamente dizse que'l problema ye bon si puede resolvese en tiempu polinómico y que ye mal si resuélvese en tiempu esponencial. Formalmente, defínese NP como un conxuntu de llinguaxes que satisfaen ciertes condiciones.

Sía L un llinguaxe definíu sobre un alfabetu finito, ${\displaystyle \Sigma }$.

Si esiste una rellación binaria ${\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}$ y un enteru positivu ${\displaystyle k}$ tal que pa tou ${\displaystyle x\in \Sigma ^{*}}$, satisfáense les siguientes condiciones:

1. ${\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}$ tal que ${\displaystyle (x,y)\in R\;}$ y ${\displaystyle \left|y\right|\in \;O(\left|x\right|^{k})}$ (O simboliza cota cimera asintótica).
2. El llinguaxe ${\displaystyle L_{R}}$=${\displaystyle \{x\#y:(x,y)\in R\}}$ en ${\displaystyle \Sigma \cup \{\#\}}$ ye decidible por una máquina de Turing en tiempu polinomial.

Entós, la máquina de Turing que decide ${\displaystyle L_{R}}$ (que la llamaremos ${\displaystyle V}$) ye llamada'l Verificador pa ${\displaystyle L}$ y ${\displaystyle y}$ ye llamáu'l Certificáu de membresía de ${\displaystyle x}$ en ${\displaystyle L}$.

Finalmente, ${\displaystyle L}$ atópase en NP "si y solu si" ${\displaystyle V}$ cuerre en tiempu polinómico.

Exemplu.

Sía

${\displaystyle \mathrm {COMPOSITE} }$ = ${\displaystyle \{x\in \mathbb {N} :x=pq\;{\text{pa enteros}}\;p,q>1\}}$

${\displaystyle R}$ = ${\displaystyle \{(x,y)\in \mathbb {N} \times \mathbb {N} :1<y<x\;;\;y\;{\text{estrema a}}\;x\}}$

Claramente, la entruga de si un dadu x ye factorizable ye equivalente a la entruga sobre si x ye un miembru de COMPOSITE. Ello ye que puede demostrase fácilmente que ${\displaystyle \mathrm {COMPOSITE} \in \mathbf {NP} }$ si verifícase que COMPOSITE satisfai la condición indicada primeramente.

(Nota. Apocayá demostróse que COMPOSITE taba dientro de P^[3])

La clase P

P ye conocíu por contener munchos problemes naturales, incluyendo les versiones de decisión de programa llinial, cálculu del máximu común divisor, y atopar una correspondencia máxima.

Problemes notables en P

Dellos problemes naturales son completos pa P, incluyendo la conectividad (o l'accesibilidá) en grafos non empobinaos.

Una xeneralización de P ye NP, que ye la clase de llinguaxes decidibles en tiempu polinómico sobre una máquina de Turing non determinista. De forma trivial, tenemos que P ye un subconxuntu de NP. Anque nun ta demostráu, la mayor parte de los espertos creen qu'esto ye un subconxuntu estrictu.

Equí, EXPTIME ye la clase de problemes resolubles en tiempu esponencial. De toles clases amosaes enriba, namái se conocen dos contenciones estrictes:

• P puramente ta conteníu en EXPTIME.
• L puramente ta contenida en PSPACE.

Los problemes más difíciles en P son los problemes P-completos

Otra xeneralización de P ye'l Tiempu polinómico Non uniforme (P/Poly). Si un problema ta en P/poly, entós puede solucionase nun tiempu polinomial determináu'l cual, dau una cadena, esti solu depende del llargor de la entrada. A diferencia de NP, nun se comprueben les cadenes defectuoses qu'entren na máquina de Turing, yá que nun ye un verificador.

P/poly ye una clase grande que contién cuasi tolos algoritmos práuticos, incluyendo tol BPP. Si esta contién a NP, la xerarquía polinomial colapsar col segundu nivel. Per otra parte, esta tamién contién dellos algoritmos pocu práuticos, incluyendo dellos problemes non decidibles.

Propiedaes

Los algoritmos de tiempu polinómico son cerraos al respective de la composición. Intuitivamente, esto quier dicir que si unu escribe una función con un determináu tiempu polinómico y consideramos que les llamaes a esa mesma función son constantes y, de tiempu polinómico, entós l'algoritmu completu ye de tiempu polinómico. Esto ye unu de los motivos principales polos que P considérase una máquina independiente; delles traces d'esta máquina, como l'accesu aleatoriu, ye que puede calcular en tiempu polinómico el tiempu polinómico del algoritmu principal amenorgándolo a una máquina más básica.

Les pruebes esistenciales d'algoritmos de tiempu polinómico

Conozse que dellos problemes son resolubles en tiempu polinómico, pero nun se conoz nengún algoritmu concretu pa solucionalos. Por casu, el teorema Robertson-Seymour garantiza qu'hai una llista finita de los menores dexaos que compón (por casu) el conxuntu de los grafos que pueden ser integraos sobre un toroide; amás, Robertson y Seymour demostraron qu'hai una complexidá O (n³) nel algoritmu pa determinar si un grafo tien un grafo incluyíu. Esto danos una prueba non constructiva de qu'hai un algoritmu de tiempu polinómico pa determinar si dau un grafo puede ser integráu sobre un toroide, a pesar de nun conocese nengún algoritmu concretu pa esti problema.

Exemplos

Camín Mínimu: atopar el camín mínimu dende un vértiz orixe al restu de los vértices.

Ciclu Euleriano: Atopar un ciclu que pase per cada arcu d'un grafo una única vegada.

La clase NP

La clase NP ta compuesta polos problemes que tienen un certificáu sucinto (tamién llamáu testigu polinómico) para toles instancies que la so respuesta ye un SÍ. La única forma de que tengan un tiempu polinomial ye realizando una etapa aleatoria, incluyendo l'azar de dalguna manera pa escoyer una posible solución, y entós n'etapes posteriores comprueba si esa solución ye correuta.

N'otres pallabres, dada una solución pa una cierta instancia, ye posible comprobar que ye válida en TIME (n^k). Nel casu de SAT (Problema de satisfacibilidad booleana), dau una asignación de valores de verdá, puede comprobase fácilmente si la fórmula ye cierta o non. Una nMT puede "aldovinar" la solución n'O (n) y verificala en tiempu polinómico.

Completitud de NP

P'analizar la entruga P = NP, resulta bien útil el conceutu de completitud NP. De manera informal, los problemes de completitud NP son los problemes más "difíciles" en NP nel sentíu de qu'ellos son los que son más probable nun s'atopen en P. Problemes NP-difíciles son aquellos pa los cualos cualesquier problema en NP puede ser amenorgáu en tiempu polinómico. Los problemes de completitud NP son aquellos problemes NP-difícil que s'atopen en NP. Por casu, la versión de problema de decisión del problema del vendedor viaxeru ye dafechu NP. Asina nengún casu de nengún problema en NP puede ser tresformáu mecánicamente nuna parte del problema del vendedor viaxeru, en tiempu polinómico. Poro, si'l problema del vendedor viaxeru tuviera conteníu en P, entós P = NP. El problema del vendedor viaxeru ye unu de munchos problemes NP-completos. Si cualquier problema NP-completu atópase conteníu en P, entós verificaríase que P = NP. Desafortunadamente, demostróse que munchos problemes importantes son NP-completos y nun se conoz la esistencia de nengún algoritmu rápidu pa ellos.

La definición anterior de NP dexa considerar de manera natural una clase de problemes complementaries. La co-NP ta compuesta polos problemes que tienen un contraejemplo sucinto pa toles instancies que la so respuesta ye NON.

Exemplos

Camín Máximu: Daos dos vértices d'un grafo atopar el camín (simple) máximu.

Ciclu Hamiltoniano: Ciclu simple que contién cada vértiz del grafo.

NP-Completu

Pa encetar la entruga de si P=NP, el conceutu de la completitud de NP ye bien útil. Informalmente, los problemes de NP-completos son los problemes más difíciles de NP, nel sentíu de que son los más probables de nun atopase en P. Los problemes de NP-completos son esos problemes NP-duros que tán conteníos en NP, onde los problemes NP-duros son estos que cualquier problema en NP puede ser amenorgáu a complexidá polinomial. Por casu, la decisión del Problema del viaxante de comerciu ye NP-completu, asina que cualquier casu de cualquier problema en NP puede ser tresformáu mecánicamente nun casu del Problema del viaxante de comerciu, de complexidá polinomial. El Problema del viaxante de comerciu ye de los munchos problemes NP-completos esistentes. Si cualquier problema NP-completu tuviera en P, entós indicaría que P=NP. Desafortunadamente, sábese que munchos problemes importantes son NP-completos y a fecha de 2008, nun se conoz nengún algoritmu rápidu pa nengún d'ellos. Basándonos solo nesta idea, nun ye obviu qu'esista un problema NP-completu. Un problema NP-completu trivial y escurríu, puede formulase como: Dada una descripción d'una máquina de Turing M que se detién en tiempu polinómico, ¿esiste una entrada de tamañu polinómico que M acepte? Ye NP porque, dada una entrada, ye simple comprobar si M acepta o non la entrada asemeyando M, ye NP-duros porque'l verificador pa cualquier casu particular d'un problema en NP puede ser codificado como una máquina M de tiempu polinomial que toma la solución pa ser verificada como entrada. Entós la entruga de si'l casu ye o non un casu, ta determináu pola esistencia d'una entrada valida. El primer problema natural que se demostró ser NP-completu foi'l Problema booleano de satisfacibilidad. Esta resultancia ye conocíu como'l teorema de Cook-Levin; la so prueba de que la satisfacibilidad ye NP-completu contién los detalles téunicos sobre máquines de Turing y como se rellacionen cola definición de NP. Sicasí, dempués demostróse que'l problema yera NP-completu, la prueba por amenorgamientu, apurrió una manera más simple de demostrar que munchos otros problemes tán nesta clase. Asina, una clase estensa de problemes aparentemente ensin rellación ye reducible a otra, y son nesti sentíu'l mesmu problema.

Ver tamién

• Ciencies de la computación
• Teoría de la computación
• Teoría d'autómates
• Teoría de la computabilidad
• Teoría de la complexidá computacional
• Problemes del mileniu

Referencies

Bibliografía

• A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
• Y. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
• Neil Immerman. Languages Which Prinde Complexity Classes. 15th ACM STOC Symposium, páxs.347-354. 1983.
• Thomas H. Cormen, Charles Y. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). «Chapter 34: NP-Completeness», Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, páx. 966–1021. ISBN 0-262-03293-7.
• Christos Papadimitriou (1993). «Chapter 14: On P vs. NP», Computational Complexity, 1st edition, Addison Wesley, páx. 329–356. ISBN 0-201-53082-1.
• Apuntes de clase de l'asignatura Analís y Diseñu d'Algoritmos de la Escuela Cimera de Infórmatica de Málaga

Enllaces esternos

• The Clay Math Institute Millennium Prize Problems (n'inglés)
• The Clay Math Institute Official Problem Description (pdf) (n'inglés)
• Gerhard J. Woeginger. The P-versus-NP page. A list of links to a number of purported solutions to the problem. Some of these links state that P equals NP, some of them state the opposite. It's probable that all these alleged solutions are incorrect. (n'inglés)
• Computational Complexity of Games and Puzzles
• Scott Aaronson's Complexity Zoo: P, (n'inglés)
• Qeden, a wiki that aims to solve the Millennium Prize Problems (n'inglés)
• Scott Aaronson's Shtetl Optimized blogue: Reasons to believe, a list of justifications for the belief that P ≠ NP (n'inglés)