Problema ¿P=NP?

De Wikipedia, la enciclopedia libre

Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos en este caso fue determinada por Ladner.^[1]

La relación entre las clases de complejidad P y NP es una pregunta que aún no ha podido ser respondida por la teoría de la computabilidad. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), es que entonces también se pueden "obtener" las respuestas rápidamente?

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto,NP, NP-Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.

Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de $1 millón de dolares norteamericanos para quién desarrolle la primera demostración correcta.

Tabla de contenidos

1 Ejemplo
2 Contexto del problema
3 Definiciones Formales
4 NP-Completo
5 Definición Formal para NP-completo
6 Problemas todavía más difíciles
7 ¿Es P realmente práctico?
8 ¿Por qué muchos informáticos piensan que P ≠ NP?
9 Consecuencias de La Demostración
10 Dificultad de la Demostración
11 Algoritmos de tiempo polinómico
12 Algoritmos Tiempo-Polinómico
13 Caracterización Lógica
14 Vease también
15 Bibliografía
16 Links externos

[editar] Ejemplo

Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un ejemplo de un problema que es 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 enteros, es que existe un subconjunto no vacío de ellos donde la suma de sus elementos es igual a 0? por ejemplo, es que existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SI, 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 "SI, 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 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 SI/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FP = FNP).

[editar] Contexto del problema

La relación entre las clases de complejidad P y NP es estudiada por la 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 dado problema. 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 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 computación en paralelo.

En esta teoría, la clase P consiste de todos aquellos problemas de decisión que pueden ser resueltos en una máquina determinista secuencial en un período de tiempo polinomial en proporció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 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 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.^[2]

[editar] Definiciones Formales

Más precisamente, un problema de decisión es un problema que especifica una cadena de caracteres de datos de entrada y require 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 Pascal con memoria irrestricta) que es capaz de entregar la respuesta correcta para toda cadena de datos de longitud n en a lo sumo $c \cdot n^k$ 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 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 n^1000000 operaciones.

En forma intuitiva, se puede pensar que NP es un problema de decisión que es dificil 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 resuleto facilmente. Por ejemplo, si se nos da el número 323 y se nos pregunta si 323 es un número factorizable, sin darnos ningun dato o información adicional, deberíamos analizar todos los números enteros positivos mayores que 2 pero menores que 323 para estudiar si alguno de ellos divide exactamente al 323. 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 facil si se puede resolver en tiempo polinómico y que es dificil 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, $Σ$ .

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

(i) $x\in L \Leftrightarrow\exists y\in\Sigma^{*}$ tal que $(x,y)\in R\;$ y $\left|y\right|\in\;$ O $(\left|x\right|^{k})$

