Mi opinión sobre la demostración P≠NP de Norbert Blum

Por Francisco R. Villatoro, el 15 agosto, 2017. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Noticias • Science ✎ 36

Dibujo20170815 P NP NPc NPhard wikipedia commons

[PS 13 Nov 2017] Norbert Blum ha publicado su propio análisis del error que cometió en la demostración del teorema 6 de su artículo; afirma que trabaja en su solución, pero no parece posible arreglar su demostración. Los interesados en los detalles disfrutarán con Norbert Blum, «The mistake in “A Solution of the P versus NP
Problem”,» 11 Oct 2017 [PDF]. [/PS]

[PS 31 Ago 2017] Norbert Blum se ha retractado de su demostración (arXiv 30 Aug 2017). «The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time.» Cuando el propio Blum sepa dónde está su error ha prometido comunicarlo en su página web. [/PS]

[PS 19 Ago 2017] Ya se conoce el error exacto. He modificado esta entrada para que sea más útil. [/PS] Norbert Blum (Univ. Bonn, Alemania) publicó esta semana una posible demostración de P≠NP. Su idea es extender un teorema de Razborov (1985) para circuitos booleanos monótonos (que solo usan operadores AND y OR) a circuitos no monótonos (que además usan el operador NOT). Hay varios resultados que indican que no es posible hacerlo (llamados barreras de complejidad). Blum evita dicho problema con un truco trivial (algo que sugirió que era posible en 2009). Gracias a dicho truco (teorema 5 de su artículo) extiende dos teoremas de Berg–Ulfberg (1999) y Amano–Maruoka (2004), basados en la aproximación CNF-DNF, de circuitos monótonos a no monótonos, obteniendo su teorema 6. A partir de ahí llega a sus teoremas 7 y 8, cuyo enunciado es poco creíble y cuyo corolario es P≠NP.

Blum es un reconocido experto en complejidad computacional. Su técnica de demostración se basa en la llamada aproximación CNF-DNF (donde CNF es forma conjuntiva normal y DNF es forma disyuntiva normal); en ella se sustituyen ciertos operados AND y OR por operadores «AND aproximados» y «OR aproximados». Blum sustituye la distancia estándar entre los operados aproximados y los originales por una nueva «pseudo-distancia» que le permita extender los resultados del caso monótono al no monótono. [PS 19 Ago 2017] Yo dediqué dos horas a leer el artículo de Blum y a tratar de entender su línea demostración para poder ofrecer una opinión sobre el mismo que me solicitaron por Twitter. No soy experto en estas lides, pero mi intuición parece que no falló demasiado. [/PS] Se me escapa dónde su argumento falla, si es que falla, pero a mí no me convence que su «pseudo-distancia» permita repetir los argumentos basados en la distancia de Razborov (Blum llama a su «pseudo-distancia» distancia débil y a la de Razborov distancia fuerte).

[PS 19 Ago 2017] Razborov afirmó el jueves que la función monótona de Éva Tardos, que está en P, es un contraejemplo del teorema 6 de Blum. El usuario de TCS SE llamado idovol ha publicado el lugar donde se encuentra el error. Un punto bastante sutil en el paso 1, página 31 (que luego se usa en la página 33); allí se encuentra una afirmación que debería ser aplicable a toda función monótona, pero que para la función de Tardos es falsa. Para entender en detalle el asunto hay que conocer la demostración original de Berg y Ulfberg, y cómo Blum la modifica. El problema es el control del error cometido al usar los operadores lógicos aproximados; se requiere un control preciso de su acumulación mediante la distancia que se esté usando. Blum se apoya en su teorema 5 (que parece correcto) para afirmar que los errores según su distancia se acumulan al mismo ritmo que los errores de la demostración de Beg y Ulfberg según la de ellos (la distancia de Razborov). Pero resulta que esto no es verdad. El ritmo de acumulación de sus errores es mayor (como se observa al usar la función de Tardos en su cota); su cota para dicho ritmo es errónea. Por tanto, el resto de su argumento se cae. No parece fácil arreglar la demostración (así lo sugieren las barreras de complejidad). Si quieres más detalles técnicos, consulta el comentario de idovol en TCS SE. [/PS]

