Ver el código de «Clases de complejidad P y NP»

{{wikificar|t=20140111185624}}
[[Archivo:Complexity classes es.svg|thumb|260px|Diagrama de clases de complejidad para el caso en que '''P''' ≠ '''NP'''. La existencia de problemas fuera tanto de '''P''' como de '''NP-completos''', fue determinada por Pichard T. Ledner.<ref>P. T. Ledner "On the structure of polynomial time reducibility," Journal ACM, 22, pp. 151–171, 1975, Corollary 1.1, [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 sitio web de ACM].</ref>]]

La relación entre las '''[[clase de complejidad|clases de complejidad]] [[NP (clase de complejidad)|NP]] y [[P (Complejidad computacional)|P]]''' es una pregunta por primera vez formulada por el científico computacional [[Stephen Cook]] que la [[teoría de la complejidad computacional]] aún no ha podido responder. En esencia, la pregunta <<¿es '''P''' = '''NP completo'''?>> significa: <<Si es posible "verificar" rápidamente las soluciones de un problema (es decir, es un problema de tipo NP), ¿eso implica que también es posible "obtener" las respuestas con la misma rapidez? (es decir, es un problema de tipo P)>>, donde "rápidamente" significa "en [[tiempo polinómico]]".

Los recursos comúnmente estudiados en [[complejidad computacional]] son:

– El '''tiempo''': mediante una aproximación al número de pasos de ejecución que un [[algoritmo]] emplea para resolver un problema.

– El '''espacio''': mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...). Este artículo se centrará en las clases P y NP.

Se considera el problema más importante en este campo, el [[Clay Mathematics Institute]] ha ofrecido un premio de un millón de [[Dólar estadounidense|dólares estadounidenses]] para quien desarrolle la primera demostración correcta.

== Ejemplo ==

Consideremos, por ejemplo, el [[problema de la suma de subconjuntos]], que es un ejemplo de un problema fácil de verificar, pero cuya respuesta se «cree» (pero no ha sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números [[entero]]s, ¿existe un [[subconjunto]] no vacío de ellos donde la suma de sus elementos es igual a 0? por ejemplo, ¿Existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SÍ, si bien puede llevar algún tiempo encontrar un subconjunto que satisface el requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10, 15} es igual a cero», entonces lo podemos comprobar en forma muy rápida y mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un proceso mucho más rápido que encontrar el subconjunto. La información necesaria para verificar un resultado positivo/afirmativo es llamada un «certificado». Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo polinomial) y es esta la razón por la que el problema se encuentra en '''NP'''. 
Una respuesta a la pregunta '''P''' = '''NP''' sería determinar si en problemas del tipo [[Problema de la suma de subconjuntos|SUMA-SUBCONJUNTO]] es tan fácil hallar la solución como verificarla. Si se encuentra que '''P''' no es igual a '''NP''', ello significa que algunos problemas '''NP''' serían significativamente más difíciles de hallar su solución que verificar la misma. La respuesta sería aplicable a todo este tipo de problemas, no solo al ejemplo específico de SUMA-SUBCONJUNTO.

La restricción a problemas de tipo SÍ/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si '''[[FNP (clase de complejidad)|FNP]]''' = '''[[FP (clase de complejidad)|FP]]''').

== Contexto del problema ==

La relación entre las '''[[clase de complejidad|clases de complejidad]] P y NP''' es estudiada por la [[Complejidad computacional|teoría de la complejidad computacional]], la parte de la [[teoría de la computación]] que trata de los recursos requeridos durante el cálculo para resolver un problema dado. Los recursos más usuales son tiempo (¿cuántos pasos son necesarios para resolver un problema?) y espacio (¿cuánta memoria es necesaria para resolver un problema?). 

En este tipo de análisis, se requiere un modelo de la computadora para la que desea estudiar el requerimiento en términos de tiempo. Típicamente, dichos modelos suponen que la computadora es [[Algoritmo determinista|determinista]] (dado el estado actual de la computadora y las variables de entrada, existe una única acción posible que la computadora puede tomar) y ''secuencial'' (realiza las acciones una después de la otra). Estas suposiciones son adecuadas para representar el comportamiento de todas las computadoras existentes, aún incluye a las máquinas con [[programación paralela|computación en paralelo]]. 