(ii) El lenguaje $L R$ = $\{ x\# y:(x,y)\in R\}$ en $\Sigma\cup\{\#\}$ es decible

Entonces, la máquina de Turing que decide $L R$ (que la llamaremos $V$ ) es llamada el Verificador para $L$ y $y$ es llamado el Certificado de membresía de $x$ en $L$ .

Finalmente, $L$ se encuentra en NP "si y solo si" $V$ corre en tiempo polinómico.

Ejemplo.

Sea $C O M P O S I T E$ = $\{x\in N:x=pq \;\text{para enteros}\; p, q > 1 \}$

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

Claramente, la pregunta de si un dado $x$ es factorizable es equivalente a la pregunta sobre si $x$ es un miembro de $C O M P O S I T E$ . De hecho, se puede demostrar facilmente que $\mathit{COMPOSITE}\in\mathbf{NP}$ si se verifica que $C O M P O S I T E$ satisface la condición indicada previamente.

(Nota. Recientemente se demostró que $C O M P O S I T E$ estaba dentro de P^[3] )

[editar] NP-Completo

Para abordar la pregunta de si P=NP, el concepto de la 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 NP 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: ¿Dado una descripción de una máquina de Turing M que para en tiempo polinomico, existe una entrada de tamaño polinomico que M acepte? Es NP porque , dado 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 maquina 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, esta determinado por la existencia de una entrada valida. 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 tecnicos 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.

[editar] Definición Formal para NP-completo

Aunque hay muchas maneras equivalentes de describir NP-completo, respecto al tema de P contra NP, es mejor definir los problemas NP-completos en términos de problemas de NP. Dado $\ L$ un lenguaje sobre un alfabeto finito $\ \Sigma$ .. $\ L$ es NP-completo si, y solo si, las dos condiciones siguientes están satisfechas:

$L\in\mathbf{NP}$ ; y
Algún $L^{'}\in\mathbf{NP}$ es reducible en tiempo polinomial a $\ L$ (escrito como $L^{'}\leq_{p} L$ ), donde $L^{'}\leq_{p} L$ si, y solo si, las dos condiciones siguientes son satisfechas:

1. Existe $f : \Sigma^{*}\rightarrow\Sigma^{*}$ tal que $\forall w\in\Sigma^{*}(w\in L^{'}\Leftrightarrow f(w)\in L)$ ; y
2. Existe una maquina de Turing de tiempo polinomial que finalice con $\ f(w)$ en su cinta para cualquier entrada $\ w$ ..

[editar] Problemas todavía más difíciles

Aunque es desconocido si P = NP, hay problemas conocidos fuera de P. Un número de problemas sucintos, es decir, los problemas que no funcionan con una entrada normal sino con una descripción computacional de la entrada, se conocen por ser EXPTIME-completos. Porque puede ser demostrado que P $\subsetneq$ EXPTIME, estos problemas están fuera de P, y por lo tanto requiere más que los de tiempo polinómico. De hecho, por el teorema de la jerarquía de tiempos, no se pueden ser resueltos en un tiempo significativamente menor que exponencial.

El problema de decidir la veracidad de una afirmacion en la aritmética de Presburger requiere aún más tiempo. Fischer y Rabin probaron en 1974 que todo algoritmo que decide la veracidad de las afirmaciones de Presburger tiene un tiempo de ejecución de al menos $2^{2^{cn}}$ para alguna constante C. Aquí, n es la longitud de la afirmacion de Presburger. Por lo tanto, se conoce que el problema necesita más tiempo que una ejecución exponencial. Aún más difíciles son los problemas no decidibles, tales como el problema de la parada. No pueden ser resueltos totalmente por ningún algoritmo, en el sentido de que para algun algoritmo particular hay al menos una entrada para la cual ese algoritmo no producirá la respuesta correcta, pero producirá la respuesta incorrecta o se ejecutará sin pararse sin producir una respuesta.

[editar] ¿Es P realmente práctico?

Artículo principal: La tesis de Cobham[1]

Todo lo dicho anteriormente ha asumido que P significa “fácil” y “no en P” significa “difícil”. Mientras que esto es una idea aceptada, común y razonablemente acercatada en la teoría de la complejidad, no es siempre verdad en la práctica. Vea la tesis de Cobham para una discusión profundizada sobre este punto, pero las discusiones principales son:

Ignora el tamaño de los exponentes. En los campos donde los problemas prácticos tienen millones de variables (por ejemplo Investigación operativa o EDA), incluso los algoritmos de O (n³) ) son a menudo poco practicos.
Ignora de los factores constantes, los cuales pueden ser arbitrariamente grandes e importantes en la práctica.
Considera solamente el tiempo en el peor caso. El algoritmo simplex a veces (o incluso habitualmente) resuelve los problemas en un tiempo $n$ , pero en muy raras ocasiones tarda un tiempo de $2 n$ . El tiempo en el peor caso es exponencial, el algoritmo deja de ser de tiempo polinomial, pero aun asi es muy práctico.
Considera solamente soluciones deterministas. Puede haber un problema que pueda ser resuelto rápidamente si una probabilidad de error pequeña es aceptable, pero es mucho más difícil de solucionar de manera exacta.
Los avances en la tecnología podrían hacer algoritmos de tiempo exponencial eficientes para los rangos prácticos de los tamaños del problema.

[editar] ¿Por qué muchos informáticos piensan que P ≠ NP?

La mayoría de los informáticos creen que P≠NP. Una razón clave para esta creencia es que tras décadas de estudio de estos problemas, nadie ha podido encontrar un algoritmo de tiempo polinómico para ningún problema NP-duros. Estos algoritmos fueron precibidos bastante antes de que el concepto de NP-completo fuese siquiera conocido (los 21 problemas NP-completos de Karp, entre los primeros encontrados, eran todos problemas existentes ya conocidos al demostrar ser NP-completos). Además, el resultado P = NP implicaría muchos otros resultados alarmantes que se creen actualmente falsos, tales como NP = co-NP y P = PH. También se discute intuitivamente que la existencia de problemas que son difíciles de solucionar pero para los cuáles las soluciones son fáciles de verificar, se corresponden con el mundo real.

Por otra parte, algunos investigadores creen que confiamos demasiado en que P ≠ NP y que también debiéramos explorar las pruebas de que P = NP. Por ejemplo, en el año 2002 se hicieron estas declaraciones: [2]

El argumento principal a favor de P≠NP es la carencia total de progresos fundamentales en el área de la búsqueda exhaustiva. Esto es, en mi opinión, un argumento muy débil. El espacio de algoritmos es muy grande y estamos solo al principio de su exploración. [. . .] La resolución del último teorema de Fermat también demuestra que preguntas muy simples [sic] pueden ser resueltas solamente por teorías muy profundas.

Estar unido a una especulación no es una buena guía para el plan de la investigación. Uno debería siempre intentar ambas direcciones de cada problema. Los prejuicios han hecho que matemáticos famosos fallasen resolviendo famosos problemas cuya solución era la opuesta a sus expectativas, a pesar de que ellos habían desarrollado todos los métodos requeridos.

[editar] Consecuencias de La Demostración

Una de las razones por las que este problema despierta tanta atención es por las consecuencias de su resolucion.

La demostración de que P=NP traería consigo grandes consecuencias practicas,sobre todo si se consiguiera mejorar o adelantar metodos para resolver problemas de tipo NP. En la mayoría de los campos de la ciencia existen importantes problemas de tipo NP,sobre todo en las matemáticas donde se podrian empezar a tratar problemas que hasta ahora resultaban intratables.Por ejemplo,muchos problemas de investigación operativa son NP-completos,tales como problemas de programación lineal o el conocido problema del viajante de comercios.Ademas soluciones eficientes para estos problemas conllevarían grandes avances en lógica ,o en biología,donde los problemas relacionados con la estructura de las proteinas con NP-completos.

Pero,esto no seria nada comparado con la revolución que supondría para las matemáticas encontrar metodos eficientes para resolver problemas NP-completos.

Según palabras de Stephen Cook (Universidad de Toronto):

Esto reduciría las matemáticas a programar ordenadores y que estos encontraran demostraciones formales para cualquier teorema, siempre y cuando esta tuviera un tamaño tratable por un ordenador, después de esto la demostración formal sería interpretada en tiempo polinomial.

Los matemáticos pasan todas su carrera intentado demostrar teoremas,algunos de los cuales han tardado decadas o siglos en demostrarse formalmente.Por ejemplo el ultimo teorema de Fermat tardo tres siglos en ser demostrado.Un metodo fiable para demostrar teoremas(debería existir alguno de una tamaño y complejidad razonable),podría terminar con este problema.

Dejando a un lado los posibles beneficios en computación,una demostración de que P≠NP tambien tendría grandes avances en muchos campos,incluido la Teoría de la Complejidad y serviría como base para futuras investigaciones.Eso permitiria demostrar de manera formal que muchos problemas comunes que creemos tiene solucion no la tendrían,y por tanto centraríamos nuestros esfuerzos en nuevos problemas .Hoy en dia debido a la extendida creencia entre los expertos de que P≠NP, ya se han comenzado estudiar problemas diferentes.

[editar] Dificultad de la Demostración

El hecho de que haya un premio de un millon de dolares para quien resuelva este problema,y que haya cientos de grupos de investigación centrados en él,nos da una idea de la magnitud y dificultad del mismo,además ha habido algunos resultados formales que prueban que efectivamente se trata de un problema de gran dificultad.

Uno de los resultados mas frecuentemente mencionados,es el relacionado con los oráculos.Los oráculos son unas máquinas abstractas que trabajan como una caja negra, vienen a representar máquinas de Turing con una capacidad de computo mayor que estas,capaces de calcular funciones que nos son capaces de calcular las máquinas de Turing ,y lo hacen en tiempo constante.

Pues bien,la pregunta que nos tenemos que hacer es si no hay limite para el numero de veces que podemos utilizar el oráculo,¿Hay problemas que pueden ser verificados en tiempo polinómico,pero que no pueden ser resueltos en tiempo polinómico?

Dependiendo del problema que el oráculo resuelva, en algunos casos el oráculo cumplirá que P=NP, mientras que para otros P≠NP. La consecuencia de esto es que cualquier demostración que pueda ser modificada para tener en cuenta la existencia de los oráculos, no podrá resolver el problema. Desafortunadamente la mayoría de los métodos conocidos y casi todos los métodos clásicos pueden ser modificados para tener en cuenta los oráculos,a estos métodos se los conoce como métodos relativizados,es decir,que no se ven afectados si se les agregan oráculos.

Además de todo esto, Alenxandre Razborov y Steven Rudich demostraron en 1993 que:

Dada una cierta suposición creíble , y una demostración de que esta suposición es ”natural” en un cierto sentido, no sirve para resolver el problema de P=NP. Esto demostró que era poco probable que los métodos aparentemente mas prometedores de la época tuvieran éxito. Cuantos mas teoremas de este tipo se demuestran, más dificultades tendrá una posible solución a la pregunta de si ¿ P=NP ? .

Esta es otra de las razones por la cual los problemas NP-completos son útiles, si un algoritmo puede resolver un problema NP-completo en tiempo polinómico, esto servirá para poder demostrar por fin que P=NP, de una forma que no sea excluida por los resultados anteriormente mencionados.

[editar] Algoritmos de tiempo polinómico

Nadie sabe si existen algoritmos de tiempo polinómico para lenguajes NP completos. En el caso de que existieran, algunos de ellos serian ya conocidos, por ejemplo, el siguiente algoritmo (creado por Levin-Cook) acepta correctamente un lenguaje NP-completo, pero a día de hoy, no sabemos cuanto tiempo tarda en ejecutarse.

  // Algoritmo que acepta el lenguaje NP-completo 
  // para el problema de la suma de subconjntos.
  //
  // Este es un algoritmo de tiempo polinómico si y solo si P=NP
  // ”Tiempo polinómico” significa que devuelve “si” en tiempo polinómico      
  // cuando la respuesta sea “si” y no para nunca cuando la respuesta es       “no”.
  // Entradas: S= conjunto finito de enteros
  // Salidas: “si” cuando un subconjunto de S suma 0.
  //     Nunca para en otro caso
  //
  // Nota: “Numero de programa P” es el programa obtenido convirtiendo P   en binario, y considerando la cadena de bits un programa. Cada programa puede ser generado de esta forma, evitando errores sintácticos.
  //
   PARA N = 1… infinito
       PARA P = 1… N
          Ejecuta el número de programa  P N pasos con la entrada S
           SI el programa muestra una lista de números enteros distintos
               Y los números enteros pertenecen todos a  S
               Y su suma es  0
           ENTONCES
               DEVUELVE “sí” y FIINALIZA

Si, y solo si, P=NP, este algoritmo acepta un lenguaje NP-completo en un tiempo polinómico. “Acepta” se refiere a que devuelve “si” en tiempo polinómico y en caso de que la respuesta sea “no”, nunca parará. Quizás queramos resolver el problema de la suma de subconjuntos antes que aceptarlo. Eso significa que buscamos un algoritmo que siempre pare y devuelva “si” o “no”, pero hoy en día no sabemos si existe un algoritmo que haga esto en tiempo polinomial. Pero si lo hay es un algoritmo que probablemente lo haga en tiempo polinomial,entonces el algoritmo resultante será igual que el anterior pero cambiaría la sentencia SI por:

           SI el programa devuelve  una demostración matemática completa 
               Y cada paso de la demostración es legal
               Y la conclusión es que S  tiene (o no tiene)  un subconjunto que  suma  0
           ENTONCES
               DEVULVE  “sí” (o “no”) y FINALIZA

[editar] Algoritmos Tiempo-Polinómico

Nadie sabe si existen algoritmos de tiempo polinómico para lenguajes NP-completos. En el caso de que existieran, algunos de ellos serian ya conocidos, por ejemplo, el siguiente algoritmo (creado por Levin-Cook) acepta correctamente un lenguaje NP-completo, pero a día de hoy, no sabemos cuanto tiempo tarda en ejecutarse.

//Algoritmo que acepta el lenguaje NP-completo para el problema de la suma de subconjuntos.
//
//Este es un algoritmo de tiempo polinómico si y solo si P=NP
//
//”Tiempo polinómico” significa que devuelve “si” en tiempo polinómico cuando la respuesta sea “si” y //no para nunca cuando la respuesta es “no”.
//Entradas: S= conjunto finito de enteros
//Salidas: “si” cuando un subconjunto de S suma 0.
//        Nunca para en otro caso
// Nota: “Numero de programa P” es el programa obtenido convirtiendo P en binario, y considerando la cadena de bits un programa. Cada programa puede ser generado de esta forma, evitando errores sintácticos.
   PARA N = 1… infinito
       PARA P = 1… N
          Ejecuta el número de programa  P N pasos con la entrada S
           SI el programa muestra una lista de números enteros distintos
               Y los números enteros pertenecen todos a  S
               Y su suma es  0
           ENTONCES
               DEVUELVE “sí” y FIINALIZA

Si, y solo si, P=NP, este algoritmo acepta un lenguaje NP-completo en un tiempo polinómico. “Acepta” se refiere a que devuelve “si” en tiempo polinómico y en caso de que la respuesta sea “no”, nunca parará. Quizás queramos resolver el problema de la suma de subconjuntos antes que aceptarlo. Eso significa que buscamos un algoritmo que siempre paré y devuelva “si” o “no”, pero hoy en día no sabemos si existe u n algoritmo que haga esto en tiempo polinomial. Pero si lo hay es un algoritmo que probablemente lo haga en tiempo polinomial, entonces el algoritmo resultante será igual que el anterior pero cambiaria la sentencia SI por:

           SI el programa devuelve  una demostración matemática completa 
               Y cada paso de la demostración es legal
               Y la conclusión es que S  tiene (o no tiene)  un subconjunto que  suma  0
           ENTONCES
               DEVULVE  “sí” (o “no”) y FINALIZA

[editar] Caracterización Lógica

El problema P=NP puede ser reformulado en términos de potencia expresiva de algunas declaraciones logicas. Todos los lenguajes en P pueden ser expresados en lógica de primer orden con el añadido del mínimo operador de punto fijo y una relación de orden(esto permite definir funciones recursivas).Igualmente, NP es el conjunto de lenguajes expresables en lógica de segundo orden existencial(Lógica de segundo orden restringida únicamente a cuantificadores existenciales). Los lenguajes en la jerarquía polinómica, corresponden todos a la lógica de segundo orden. De esta manera la pregunta ¿Es P un subconjunto propio de NP? puede ser reformulada como ¿Es capaz la lógica de segundo orden de representar/describir lenguajes, que la lógica de primer orden con operador mínimo de punto fijo no puede representar/describir?

[editar] Vease también

[editar] 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 Theory Research Worksh., 2000.
Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347–354. 1983.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). “Chapter 34: NP-Completeness”, Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, pp.966–1021. ISBN 0-262-03293-7.
Christos Papadimitriou (1993). “Chapter 14: On P vs. NP”, Computational Complexity, 1st edition, Addison Wesley, pp.329–356. ISBN 0-201-53082-1.

[editar] Links externos

The Clay Mathematics Institute Millennium Prize Problems (en inglés)
Ian Stewart on Minesweeper as NP-complete at The Clay Math Institute] (en 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 is probable that all these alleged solutions are incorrect.] (en inglés)
Computational Complexity of Games and Puzzles] (en inglés)
Scott Aaronson's Complexity Zoo: P, NP] (en inglés)
Qeden, a wiki that aims to solve the Millennium Prize Problems] (en inglés)
Scott Aaronson's Shtetl Optimized blog: Reasons to believe, a list of justifications for the belief that P ≠ NP] ( en inglés)

Categoría: Complejidad computacional

See also ebooksgratis.com: no banners, no cookies, totally FREE.