Hay dos cuestiones importantes que creo necesario destacar. Primero, todo el mundo espera que una demostración de P≠NP ayude a entender la diferencia entre P y NP; la demostración de Blum no aporta nada relevante al respecto. Y segundo, el argumento de Blum es casi «trivial», una idea que él mismo afirma que se le ocurrió en 2009 y se basa en repetir una línea argumental de 1985 explorada por muchos otros en multitud de ocasiones; no entiendo cómo se le ha escapado esta idea todos los expertos en complejidad computacional en los últimos 30 años. Ambos argumentos me hacen sospechar que hay un error en el argumento de Blum, pero no soy capaz de encontrarlo.

El artículo es Norbert Blum, «A Solution of the P versus NP Problem,» arXiv:1708.03486 [cs.CC]. Estaré al tanto de lo que opinen los expertos sobre este asunto, pero me temo que no estamos ante una demostración correcta de P≠NP (algo que, por otro lado, todo el mundo piensa que es cierto).

[PS 19 Ago 2017] Hay muchos posts en la blogosfera sobre el análisis de la demostración de Blum. Recomiendo la lectura de Dick Lipton, «A topical look at Norbert Blum’s paper and wider thoughts,» Gödel’s Lost Letter and P=NP, 17 Aug 2017 (aquí es donde apareció por primera vez el comentario de idovol);  Luca Trevinsan, «On Norbert Blum’s claimed proof that P does not equal NP,» In Theory, 15 Aug 2017, que a su vez recomienda la de Tim Gowers, «Razborov’s method of approximations,» PDF (2009); y por supuesto la discusión de la demostración recomiendo «Where is Norbert Blum’s 2017 proof that P≠NP being discussed?» en Theoretical Computer Science Stack Exchange.

Hay muchos otros posts que se hicieron eco de esta demostración, que casi podríamos calificar de viral en la blogosfera científica, pero que cuyos autores no son expertos en el área. Mantengo los que ya cité, John Carlos Baez, «Norbert Blum on P versus NP,» Azimuth, 15 Aug 2017; Luboš Motl, «A future proof of P=NP or P≠NP may be far-reaching or not so much,» TRF, 15 Aug 2017. [/PS]

[PS 18 Ago 2017] Carlos destaca abajo en los comentarios que el usuario Mikhail en CSTheory Stack Exchange le ha preguntado al mismísimo Alexander Razborov sobre la prueba de Blum. Razborov dice que ha detectado un problema. El teorema 6 de Blum tiene que ser falso, porque hay un contraejemplo a su enunciado, la función introducida por Éva Tardos (1986) para demostrar que un salto de complejidad computacional exponencial entre el caso monótono y el no monótono. No hay más detalles.

Te recuerdo que Razborov (1985) encontró una función booleana monótona (que resuelve el problema clique) cuya complejidad computacional era superpolinómica, y Alon y Boppana (1985), y Tardos (1986), demostraron que era exponencial; luego no era polinomial y demostraba P≠NP en el caso monótono. Si se extendía el resultado al caso no monótono, entonces el problema clique no estaría en P y se tendría una demostración general de P≠NP. Sin embargo, Tardos (1986) también encontró una función para la que el salto de complejidad computacional entre el caso monótono y el caso no monótono es exponencial; por tanto, P≠NP monótono y P=NP no monótono son compatibles, con lo que los resultados en el caso monótono no dicen nada de nada sobre el caso general no monótono. El teorema 6 de Blum afirma que no existe la barrera de complejidad de Tardos si se usa una modificación adecuada de los argumentos de Berg y Ulfberg (1999) basados en operadores aproximados. En su comentario a Mikhail, Razborov le contradice, afirmando que el famoso contraejemplo de Tardos sigue siendo válido y que Blum tiene que haber cometido un error en la demostración de tu teorema 6. Todavía no sabemos cuál.

Dibujo20170818 circuito logico