En esta teoría, la clase '''[[Tiempo polinómico|P]]''' consiste de todos aquellos [[problema de decisión|problemas de decisión]] que pueden ser resueltos en una máquina determinista secuencial en un período de [[tiempo polinómico|tiempo polinomial]] en función a los datos de entrada. En la teoría de complejidad computacional, la clase P es una de las más importantes; la clase '''[[NP_(clase de complejidad)|NP]]''' consiste de todos aquellos problemas de decisión cuyas soluciones positivas/afirmativas pueden ser verificadas en [[tiempo polinómico]] a partir de ser alimentadas con la información apropiada, o en forma equivalente, cuya solución puede ser hallada en tiempo polinómico en una máquina [[Máquina de Turing no determinista|no determinista]]. Por lo tanto, la principal pregunta aún sin respuesta en la [[teoría de la computación]] está referida a la relación entre estas dos clases:
 
:¿Es '''P''' igual a '''NP'''?

En una encuesta realizada en el 2002 entre 100 investigadores, 61 creían que la respuesta era NO, 9 creían que la respuesta era SI, 22 no estaban seguros, y 8 creían que la pregunta podía ser independiente de los [[axiomas]] actualmente aceptados, y por lo tanto imposible de demostrar por el SI o por el NO.<ref name=poll>{{cita publicación|autor=William I. Gasarch |título=The P=?NP poll. |revista=SIGACT News |volumen=33 |número=2 |páginas=34-47 |fecha=junio de 2002 |url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804}}</ref>

== Definiciones formales ==

Más precisamente, un ''problema de decisión'' es un problema que especifica una [[cadena de caracteres]] de datos de entrada y requiere como solución una respuesta por el SI o por el NO. Si existe un [[algoritmo]] (por ejemplo una [[máquina de Turing]], o un programa en lenguajes [[Lisp]] o [[Lenguaje de programación Pascal|Pascal]] con memoria irrestricta) que es capaz de entregar la respuesta correcta para toda cadena de datos de longitud ''n'' en a lo sumo <math>c \cdot n^k</math> pasos, donde ''k'' y ''c'' son constantes independientes del conjunto de datos, entonces se dice que el problema puede ser resuelto en ''tiempo polinómico'' y lo clasificamos como perteneciente a la clase '''P'''. En forma intuitiva, consideramos que los problemas contenidos en '''P''' son aquellos que pueden ser resueltos en forma razonablemente rápida.

'''P''' suele ser la clase de [[Problema computacional|problemas computacionales]] que son “eficientemente resolubles” o “tratables”, aunque haya clases potencialmente más grandes que también se consideran tratables, como RP Y BPP. Aunque también existen problemas en P que no son tratables en términos prácticos; por ejemplo, unos requieren al menos <math>n^{1000000}</math> operaciones.

En forma intuitiva, se puede pensar que '''NP''' es un problema de decisión que es difícil de resolver si no se posee ningún otro dato o información adicional. Sin embargo, si se recibe la información adicional llamada un certificado, entonces el problema puede ser resuelto fácilmente.  Por ejemplo, si se nos da el número 323 y se nos pregunta si 323 es un número factorizable, sin darnos ningún dato o información adicional, deberíamos hacer la [[raíz cuadrada]] de 323 (+/-17.9722) redondear al entero menor en [[valor absoluto]] (17) e intentar dividir desde 17 a 2. Sin embargo, si se nos da el número 17, podemos dividir 323 por 17 y rápidamente verificar que 323 es factorizable.  El número 17 es llamado un certificado.  El proceso de división para verificar que 323 es factorizable es en esencia una máquina Turing  y en este caso es denominado el verificador para 323.  Técnicamente se dice que el problema es fácil si se puede resolver en tiempo polinómico y que es difícil si se resuelve en tiempo exponencial. 
Formalmente, se define  '''NP''' como un conjunto de lenguajes que satisfacen ciertas condiciones.

Sea ''L'' un lenguaje definido sobre un alfabeto finito, <math>\Sigma</math>.

Si existe una relación binaria  <math>R\subset\Sigma^{*}\times\Sigma^{*}</math> y un entero positivo <math>k</math> tal que para todo <math>x\in\Sigma^{*}</math>, se satisfacen las siguientes condiciones:

# <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> tal que <math>(x,y)\in R\;</math> y <math>\left|y\right|\in\;O(\left|x\right|^{k})</math> (O simboliza [[cota superior asintótica]]).
# El lenguaje <math>L_{R}</math>=<math>\{ x\# y:(x,y)\in R\}</math> en  <math>\Sigma\cup\{\#\}</math> es decidible por una máquina de Turing en tiempo polinomial.

Entonces, la máquina de Turing que decide <math>L_{R}</math> (que la llamaremos <math>V</math>) es llamada el Verificador para  <math>L</math> y <math>y</math> es llamado el Certificado de membresía de  <math>x </math> en <math>L</math>.

Finalmente, <math>L</math> se encuentra en  '''NP''' "si y solo si" <math>V</math> corre en tiempo polinómico.

'''Ejemplo'''.  

Sea 

:<math>\mathrm{COMPOSITE}</math> = <math>\{x\in \N : x=pq \;\text{para enteros}\; p, q > 1 \}</math>
:<math>R</math> = <math>\{(x,y)\in \N\times \N: 1<y<x\; ; \;y\; \text{divide a}\; x\}</math>

Claramente, la pregunta de si un dado ''x'' es factorizable es equivalente a la pregunta sobre si ''x'' es un miembro de COMPOSITE.  De hecho, se puede demostrar fácilmente que <math>\mathrm{COMPOSITE}\in\mathbf{NP}</math> si se verifica que COMPOSITE satisface la condición indicada previamente.

('''Nota'''.   Recientemente se demostró que COMPOSITE estaba dentro de  '''P'''<ref name=Agrawal>{{Cita web |autor= M. Agrawal, N. Kayal, N. Saxena |título=Primes is in P |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf}}</ref>)

== La clase P ==

P es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión de programa lineal, cálculo del [[máximo común divisor]], y encontrar una correspondencia máxima. 

'''Problemas notables en P''' 

Algunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en [[Grafo no dirigido|grafos no dirigidos]]. 

Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo polinómico sobre una [[máquina de Turing]] no determinista. De forma trivial, tenemos que P es un subconjunto de NP. Aunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.

Aquí, [[EXPTIME]] es la clase de problemas resolubles en tiempo exponencial. De todas las clases mostradas arriba, sólo se conocen dos contenciones estrictas:

* P estrictamente está contenido en EXPTIME.
* L estrictamente está contenida en [[PSPACE]].
         

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