[PS 18 Ago 2017] No soy experto en complejidad computacional (estudié bastante hace 25 años y sobrevivo de las rentas). Permíteme una introducción breve a todo este asunto de la complejidad de circuitos lógicos que evalúan funciones booleanas. Espero no meter mucho la pata.

Una función lógica f(x,y,…) con n variables evalúa una expresión matemática con n números binarios; las variables x,y,… son {0, 1}. Esta función se puede implementar mediante un circuito lógico (o combinacional) usando puertas lógicas (operadores lógicos). Hay conjuntos de puertas lógicas universales que permiten escribir cualquier circuito lógico (o función lógica); por ejemplo, basta la puerta NAND (o NOR), o las puertas AND y NOT (o OR y NOT). Sin embargo, usando solo AND y OR no es suficiente, pues estas puertas no permiten escribir la negación NOT.

Shannon (1949) propuso que el número de puertas lógicas de un circuito booleano es una medida de la complejidad de la función (o fórmula) que calcula el circuito. Savage (1972) demostró que todo problema en P (que una máquina de Turing resuelve en tiempo polinómico) se puede resolver con una familia de circuitos de tamaño (número de puertas lógicas) polinómico. En los 1970 parecía que los circuitos booleanos eran un camino muy prometedor para resolver la cuestión P vs NP: bastaba encontrar una función para lo que no existan circuitos lógicos de tamaño polinómico para demostrar que P≠NP. Se puede demostrar que la mayoría de las funciones booleanas de n variables requieren circuitos de tamaño exponencial en n; basta encontrar una entre ellas que sea superpolinómica.

La línea de demostración de P≠NP basada en la complejidad computacional de los circuitos lógicos parecía muy prometedora a principios de los 1980. Norbert Blum lleva trabajando en ello desde entonces. Sin embargo, muchos expertos empezaron a cambiar de opinión cuando se encontraron varias barreras que parecían imposibles de superar. Por ejemplo, Valiant (1990) ya apuntaba que este camino llevaba a un callejón sin salida y recomendaba seguir otras líneas de  trabajo.

El estudio de circuitos booleanos restringidos ha sido explorado por muchos expertos. Destacan los circuitos monótonos, que no tienen puertas de negación NOT, solo de conjunción AND y disyunción OR; se llaman así porque estos circuitos calculan solo funciones monótonas, tales que si x ≤ y entonces f(x) ≤ f(y). En inglés, se llama clique a un grupo de personas que comparten un interés común; en español sería algo así como una pandilla o una camarilla, pero en teoría computación no se usa la traducción (y se suele pronunciar en inglés, algo así como click). En teoría de grafos, un clique de un grafo es un subgrafo en el que cada vértice está conectado todos los otros vértices de dicho subgrafo; el tamaño del clique es su número de vértices.

El problema clique consiste en dado un grafo, decidir si existe un clique con un tamaño dado j < n (el número de vértices del grafo); este problema es NP-completo. Razborov (1985) demostró que la función clique que resuelve el problema del clique (para j suficientemente cercano a n) tiene una complejidad computacional monótona superpolinómica (solo usando puertas AND y OR); Andreev (1985) y Alon y Boppana (1987) demostraron que su complejidad monótona es exponencial. Si se extendía este resultado al caso no monótono (incluyendo la negación NOT), entonces se lograría una demostración de P≠NP. Por supuesto, se puede transformar todo circuito general (no monótono) que calcule una función monótona en un circuito monótono; si se pudiera hacer en tiempo polinómico, tendríamos resuelto el problema P≠NP. Razborov (1985) demostró que esto no es posible. Éva Tardos (1988) demostró que hay un problema monótono en P que requiere un circuito monótono de tamaño exponencial.

Razborov y Rudich (1993) desarrollaron la noción de demostración natural: si no hay demostraciones cortas (polinómicas) de una tautología, entonces P ≠ NP. Te recuerdo que una tautología es una función lógica f(x,y,…)=1 para todos los posibles valores de sus variables x,y,… Por ejemplo, f(x,y) = (x AND y) OR (NOT x) OR (NOT y) es una tautología, f(x,y)=1. Para decidir que una función f(x,y,…) no es una tautología basta encontrar un contraejemplo, unos valores de sus variables tales que f(x,y,…)=0; pero para decidir si es una tautología, o se prueban todos los valores posibles (una cantidad exponencial), o se encuentra una demostración matemática.

Se llama forma normal disyuntiva (DNF) es la escritura de una fórmula lógica como una disyunción de conjunciones en la que las negaciones solo se aplican a las variables individuales. Como es obvio, toda fórmula se puede escribir como DNF, pero solo si se permite el operador NOT; por ejemplo, (x AND NOT y AND NOT z) OR (NOT x AND z) OR z, está en DNF, pero x OR NOT (y AND z) no lo está (su forma DNF es x OR NOT y OR NOT z). Se llama forma normal conjuntiva (CNF) a la fórmula escrita como conjunción de disyunciones, con negaciones solo en las variables individuales. En la demostración automática de teoremas se suelen usar la DNF o la CNF para facilitar las operaciones. También se puede usar el intercambio DNF/CNF, que consiste en escribir las fórmulas en ambas formas normales y elegir la más corta de las dos para continuar con la demostración.

Una forma de demostrar una tautología escrita en forma DNF se llama resolución: si tenemos dos fórmulas (ψ1 AND x) y (ψ2 AND NOT x), se pueden sustituir por (ψ1 AND ψ2). Una fórmula DNF es una tautología si aplicando resoluciones se puede reducir a la fórmula identidad. Haken (1985) mostró que hay tatutologías para un problema concreto que no tienen demostraciones cortas por resolución. Tras los argumentos de Razborov y Rudich (1993) parecía que el camino de los circuitos monótonos había llegado a su fin; el uso de la complejidad de circuitos monótonos para demostrar P≠NP se considera un callejón sin salida.

Por supuesto, ha habido trabajos más recientes en esta línea, como el nuevo trabajo de Blum (2017). Pero dichos trabajos deben dejar muy claro cómo resuelven las barreras de complejidad circuital que se conocen. El nuevo trabajo de Blum no lo aclara de forma explícita. Si Razborov le ha dicho a Mikhail que dichas barreras siguen tan firmes como estaban, me temo que puede tener razón. Aún así, Blum lleva investigando en este campo desde principios de los 1980. Mientras ningún experto aclare exactamente dónde ha metido la pata, no podemos estar seguros de que la haya metido.

Por cierto, por Twitter hay quien dice que si Razborov tras una lectura rápida afirma que la prueba de Blum está mal, sin más detalles, entonces está mal y punto. Permíteme un grano de sal; por ahora solo tenemos la opinión de Razborov, un argumento de autoridad. Hasta que no se publiquen más detalles debemos ser cautos con estas afirmaciones.