Otra generalización de NP es el Tiempo polinómico No uniforme (NP/Poly)[//en.wikipedia.org/wiki/P/poly]. Si un problema está en NP/poly, entonces puede solucionarse en un tiempo polinomial determinado el cual, dado una cadena, este solo depende de la longitud de la entrada. A diferencia de P, no se comprueban las cadenas defectuosas que entran en la máquina de Turing, puesto que no es un verificador. 

NP/poly es una clase grande que contiene casi todos los algoritmos prácticos, incluyendo todo el BPP. Si esta contiene a P, la jerarquía polinomial se colapsa con el segundo nivel. Por otra parte, esta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.

'''Propiedades'''

Los algoritmos de tiempo polinómico son cerrados respecto a la composición. Intuitivamente, esto quiere decir que si uno escribe una función con un determinado tiempo polinómico y consideramos que las llamadas a esa misma función son constantes y, de tiempo polinómico, entonces el algoritmo completo es de tiempo polinómico. Esto es uno de los motivos principales por los que P se considera una máquina independiente; algunos rasgos de esta máquina, como el acceso aleatorio, es que puede calcular en tiempo polinómico el tiempo polinómico del algoritmo principal reduciéndolo a una máquina más básica. 

'''Las pruebas existenciales de algoritmos de tiempo polinómico'''

Se conoce que algunos problemas son resolubles en tiempo polinómico, pero no se conoce ningún algoritmo concreto para solucionarlos. Por ejemplo, el teorema Robertson-Seymour garantiza que hay una lista finita de los menores permitidos que compone (por ejemplo) el conjunto de los grafos que pueden ser integrados sobre un [[toroide]]; además, Robertson y Seymour demostraron que hay una complejidad O (n<sup>3</sup>) en el algoritmo para determinar si un grafo tiene un grafo incluido. Esto nos da una prueba no constructiva de que hay un algoritmo de tiempo polinómico para determinar si dado un grafo puede ser integrado sobre un toroide, a pesar de no conocerse ningún algoritmo concreto para este problema.

'''Ejemplos'''

'''[[Algoritmo de Dijkstra|Camino Mínimo]]:''' encontrar el camino mínimo desde un vértice origen al resto de los vértices.

'''[[Ciclo Euleriano]]:''' Encontrar un ciclo que pase por cada arco de un grafo una única vez.

== La clase NP ==

La clase NP está compuesta por los problemas que tienen un certificado sucinto (también llamado testigo polinómico) para todas las instancias cuya respuesta es un SÍ. La única forma de que tengan un tiempo polinomial es realizando una etapa aleatoria, incluyendo el azar de alguna manera para elegir una posible solución, y entonces en etapas posteriores comprueba si esa solución es correcta.

En otras palabras, dada una solución para una cierta instancia, es posible comprobar que es válida en TIME (n^k). 
En el caso de SAT ([[Problema de satisfacibilidad booleana]]), dado una asignación de [[Valor de verdad|valores de verdad]], se puede comprobar fácilmente si la fórmula es cierta o no. Una nMT puede "adivinar" la solución en O (n) y verificarla en tiempo polinómico.

'''Completitud de NP'''

Para analizar la pregunta  '''P''' = '''NP''', resulta muy útil el concepto de  [[P-completo|completitud '''NP''']]. De manera informal, los problemas de completitud '''NP''' son los problemas más "difíciles" en '''P''' en el sentido de que ellos son los que son más probable no se encuentren en '''P'''.  Problemas [[NP-hard|'''P'''-difíciles]] son aquellos para los cuales ''cualquier'' problema en '''P''' puede ser reducido en tiempo polinómico.  Los problemas de completitud '''P''' son aquellos problemas '''P'''-difícil que se encuentran en '''P'''.  Por ejemplo, la versión de problema de decisión del [[problema del vendedor viajero]] es completamente  '''P'''.  Así ningún caso de ningún problema en '''P''' puede ser transformado mecánicamente en una parte del problema del vendedor viajero, en tiempo polinómico.  Por lo tanto, si el problema del vendedor viajero estuviera contenido en  '''NP''', entonces '''P ''' = '''NP'''.  El problema del vendedor viajero es uno de muchos problemas '''P'''-completos. Si cualquier problema '''P'''-completo se encuentra contenido en  '''NP''', entonces se verificaría que '''P''' = '''NP'''. Desafortunadamente, se ha demostrado que muchos problemas importantes son '''P'''-completos y no se conoce la existencia de ningún algoritmo rápido para ellos.
<!--
Es relativamente obvio que la clase P-completo no es vacía porque es posible formular un problema de decisión llamado DUH que es trivial P y difícil-P: dada la descripción de una máquina de Turing M garantizada que se detendrá en tiempo polinómico, DUH corresponde a la pregunta de si existe un conjunto de datos de dimensión polinómica que M aceptará.<ref name=scott>{{Cita web |autor=Scott Aaronson |title=PHYS771 Lecture 6: P, NP, and Friends |url=http://www.scottaaronson.com/democritus/lec6.html |fechaacceso=27 de agosto de 2007}}</ref> Sin embargo, dado que DUH is contrived y de interés eminentemente teórico, fue realmente un gran descubrimiento encontrar que numerosos problemas existentes muy prácticos eran también NP-completos.

El primer problema natural que se demostró que es NP-completo fue el [[Boolean satisfiability problem]]. Este resultado fue demostrado por [[Stephen Cook]] en 1971, y se lo llamó el [[teorema de Cook]]. Cook's proof that satisfiability is NP-complete is very complicated. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] has provided a simpler way to show that many other problems are in this class. Por lo tanto, una amplia clase de problemas en principio inconexos son reducibles unos a otros, y por lo tanto resultan en "el mismo problema" -- un resultado profundo e inesperado.
-->

La definición anterior de P permite considerar de manera natural una clase de problemas complementarias. La [[co-P]] está compuesta por los problemas que tienen un [[contraejemplo]] sucinto para todas las instancias cuya respuesta es NO. 

'''Ejemplos'''

'''Camino Máximo:''' Dados dos vértices de un grafo encontrar el camino (simple) máximo.

'''[[Ciclo Hamiltoniano]]:''' Ciclo simple que contiene cada vértice del grafo.

== NP-Completo ==

Para abordar la pregunta de si P=NP, el concepto de la [[NP-completo|completitud de NP]] es muy útil. Informalmente, los problemas de NP-completos son los problemas  más difíciles de NP, en el sentido de que son los más probables de no encontrarse en P. Los problemas de NP-completos son esos problemas NP-duros que están contenidos en NP, donde los problemas NP-duros son estos que cualquier problema en P puede ser reducido a complejidad polinomial. Por ejemplo, la decisión del [[Problema del viajante]] de comercio es NP-completo, así que cualquier caso de cualquier problema en NP puede ser transformado mecánicamente en un caso del [[Problema del viajante]] de comercio, de complejidad polinomial. El [[Problema del viajante]] de comercio es  de los muchos problemas NP-completos existentes. Si cualquier problema NP-completo estuviera en P, entonces indicaría que P=NP. Desafortunadamente, se sabe que muchos problemas importantes son NP-completos y a fecha de 2008, no se conoce ningún algoritmo rápido para ninguno de ellos. Basándonos solo en esta idea, no es obvio que exista un problema NP-completo. Un problema NP-completo trivial e ideado, se puede formular como: Dada una descripción de una [[máquina de Turing]] M que se detiene en tiempo polinómico, ¿existe una entrada de tamaño polinómico que M acepte? Es NP porque, dada una entrada, es simple comprobar si M acepta o no la entrada simulando M, es NP-duros porque el verificador para cualquier caso particular de un problema en NP puede ser codificado como una máquina M de tiempo polinomial que toma la solución para ser verificada como entrada. Entonces la pregunta de si el caso es o no un caso, está determinado por la existencia de una entrada válida. El primer problema natural que se demostró ser NP-completo fue el Problema booleano de satisfacibilidad. Este resultado es conocido como el [[teorema de Cook]]-Levin; su prueba de que la satisfacibilidad es NP-completo contiene los detalles técnicos sobre máquinas de Turing y como se relacionan con la definición de NP. Sin embargo, después se demostró que el problema era NP-completo, la prueba por reducción, proporcionó una manera más simple de demostrar que muchos otros problemas están en esta clase. Así, una clase extensa de problemas aparentemente sin relación es reducible a otra, y son en este sentido el mismo problema.

== Soluciones reclamadas. ==
Se han publicado muchos artículos intentando resolver  el problema P vs NP. <ref>{{Cita web|url=https://www.researchgate.net/publication/377978681_Is_P_equal_to_NP_Response_absolute|título=Is P equal to NP? Response absolute|autor=Nilson Rafael Bolívar Barrios|sitioweb=ResearchGate}}</ref>

== Véase también ==
* [[Ciencias de la computación]]
* [[Teoría de la computación]]
* [[Teoría de autómatas]]
* [[Teoría de la computabilidad]]
* [[Complejidad computacional|Teoría de la complejidad computacional]]
* [[Problemas del milenio]]

== Referencias ==
{{listaref}}

== 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.
* E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theor
y Resear

== Enlaces externos ==
* [https://web.archive.org/web/20051126011639/http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems] (en inglés)
* [https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf The Clay Math Institute Official Problem Description (pdf)] (en inglés)
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-P 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. (en inglés)
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* Scott Aaronson's Complexity Zoo: [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#p P],  (en inglés)
* [https://web.archive.org/web/20071212164513/http://www.qeden.com/ Qeden], a [[wiki]] that aims to solve the Millennium Prize Problems (en inglés)
* [http://scottaaronson.com/blog/?p=122 Scott Aaronson's Shtetl Optimized blog: Reasons to believe], a list of justifications for the belief that P ≠ NP (en inglés)

{{Control de autoridades}}
[[Categoría:Clases de complejidad]]
[[Categoría:Problemas matemáticos no resueltos]]
[[Categoría:Problemas no resueltos de las ciencias de la computación]]
[[Categoría:Problemas del milenio]]
[[Categoría:Introducciones relacionadas a la ciencia de la computación de 1956]]
[[Categoría:Informática de 1956]]