36 Comentarios

  1. Acabo de entrar en el blog de Scott Aaronson, y el tampoco lo ve «[…] the paper claims to give an exponential circuit lower bound for Andreev’s function, but that function as defined in Section 7 of the paper seems clearly to have a polynomial-size circuit, based on polynomial interpolation (thanks to Luca Trevisan for this observation). So I don’t see how this can possibly stand»

    Sea como fuere, como aficionadillo que solo es capaz de seguir a «aficionados» de altura como vosotros, en cuanto he leído «Primero, todo el mundo espera que una demostración de P≠NP ayude a entender la diferencia entre P y NP; la demostración de Blum no aporta nada relevante al respecto» Pues ya me ha quedado claro.

    Me pregunto si esta será una de esas cuestiones, que en vez de solucionarse, acaban desvaneciéndose finalmente entre nuevos paradigmas.

  2. Dice Norbert Blum (traducción aproximada):

    -Para el característico problema NP-Completo de la función cliqué se cree que las negaciones no pueden ayudar demasiado a mejorar la complejidad Booleana de exponencial a polinomial.

    En tanto en cuanto se puede simular una máquina de Turing de una cinta con un circuíto booleano no-monótono de un tamaño superior al cuadrado de los pasos necesarios, un superpolinomio de límite inferior para la complejidad del circuito no-monótono de dicha función implicaría que (P!=NP).-

    Independientemente de lo interesantísimo de que todo algoritmo se pueda expresar con circuitos no-monótonos (que es lo que parece haber demostrado) no logro entender (por favor a ver si alguien me lo puede explicar) por qué se presupone que un problema no puede ser resuelto con un algoritmo más eficiente que el que resulta de la simulación con circuítos booleanos no-monótonos.

    Resulta inverosímil decir que una máquina de Turing que resuelve un problema de manera poco eficiente, con la «simulación» mediante funciones booleanas (tengan o no operadores NOT) va a ser la más óptima; o siquiera mejor. De hecho creo que (insisto no lo he leído todo) lo que esta demostrando (si acaso) es exactamente que el coste de dicha transformación/simulación es equivalente.

    1. Íñigo, lo que pretende demostrar Blum es que si los circuitos monótonos de tamaño polinómico (para un problema monótono) admiten esta aproximación a no monótonos, para una promesa del problema, entonces también lo admitirá culquier circuito general del problema (el problema completo), por lo tanto, si no existe esta aproximación, no solo la promesa restringida será super polinómica, también cualquier circuito general.

      Como sabes estaba demostrado, que el problema Clique no se podía resolver con circuitos monotonos polinómicos, de hecho los requiere de tamaño exponencial; para demostrarlo Razborov se basó en un método de aproximaciones donde para un problema más «débil» que el propio Clique, una versión promesa, es decir, un clique solo para un subconjunto de datos de entrada, el circuito polinómico monótono no era suficiente, y por lo tanto no lo sería para todo él.

      Lo puñetero aquí, es que el problema «Perfect Matching». es un problema traidor, que está en P, pero no admite circuitos monótonos polinómicos, por lo que parecía que seguir dándole vueltas a ese tema con el Clique no nos iba a llevar a ningún lado, es decir, que demostrar el hecho de que no tuviera este tipo de solución no implicaba que no estuviera en P

      Además Razborov había demostrado que su método de aproximaciones solo se podía aplicar hasta ciertos límites.

      Pues bien, lo que hace Blum es resucitar el muerto de nuevo, y modificando lo que Razborov definió como aplicación de las aproximaciones a los circuitos generales (lo que comenta Francis de la pseudo distancia) y a partir de los trabajos sobre aproximaciones de Berg y Ulfberg de monótono a no monótono, concluye lo que comento más arriba, y por lo tanto Clique no está en P, ergo NP !=P

      1. Me parece que el argumento que sirve de corolario es una falacia. En tanto en cuanto se hable de problema y no de funciones este argumento podría ser válido, no obstante cuando hablamos de expresar un problema mediante circuitos booleanos nos debemos referir a todos los posibles circuitos booleanos que resuelven un problema, no al circuito que representa una (única) función booleana, por muy genérica que parezca.

        Debe quedar claro que un circuito booleano representa una función, no la mejor solución posible a un problema. Un mismo problema puede ser expresado mediante infinidad de funciones, ya sean monótonas o no.

        La complejidad de los circuitos booleanos se refieren al mejor circuito que compute una función booleana, esto no significa que dicho circuito sea la mejor solución a un problema.

        Las demostraciones de Blum, así como las precedentes de Razborov, en todo caso se refieren a las funciones que representan una solución al problema, pero no demuestra que es la mejor función para resolverlo.

        Hasta la fecha no tenemos un mecanismo que produzca la mejor función booleana para un problema dado por lo que este argumento es insuficiente para demostrar que P!=NP.

        1. No lo has entendido, no es una solución al problema; es una especie de contraejemplo rocambolesco y para eso en matemática si que con un solo caso basta.

  3. Francis, parece que Molt te lee; referencia este artículo; me pregunto si lee español.

    Por cierto, me extraña que no hayan aquí más comentarios ¿está de vacaciones el revisor de comentarios de naukas? 😉

  4. No he comentado, porque me ha dejado muy extrañado, no lo conocía, tengo que leermelo, pero ahora no puedo.
    Yo sé que con sólo NAND se puede hacer de todo, de hecho he programado muchas gate array, desde las antiguas PAL, pasando por las Xilin y Alteras, ahora vienen incorporados en muchos microcontroladores, por ejemplo en los PICs, con el nombre de CLC.
    Incluso he hecho un amplificador bidireccional para I2C, teniendo incluso en cuenta los tiempos de propagación.
    Me gusta mucho lo que escribe Francisco y aprendo mucho, de hecho mi enhorabuena.
    Pero esta vez me he quedado en blanco, a ver si saco tiempo.

        1. De ser cierto lo que dice Mikhail, Razborov ni se había molestado en principio en leerlo; cuan claras tiene las cosas respecto al camino que él mismo abrió.

  5. Francis, dices «…Sin embargo, encontró una función booleana monótona de complejidad polinómica para la que el salto de complejidad computacional entre el caso monótono y el caso no monótono era exponencial…» Posiblemente no estoy entendiendo la frase, pero ¿no es al revés? ¿No fue que encontró un problema en P que no admitia un circuito monótono polinómico?

  6. A ver si lo consigo entender (prometo empollarmelo a fondo algún día)
    Dices : “bastaba encontrar una función para lo que no existan circuitos lógicos de tamaño polinómico para demostrar que P≠NP.”

    Cuando dices función te refieres a un algoritmo o a un problema?

    Seguido parece que esta la clave del asunto: “Se puede demostrar que la mayoría de las funciones booleanas de n variables requieren circuitos de tamaño exponencial en n; basta encontrar una entre ellas que sea superpolinómica.”

    ¿No habría que demostrar que todas (no solo la mayoría) las funciones booleanas de n variables requieren al menos un coste superpolinómico? ¿Como llega a eso Blum?

    1. Añado …
      Recuerdo en mis tiempos mozos cuando estudié Electrónica Digital que era novedoso lo de los mapas de Karnaugh. Por si no lo recordáis, o ya no se estudia, con este método se conseguía obtener una función canónica reducida de una tabla de verdad dada. Si se pudiera demostrar que para una tabla de verdad dada la reducción por Karnaugh es la menor posible y además el tamaño de función canónica resultante fuera superpolinómica con respecto del número de variables booleanas, entonces sí, se demostraría que P!=NP. Bueno, ojo, por lo menos se debería comprobar que para muchas variables de entrada se supera n^15.

    2. Iñigo, para demostrar que P≠NP es suficiente demostrar que un solo problema en NP no está en P. Quizás te confundes con P=NP, o bien demuestras que todos los problemas en NP están en P, o bien demuestras que un solo problema NP-completo está en P.

      La idea de Blum era mostrar que un problema NP concreto (de hecho uno que es NP-completo) no está en P.

      1. Por supuesto, eso lo tengo claro, pero si ves hablas de problema no de función. Estarás conmigo en que para demostrar que un problema esta en NP hay que verificar que todas las funciones que resuelven ese problema están en NP, o bien, como decía obtener la función booleana mínima posible para un problema y demostrar que tanto dicha función es la mínima irreductible y que el coste de implementar esa función es NP. (Por favor confirmame que no soy el único en el mundo que lo ve así)

        Para eso último sería necesario conocer la tabla de verdad de antemano, es decir, las 2^(n-1) combinaciones posibles y sus resultados. Lo que decías de la DNF/CNF con negaciones sirve para obtener la función booleana de esta tabla. Hay diversas técnicas, entre ellas la de Karnaugh, que permiten reducir la función booleana, pero que yo sepa no esta demostrado que alguna de ellas sea infalible.

        Esta claro que no se puede encontrar un ejemplo (llamémoslo E) para el que dados unos datos de entrada que producen una salida conocida sean necesarios k^n operadores. Lo que pretendía Razborov es demostrar lo contrario, que cualquier circuito de n puertas lógicas, no puede implementar una tabla de verdad de un problema conocido de clase NP. Para eso usa los aproximadores de límite inferior en el problema simple del cliqué. No obstante estos aproximadores son la pescadilla que se muerde la cola (eso ya lo debe saber Razborov) por que para demostrar que ese aproximador es correcto necesitas un ejemplo E. No se si Blum hace algún truco de magia pero por lo que dicen por ahí se ha liado, y no me extraña.

        1. «Estarás conmigo en que para demostrar que un problema esta en NP hay que verificar que todas las funciones que resuelven ese problema están en NP»

          No; sabes que un problema está en NP, porque dada una determinada solución positiva al problema, puedes verificar si ésta es positiva en un tiempo polinómico. Un problema que sea de tipo NP puede ser perfectamente de tipo P, por ejemplo el problema de emparejar compañeros de cuarto o el de secuenciación del ADN son problemas de tipo NP que están en P.

          En cambio, hay problemas NP, como el de la suma de subconjuntos, que no sabemos si están en P, pero que además, al ser NP-completos, es decir, al ser tales que todo tipo de problema NP puede reducirse a ellos, si se demostrara que son de tipo P, todos los NP serían P y por lo tanto NP=P, pero si se demostrara que NO son P, entonces, a pesar de que hay algunos NP en P, no serían iguales NPP.

          Nota: tengo la sensación de que estás confundiendo los problemas NP con aquellos que no admiten soluciones polinómicas, es un error muy común, obviamente no es así, pues si fuera el caso, NP!=P y punto pelota. Pero no.

          1. No me confundo en eso, quería decir NP-completo. La verdad es que parece un trabalenguas, corrijo … “Estarás conmigo en que para demostrar que P!=NP hay que verificar que todas las funciones que resuelven un problema están en NP-completo” ¿Si?

          2. Iñigo, una de las sorpresas de la teoría de la complejidad para los profanos es que en los problemas de decisión NP hay un subconjunto de problemas tales que todo problema de NP se puede reducir con coste polinómico a uno de dichos problemas, llamados por ello problemas NP completos. Así que basta verificar que un problema NP-c no es polinómico para que P y NP sean diferentes; además, de forma automática será cierto para todos los problemas NP-c. Ahora bien, ello no quita que muchos problemas que hoy pensamos que están en NP, pero no en NP-c, en realidad sean problemas en P mal clasificados en NP. Es decir, los problemas que «de verdad» están en NP son los NP-c; los demás de NP, pueden estar «de verdad» en NP o «de verdad» en P, no lo sabemos y resolver la cuestión NP vs P no nos dará información sobre ello (a priori).

  7. Cierto, pero eso no contradice mi deducción: Para demostrar que P!=NP hay que verificar que todas las funciones que resuelven un problema están en NP-completo, y eso no lo hace en ninguna parte Norbert Blum.

    En realidad si un problema NP-completo se resolviera de manera determinista con una heurística, función, lenguaje, algoritmo, Máquina de Turing, circuito booleano, o como se quiera llamar, con un coste polinómico tendríamos que decir que dicho problema es de clase P. Supongo que por extensión todos los problemas NP-completos también lo serían a no ser que ese problema NP-c estuviera mal clasificado previamente. ¿Como se determina la clasificación de un problema NP-c? ¿Basta con que por fuerza bruta el coste sea exponencial y que además la comprobación de una solución tenga un coste polinómico.?

    1. Cuando digo «todas las funciones que resuelven un problema» me refiero a todas las representaciones algebraicas de la tabla de verdad propia del problema. Por otra parte esta frase se podría sustituir (sin menoscabo de su validez) por «la representación mínima de la tabla de verdad propia de un problema».

      Hay que tener en cuenta que una función booleana se puede representar algebraicamente de infinitas formas, solo la representación mínima es la que nos dirá si la función es polinómica o suprapolinómica.

    2. . ¿Como se determina la clasificación de un problema NP-c? . ¿Basta con que por fuerza bruta el coste sea exponencial y que además la comprobación de una solución tenga un coste polinómico.?
      No, Iñigo, es por el teorema de Cook.
      Iñigo, párate a pensar un momento, ¿de verdad crees que si fuera como tú dices, no se estaría trabajando en es línea?

      Si estás interesado en complejidad computacional, los clásicos recomendados son el Sipser, el de Arora and Barak o el de Oded Goldreich. Es muy ameno también el de Scot aaronson , el de Quantum computing since Democritus.

  8. Gracias Pedro me lo voy a empollar, no obstante, la pregunta era retórica claro. Lo que no pillo es tu pregunta. ¿A qué te refieres cuando dices «si fuera como tú dices»? Si te refieres a que hay que buscar “la representación mínima de la tabla de verdad propia de un problema”, la respuesta es Sí, si lo creo, si no demuestras que un circuito o expresión algebráica es la mínima e irreductible de la tabla de verdad de un problema, no demuestras que P!=NP por mucho que esa expresión/representación sea superpolinómica. Lo que dice Francis de las tautologías se refiere a eso exactamente.

    1. Me refería a si de verdad crees que a un experto como Blum, se le ha escapado hacer tal comprobación, en vez de venir implícito ya en la teoría subyacente en la que se basa. Solo eso.

      1. Sí. Por lo que he leído de Razborov de las reducciones y de los aproximadores no lo veo demostrado. De hecho de estarlo la misma demostración concluiría que P!=NP.

        Ya de paso, como te veo que controlas del tema … empollando un poco el asunto veo que hay aproximaciones PTAS para problemas NP-hard, lo que los convierte además en APX-completos si no entiendo mal. Si para un APX-completo logramos un algoritmo determinista, ¿significaría que P=NP?

      2. Corrijo mi anterior comentario/pregunta. Como bien dice Francis que sea determinista no influye. Quería decir que si para un APX-completo damos con un algoritmo que resuelve el problema en tiempo (y recursos) polinómicos, ¿estamos resolviendo en realidad un NP-hard en tiempo P? Eso implicaría P=NP si no me equivoco.

          1. Sí.
            Las clases de aproximación me resultan un poco confusas. Parece que todos los (o muchos) problemas están condicionados a la precisión de las variables de entrada y de salida.

            Por ejemplo por mucho que tenga un algoritmo que resuelve la distancia entre dos puntos de un plano en tiempo polinómico en realidad solo puedo calcular la distancia exacta de algunos números, los representables con la cantidad de bits de la salida. Por mucho que aumente la precisión de la salida habrá resultados que no sean representables en binario, mismamente PI. Entiendo que mi algoritmo en este caso sera un PTAS y nunca un P.

            En mi opinión siempre que la salida cumpla la misma precisión de los inputs de entrada, y no haya otro factor que merme el resultado, si el algoritmo es polinómico debería ser P y no PTAS. No sé si me explico.

  9. Hola Francis & co … me he estado empollando el tema. Fuera a parte que parece que se confirman mis sospechas respecto de lo que decía de la solución de Blum creo que he dado con un algoritmo que resuelve un problema tipoTSP grid en tiempo polinómico pero me surgen dos dudas, a ver si me podéis dar alguna referencia o iluminarme un poco el camino :

    1) los problemas de tipo TSP en Grid (Hamiltonicity o similar) o de manera general aquellos grafos Euclideos en los que cada vértice solo esta conectado con los k más próximos son problemas NP-c?

    2) dado un algoritmo que resuelve estos problemas si monitorizamos el número de operaciones «C» que realiza según el número de vértices y obtenemos una gráfica donde la componente X representa el número de vértices y la componente Y el exponente al que debemos elevar X para que resulte C, es decir C = x^y, si dicha gráfica tiene una curvatura que induce un límite asintótico en Y relativamente bajo (aparentemente dependería de k) y además su crecimiento (conceptualmente su derivada) tiende a ser lineal, por lo que que en consecuencia no cumple la regla de derivación exponencial {(d/dx)e^x = e^x}, ¿Podemos asegurar entonces que el coste de dicho algoritmo es polinómico?

      1. Gracias Francis. No obstante, si un NP-hard se resuelve en P también se verifica en P así que los NP-hard serian NP-c y al mismo tiempo los NP-c serián P. Es lioso pero es así, ¿no?

        Lo de la gráfica es una puñeta vaya.

Deja un comentario