Esta entrada ha sido escrita en colaboración con Alberto Márquez @twalmar, sin cuya ayuda no podría haber afrontado tan titánica tarea. ¿De qué va esta entrada? Teniendo en cuenta que el título es bastante explícito tan solo diremos que está en nuestro ánimo aclarar de la forma más exquisita posible el problema P/NP. Somos conscientes de que se han escrito miles de palabras sobre el tema a nivel de divulgación y popularización. Desgraciadamente, también somos conscientes de que un alto porcentaje de las mismas son mamarrachadas de un considerable calibre. Esperamos con anhelo no formar parte de ese excelso conjunto con esta, nuestra pequeña contribución.
Esta entrada se complementa con el programa 29, de @Los3_Chanchitos (específicamente la tercera sección conducida por Alberto), por si eres aficionado al tema podcast:
Y con este vídeo por si le das más al tema YouTube (también de Alberto):
El problema que pretendemos desgranar es bello, es hermoso, es complicado y es esencial para la matemática y para la física. Su solución en un sentido u otro, y aclararemos eso en esta entrada, supondrá una demostración de que hemos entendido algo del universo o bien que no habíamos entendido nada pero que será fácil empezar a entenderlo todo. (Estamos siendo crípticos en pleno uso de nuestras facultades mentales). Vamos a establecer qué es eso del problema P/NP.
Si cuando hayas leído esto te encanta el tema y quieres agradecerlo estaría genial que pulsaras el botón que tienes abajo y votaras a los tres chanchitos (dirección: 3chanchitos.es) para el mejor podcast en el premio Bitácoras de este año:
Vamos al lío… Nunca mejor dicho.
Comprobar y resolver no parecen lo mismo pero tampoco lo sabemos seguro
¿Qué te parece más fácil? Que te den un sudoku gigante y te pidan que lo resuelvas o que te den el mismo sudoku relleno de números y te pidan que compruebes si está bien resuelto.
Resuelve:
Comprueba:
No sabemos qué pensaréis, pero nosotros tenemos la intuición de que es más fácil comprobar que resolver. Esto en mates suele ser bastante más hiriente. En general, tenemos la sensación de que es mucho más fácil comprobar si algo que te dan es solución de un problema que encontrar una solución al problema por ti mismo. Por ejemplo, es más fácil comprobar que x=5 resuelve la ecuación x^2+x-30=0 que encontrar la solución por nuestros propios medios. Y eso que hemos puesto un ejemplo chorra, las cosas se pueden poner muy feas en matemáticas.
Pero, ¿es más fácil comprobar que resolver? ¿Seguro? Que nos parezca más fácil comprobar que resolver no significa que eso sea lo correcto. Especialmente cuando tratamos con gentes de matemáticas, porque ya sabéis: Esto es matemática y aquí hay que demostrar. De todas formas nosotros no confiaríamos ni un pimiento en nuestra intuición, por poner un ejemplo, la materia nos parece continua y sabemos que en realidad es un puñado de átomos muy lejos los unos de los otros en relación a los tamaños típicos de los átomos. La materia de continua tiene poco. Así que tampoco os vengáis arriba y no asumáis que vuestra intuición vale para mucho. Tendremos que convivir con ello.
Resolver o comprobar es cuestión de tiempo
Vamos a entrar en harina, dijo el caracol (chiste autóctono de la zona donde los autores crecieron y que es graciosísimo porque los caracoles se meten en harina para secarles las babas antes de empezar a cocinarlos) y vamos a hablar de complejidad computacional.
El campo de la complejidad computacional enmarca su campo de aplicación a la clasificación de los distintos problemas en función del tiempo que tardamos en resolverlos con un algoritmo o receta matemática diseñada para tal efecto. Es un campo ciertamente complejo que tiene sus raíces en la lógica, la combinatoria y los fundamentos más básicos de la matemática como llegaremos a intuir en el transcurso de esta compleja entrada (otro chiste). Nos podríamos poner muy formales pero la verdad nos quedaría una cosa bastante pedante. Por el bien tanto de nosotros como autores como de vuestras mercedes, lectoras y lectores de esta entrada, vamos a procurar simplificar la palabrería propia del tema procurando en todo momento no decir nada que roce lo absurdo o incorrecto.
Centremos el tema…
Supongamos que tenemos un problema y un algoritmo para él, es decir, una receta de pasos que si los seguimos encontramos una solución al problema. La situación no puede ser más idílica. ¿Qué podemos pedir más? Si tenías un problema y has encontrado un algoritmo que lo resuelve ya no hay problema del que preocuparse.
Ese es el caso hasta que llega la típica persona que hace la típica pregunta incómoda. En esta situación la pregunta es:
¿Cuánto tarda el algoritmo en encontrar la solución?
-Uuupsss-, es lo primero que a cualquiera se le vendría a la cabeza para esa pregunta.
Se puede dar el caso de que tengamos un algoritmo que encuentre la solución pero que el tiempo que tarde en encontrarla sea tan alto que a efectos prácticos no tenemos solución alguna. Imagina que tu algoritmo necesita varias veces el tiempo de vida del universo en encontrar la solución, ciertamente es un algoritmo poco operativo.
Otra pregunta que nos puede poner en un brete es: ¿De qué tiempo hablas cuando hablas de tiempo en este contexto? Y esa es una muy buena pregunta porque para resolver el problema se lo tenemos que dar a una máquina en la que hemos programado el algoritmo y que ejecuta los pasos del mismo haciendo las operaciones necesarias para llegar a dar una respuesta. Es evidente que no es lo mismo usar un spectrum que un supercomputador o tu propia cabeza. Cada uno en función de su hardware o el lenguaje de programación elegido tardará más o menos.
Aquí lo interesante es trabajar con generalidad sin comprometernos con una máquina concreta o un lenguaje de programación concreto. Así establecemos que el tiempo que tarda un algoritmo en realizar su tarea como el número de operaciones necesarias para finalizar su trabajo y dar una respuesta. Evidentemente si nuestro supercomputador resuelve un problema en segundos, el spectrum podrá tardar una semana, un mes o años, pero es un tiempo manejable. Si el supercomputador necesita el tiempo de vida del universo para solucionar un problema…
Por lo tanto, el tiempo asociado a un algoritmo es el número de operaciones que ha de realizar para resolver un problema. A eso se le denomina complejidad del problema.
La complejidad no hace referencia a lo fácil o difícil que sea resolver el problema en términos coloquiales sino a la que hay que liar, el número de operaciones necesarias, para resolverlo. En realidad, el problema está resuelto teóricamente, tenemos un algoritmo que lo hace, el tema es cuánto tiempo tardará en hacerlo, es decir, cómo de complejo es llegar a la solución.
Detente un segundo a recapacitar sobre lo que llevamos y prométenos que no seguirás leyendo hasta que tu cabeza esté convencida de haber pillado estos detallitos. Mientras haremos un comentario para los tiquismiquis.
Nota para exquisitos: Sí, lo sabemos, aquí podríamos haber sacado las plumas de pavo real y meternos a discutir sobre la notación de Landau, asintotismos (sí, también sabemos que no existe esa palabra, pero ahora ya sí existe) varios y cotas inferiores y superiores. Si crees que es estrictamente necesario y se te ocurre una forma divertida de contarlo puedes enviar tu aporte a cuentos.cuanticos@gmail.com. Gracias por adelantado.
El tamaño importa
Vamos a empezar por un ejemplo sencillo. Esto va de multiplicar números.
Caso 1:
Suponte que te piden encontrar la solución al problema 5 x 7. Este es un problema matemático del que tenemos un algoritmo, al menos uno, para encontrar una solución. Eso requiere una operación.
Ahora imaginemos que nos piden resolver el problema 23 x 19. ¡Chupado! (Nota: En castellano español se dice que un problema o alguna tarea está chupado/a si es fácil de hacer) . Eso sí, ahora requerimos cuatro operaciones (solo contamos las multiplicaciones que hemos de realizar, también hay que hacer unas cuantas sumas pero consideramos que eso no cuesta tiempo de cálculo comparado con las multiplicaciones).
¿Cuántas operaciones necesitamos para multiplicar dos números de 3 cifras? ¿Y de 4 cifras? Está claro que empleando el algoritmo que nos enseñan en los coles tendremos que realizar 9 y 16 operaciones respectivamente.
Así, podemos decir que el algoritmo de multiplicación (para números del mismo número de cifras en este caso) tardará más o menos dependiendo del tamaño de los números iniciales que queremos multiplicar.
Cuando hablamos del tiempo que tarda un algoritmo en resolver un problemas hemos de referirnos al número de operaciones necesarias en función del tamaño de los datos de entrada del problema.
Otros ejemplos, otros problemas:
Imaginemos que hemos ganado grandes dineros y nos da por fundar institutos de investigación por España.
Primer problema:
Una vez que hemos construidos los institutos, los hemos dotado de material, etc, queremos conectarlos por fibra óptica. La cuestión es que queremos encontrar la mínima cantidad de fibra para unirlos todos sin crear nuevos puntos de conexión. Queremos que todos estén unidos y queremos que no nos salga muy caro. Así es la vida.
Lo que podemos hacer es poner los institutos como puntos y la fibra la representamos con líneas que unen dichos puntos, es decir, construimos un grafo. Sobre cada línea del grafo le ponemos la cantidad de fibra, en metros, que hay que tirar para unir dos institutos. La idea es la de unirlos todos empleando la cantidad mínima de fibra. Y recordad, no podemos meter nodos nuevos auxiliares.
Pongamos ejemplos, dos institutos, tres institutos, cuatro institutos, etc…
Para dos institutos solo hay un red para unirlos por fibra. Resuelto.
Para tres institutos tenemos tres redes posibles para unirlos. Solo hay que conocer las distancias entre los institutos y quedarnos con la opción de mínima distancia de fibra empleada.
Para cuatro institutos:
Ya nos vamos a 16 redes. Así que tenemos un algoritmo que resuelve el problema. Solo hay que generar todas las posibles posibles, árboles en grafos, y quedarnos con el de menor distancia (las distancias entre los institutos son conocidas). Pero eso significa generar todos los posibles árboles o redes, calcular la distancia total de fibra en cada uno de ellos y quedarnos con la mínima.
El problema es que para 100 institutos, nodos del grafo tenemos 
La complejidad de este algoritmo que resuelve, ojo que sí resuelve el problema, es como mínimo de 
Lo que ocurre es que hacer eso a las bravas se va de madre en cuanto tengamos un número apreciable de elementos a conectar de forma mínima. El tiempo que tardaríamos en hacer eso a lo bruto crece muy rápido al aumentar el tamaño de la entrada del problema.
Para este caso en concreto existe una idea feliz que hace que el tiempo que se tarda en dar una respuesta al problema sea de $n log(n)$. Y ese es un tiempo mucho más manejable. Es decir, en ocasiones gracias a alguna propiedad matemática podemos «simplificar» el algoritmo para que su tiempo sea manejable y nos de una respuesta antes de que hayamos pasado al olvido.
Nota: La idea feliz de este problema es hacer el diagrama de Voronoi sobre la base de los nodos disponibles y establecer la triangulación de Delaunay. Luego tomamos todas las aristas las ordenamos según su longitud y vamos tomando en cada paso la más corta siempre que no se haga un ciclo. El resultado final es el árbol de longitud mínima.
Para este problema que si lo resolvemos calculando todos los caminos y comprobando su distancia total es poco efectivo podemos encontrar un algoritmo que lo resuelve de forma razonable. Este es un detalle importante.
Segundo problema:
Supongamos que nuestros institutos empiezan a funcionar y te dicen que des una charla en todos los institutos, empezando y terminando por el tuyo, de forma que la ruta que hagas sea mínima en distancia. Eso lo hace más barato. Esta es una variante adaptada del conocido como Problema del Viajante.
Aquí otra vez podemos hacer el truco de poner nuestros institutos en forma de grafos y pintar ciclos que salgan de nuestro instituto y acaben en él. Solo tenemos que calcular la distancia de todos los caminos cerrados y quedarnos con la más pequeña.
Para un número pequeño de elementos a conectar de la forma descrita no hay problema, eso se hace muy rápido. Pero la cuestión está en que tenemos que el número de operaciones para unir n puntos en un ciclo cerrado son (n-1)!.
Aquí «!» no indica exclamación sino factorial. Un número factorial se calcula multiplicando todos los enteros empezando por el que te dan hasta el 1.
1!= 1
2!= 2·1
3!= 3·2·1
Esa es una mala noticia porque los números factoriales crecen mucho, muchísimo.
Ahora estarás esperando que te digamos que hay una forma inteligente de resolver este problema de una forma elegante en un tiempo razonable. Que aplicando propiedades matemáticas eso se simplifica y tenemos un algoritmo genial que hace eso muy rápido.
Lo sentimos, no tenemos ni idea. No sabemos si existe o no ese algoritmo, nadie ha probado que exista o que no exista. Y eso es muy importante para lo que sigue.
Pero dejadnos insistir en una cosa. Sabemos resolver el problema, basta calcular todos los caminos que empiezan y terminan en un punto y quedarte con el de longitud mínima. La solución es fácil… Lo que pasa es que esa solución no se puede implementar en tiempo razonable. Si el tamaño de puntos a conectar es elevado el algoritmo es inútil.
Para acabar esta sección supongamos que tenemos tres problemas y que hemos encontrado la forma de solucionarlos, tenemos un algoritmo para cada uno de ellos. Sin embargo, para el primer problema el número de operaciones va como 
Ya se ve dónde está el gato encerrado. Todos los problemas se pueden resolver, el punto clave es el tiempo que tardamos en encontrar la solución.
P y NP
Es hora de entrar en el meollo de la cuestión. P y NP son etiquetas que les asignamos a los problemas. Estás etiquetas no están relacionadas con «se puede resolver» y » no se puede resolver». Eso tiene que quedar claro.
Vamos a definir estas etiquetas de los problemas:
Problemas tipo P
Diremos que un problema es de tipo P cuando conocemos un algoritmo que lo resuelve en tiempo de la forma 
Es decir, los problemas P son aquellos que se pueden resolver en tiempo razonable. Hay que hacer un número de operaciones que crecen lentamente, polinómicamente para ser estrictos, con el tamaño del dato de entrada.
Problemas de tipo NP
Diremos que un problema es de tipo NP cuando conocemos un algoritmo que es capaz de comprobar si algo dado es solución del problema en un tiempo polinómico.
Vamos que los problemas NP son aquellos para los que podemos comprobar si algo es solución en tiempo razonable dependiendo del tamaño de la solución propuesta.
Eso no quiere decir que no exista un algoritmo que los resuelva en tiempo polinómico. Lo que quiere decir es que no sabemos si existe o no, ese es el problema realmente.
Ahora viene un detalle esencial… abrid bien los ojos y las cabezas.
Todos los problemas P son NP
¡Evidentemente!, habrás pensado. Si los problemas P son aquellos para los que tenemos un algoritmo que los resuelve en tiempo razonable (polinómico) es lógico que podamos comprobar si algo es solución en tiempo razonable, el propio algoritmo que lo resuelve es un ejemplo. Tú nos das una solución, nosotros corremos nuestro algoritmo y nos da una respuesta en un tiempo razonable, comprobamos si la solución del problema es la que tú nos has dado o no lo es. Por tanto hemos comprobado si algo es solución en tiempo polinómico.
Pero dado que los problemas para los que podemos comprobar si algo es solución son los problemas NP entonces todos los problemas P son NP por derecho propio.
Podemos representar esto usando diagramas de conjuntos:
Es decir, los problemas que podemos resolver en tiempo razonable están incluídos en los problemas que podemos comprobar si algo es solución en tiempo razonable. Los problemas P son problemas NP.
Vayamos al problema de verdad, ¿P=NP?
Muchas veces se dice que los problemas P son los que se pueden resolver y los problemas NP son los que no se pueden resolver.
Si esa es la definición hemos demostrado ya que P no es igual a NP, fin de la historia. Si unos se pueden resolver y otros no entonces se ha acabado el juego.
El problema es que hay problemas NP que no sabemos si admiten un algoritmo que los resuelva en tiempo razonable, es decir que sean en realidad de la subclase P. Hay muchos problemas NP para los que se conocen algoritmos para resolverlos solo que no dan la respuesta en un tiempo razonable. Puede que todos los NP se puedan resolver en tiempo razonable y puede que no. Eso es justamente lo que se nos plantea.
Las situaciones que podemos tener son:
a) Que P no sea igual a NP. Resolver no es igual a comprobar.
b) Que P y NP sean iguales. Resolver y comprobar son igualmente de complicados.
Para demostrar que P y NP no son iguales bastaría con mostrar que un único problema de tipo NP no admite un algoritmo que lo resuelva en tiempo polinómico.
Claro, para demostrar que todos los problemas NP son P tendríamos que encontrar para todos y cada uno de ellos un algoritmo que los resuelva en tiempo polinomial. Eso es mucho trabajo.
Pero en realidad hay un detalle mágico en todo esto…
Problemas NP-completos
De entre todos los problemas NP, los que podemos comprobar si algo es solución en tiempo polinómico pero no sabemos si podemos resolverlos en tiempo polinómico o no, hay unos que pertenecen a una clase especial, los NP-completos.
Un problema NP es NP-completo si por un lado es NP, evidentemente, y además si cualquier problema NP se puede traducir, (el término técnico es reducir) a ese problema NP concreto.
La sorpresa llegó en la década de los 70 del pasado siglo cuando se demostraron unos teoremas que establecían la existencia de estos problemas NP-completos. Demostraron que cualquier problema NP se podía reducir o traducir, como prefieras a un problema NP-completo y demostraron que los problemas NP-completos eran todos equivalentes entre sí.
Nota: Aquí tenéis el primer artículo sobre este tipo de problemas de 1971 por Stephen A. Cook: The complexity of theorem-proving procedures.
Dado que cualquier problema NP se puede reducir a un problema NP-completo y todos los completos son equivalentes resulta que:
1.- Si alguien demuestra que un problema NP-completo no admite un algoritmo que lo resuelva en tiempo polinomial habrá demostrado que P es distinto de NP.
2.- Si alguien demuestra que un problema NP-completo se puede resolver con un algoritmo en tiempo polinomial, es decir, que ese problema en realidad es P, habrá demostrado que P es igual a NP.
Si demuestras lo primero dirígete al Instituto Clay y diles que has resuelto uno de los Problemas del Milenio. Ganarás un millón de dólares, la fama y la inmortalidad en el universo de las matemáticas.
Si demuestras que P=NP tendrás acceso a cualquier sistema informático, a cualquier tarjeta de crédito, a cualquier dato que quieras, a cualquier cuenta bancaria, a cualquier información. Eso es porque el sistema de encriptación que tenemos en la actualidad se fundamenta en la creencia de que resolver es más difícil que comprobar. Las claves son números enormes que hay que descomponer en números primos. Más o menos, no sabemos si ese problema se podría hacer en tiempo polinomial pero actualmente no hay algoritmo que lo consiga. Sin embargo, si conoces los números primos grandes es fácil multiplicarlos para ver si reproducen la clave. Basta multiplicarlos y listo.
Pero ojo, no vayas al Instituto Clay, no se lo digas a nadie porque lo más seguro es que te quiten de la vista. Es más barato matarte que cambiar todo el chiringuito que tenemos montado.
Nos seguimos leyendo…
Cuentos Cuánticos 
Jeje qué buena verdad el último párrafo 🙂
He solucionado el problema P vs NP gracias a la excelente explicacion de los tres chanchitos… Gracias
Me gustó su explicación del cálculo de 2 a la 64 mediante la historia creada del ajedrez. Excelente!!
Aprovecharía si puede comentar sobre el Método de chubanov para la programación lineal, si no, no hay problema.
Gracias!
A ver, es muy facil:
P = NP
N = P/P
N = 1
Denme mi millón de dolares
Solo me faltaba añadir que mí teoría se basa en una red multifamiliar de tableros , sustentada en pruebas experimentales con toda clase de tableros desde N igual a 4 a N igual infinito. Verificado hasta un N razonable que genera una familia en especial. Luego mí algoritmo de pn se transformó en p. Que existen otros algoritmos es cierto que también son p y dan solución inmediata
Bueno encontrar algoritmos que resuelvan una solución en especial para todos los tableros N existe . Hoy en día esos logaritmos representan los p porque lo hacen en segundos. Lo que no se ha hallado aquel polinomio que resuelva todas los tableros para un N dado ,es decir, si me dicen hallar todas las soluciones para N igual a 27 en tiempo polinomio o razonable no existe uno ..
Con esto queda demostrado que podemos hacer que pn se vuelva p cuando hallamos una ecuación que lo resuelve en segundos. Para todas las soluciones restantes tendrán que crearse miles y millones de p y el problema pn se vuelve p. Lo digo porque hoy en día sin computadora alguna he hallado cientos de distribuciones N 1000 y yo diría que hasta miles que pueden convertirse en millones
Todo problema consta de tres partes :
Una hipótesis
Unrazonamiento deductivo y riguroso
Y una tesis que es la solución del problema.
Si la Hipótesis se sustituye por un Axioma el problema se convierte en teorema.
Por más que he indagado no he encontrado un enunciado del problema, que se puede plantear en vez de con una hipótesis con una pregunta muy concreta exponiendo lo que se busca y dando unos datos precisos
Hola envio mi posible solucion del problema P=NP para que la analicen
Sea el A {>1, 100, 200, < 300}2 = b2 + (2b)a + a2 + c2 + (2c)b + (2c)2
Si se programa una computadora con estas ecuaciones fácilmente las puede resolver
Son mas ecuaciones de conjuntos de numeros
saludos
Pingback: Órbita Laika, La Nueva Generación – ¿Quién maneja mi barca? – Primera sección | Cuentos Cuánticos
Cuándo se habla de resolverlo «en poco tiempo», en qué rango de tiempo debe estar la solución?
Tiempo «razonable», es decir, en tiempo polinómico.
Yo me planteo relacionar esto con el problema de la parada. Supongamos el problema del viajante(problema np). Sabemos que por ejemplo en el caso de n=2,n=3(para algunos «n razonables») tenemos respuestas en «tiempo razonable»:no se si se podrá hacer esto pero hasta ciertos n(no para todo n sino P=NP) tal vez podemos formular un problema equivalente que nos de una respuesta en tiempo polinómico. La pregunta sería(y aquí la relación con el problema de la parada): si para un n podemos determinar un algoritmo que nos de una respuesta de un np-completo en tiempo polinómico, para el siguiente n+1 ¿existirá dicho algoritmo? (igual que determinar en el problema de la parada si la máquina para o no para, en este caso es ¿existe o no existe dicho algoritmo para el siguiente n?). Igual que no existe manera de comprobar que todos los programas del mundo terminan(que creo que es lo esencial en el problema de la parada), yo creo que hay n en el np completo que probablemente se puedan demostrar que no son resolvibles en tiempo polinómico(igual me equivoco pero si uno se fuera por este camino una posible vía de ataque sería buscar un truco a lo «Turing» creo yo).
Hola, buenas…Me llamo Maximilian. Aprovecho la campaña de Bitácoras para pasar por aquí y dejarte mi voto en tu categoría. Y si tuvieras una casilla libre en Arte y Cultura para mi blog (hazmepoeta.com) sería genial. Muchísimas gracias por adelantado, y suerte!!
En programación es evidente que P es diferente a NP. Se manifiesta con la máxima: «Hacer software a prueba de tontos» y su correspondiente ley de Murphy: «Es inútil hacer cualquier cosa a prueba de tontos, porque los tontos son muy ingeniosos.»
Parece que la factrización no es un problema NP-completo; de otra forma, con un algoritmo de Shor, podríamos resolver eficientemente todos los problemas en NP. Por lo tanto, no creo que aciertas con eso que dices de «si demuestras que P=NP tendrás acceso a cualquier sistema informático».
Por otro lado, es cierto lo que decís más abajo. La computación cuántica tampoco resuelve los NP-completos. Hay mucha investigación interesante relacionada con este asunto. Pero también hay mucho alucinao con esto de los ordenadores cuánticos.
Más allá de la terminología técnica que podamos utilizar lo que la conjetura plantea básicamente es si la complejidad puede siempre ser expresada de forma simple.
Ahora bien, esta hipótesis no sólo afecta al ámbito computacional, sino que debido a su indudable trasfondo matemático potencialmente podría ser aplicada al universo entero (como ha indicado el autor/es del post), siempre que veamos éste como si fuera un sistema de intercambio de información. Es decir, una especie de simulación virtual.
Con esta idea en mente podemos hacer varias objeciones al argumento o a la formulación de la propia conjetura. La primera sería la independencia con respecto al tiempo que parece tener el Universo, en el sentido de que poco o mucho tiempo sería un argumento o un pensamiento irrelevante. Casi egocéntrico. La segunda sería el problema de la parada, aún más irrelevante si cabe si pensamos en el Universo como un sistema en perpetuo movimiento, una especie de referencia circular. Algo sin principio ni final.
La tercera sería la irrelevancia con respecto a lo que puede ser o no ser computable. Bien podría ser que la conjetura tuviera solución, pero que no pudiéramos computarla; es decir, que no pudiéramos desprendernos del «dichoso» bucle del infinito. Por ej., la recta real no es computable, pero ello no impide que pueda existir un algoritmo o razón lógica dentro de ella. De acuerdo con la Conjetura de Riemann este algoritmo seguiría un criterio de densidad. Al margen de esto ciertas «estructuras» matemáticas no pueden ser simuladas en ordenador. El ejemplo más claro sería una hiper-esfera, o una esfera tetra-dimensional.
De todas maneras y aunque no se pudiera ofrecer una solución matemática al respecto (un algoritmo global y acotado en el tiempo o en sus términos) lo que es indudable es que el Universo ya ha resuelto esta cuestión afirmativamente. Las leyes de gravitación universal así como las leyes planetarias son una solución lineal o polinómica versus el crecimiento exponencial o dimensional. La existencia de la constante de gravitación universal (o de todas las constantes universales), así como la alineación de la intensidad gravitatoria de los planetas en relación al Sol así lo demuestran.
En conclusión, la conjetura P vs NP podría ser cierta y no serlo al mismo tiempo. Todo depende de la consideración del tiempo.
O tal vez el universo haya descubierto otras formas de computación para las que estas clases de complejidad simplemente se quedan cortas. Tal vez haya sido capaz de encontrar la forma de hacer computación en «maquinas no deterministas».
Estas cosas me cuestan muchísimo, hay que estar bien atento y concentrado para no perderse algo.
Hay una cosa que no acabo de entender. Dices que demostrando que un solo problema NP-completo sea P entonces demuestras P=NP. Siguiendo la argumentación lógica donde dices que todo problema NP se puede reducir a un NP-completo y, sabiendo que todo problema P es NP, se deduce que un problema P (puesto que es NP) se puede reducir a un problema NP-completo, no?. Por lo tanto cualquier problema P es también NP-completo y por tanto acabas de demostrar que P=NP. Puesto que has encontrado un NP-completo que es P, aquel que obtienes de reducir un problema P (que es NP) a un problema NP-completo.
Estoy seguro que hay algún fallo en mi lógica, pero no veo cual…
HELP!!
Se puede reducir en este contexto se puede entender del siguiente modo:
En un algortimo o programa para un problema (NP-completo) hay subrutinas que resuelven otros problemas (NP). Resolviendo el NP-completo en tiempo polinomial resuelves todos los que contenga en tiempo polinomial. Evidentemente, contendrá también a problemas P pero esos ya sabemos que se pueden resolver en tiempo polinomial. Lo interesante es comprobar todos los que quedan, saber si son P o no lo son.
¿Mejor ahora?
Una duda en donde no me doy cuenta dónde está el error de razonamiento.
En la sección «Todos los problemas P son NP» (que copio con ediciones adicionales entre paréntesis rectos y texto entre asteriscos para la parte que me genera la duda):
«Todos los problemas P son NP
¡Evidentemente!, habrás pensado. Si los problemas P son aquellos para los que tenemos un algoritmo que los resuelve en tiempo razonable (polinómico) es lógico que [conocemos un algoritmo con el que] podamos comprobar si algo es solución en tiempo razonable, el propio algoritmo que lo resuelve es un ejemplo. Tú nos das una solución, nosotros corremos nuestro algoritmo y nos da una respuesta en un tiempo razonable, *comprobamos si la solución del problema es la que tú nos has dado o no lo es*. Por tanto hemos comprobado si algo es solución en tiempo polinómico.
Pero dado que los problemas para los que podemos comprobar si algo es solución [en tiempo razonable (polinómico)] son los problemas NP entonces todos los problemas P son NP por derecho propio.»
Se está suponiendo que la solución es única y que se puede comprobar que «la solución del problema es la que tú nos has dado o no lo es» en tiempo polinómico.
Por ser el problema de tipo P, el algoritmo que resuelve el problema nos da la solución en tiempo razonable (polinómico) pero no veo la relación entre el algoritmo que lo resuelve y el que comprueba que la solución dada por el algoritmo sea igual a la dada
A ver si esto ayuda:
Tengo un problema para el que he diseñado un
Algoritmo que resuelve en tiempo polinomial.
¿Podemos hacer un algoritmo que compruebe si algo es solución en tiempo polinomial? Pues sí, solo tenemos que hacer lo siguiente
Algoritmo de comprobación = (Algortimo que resuelve + una línea que compare su resultado con el input que le proporcionas)
Es claro que eso se hará en tiempo polinomial ya que solo hemos añadido una orden de comparar y eso es bastante rápido.
Pero ahí está mi duda: para mí la orden para comparar es un problema que se debe resolver con un algoritmo ¿por qué se puede asegurar que la línea agregada para comparar se puede resolver en tiempo polinómico?
A no ser que se diga que es por la definición de tiempo asociado a un algoritmo:
«el tiempo asociado a un algoritmo es el número de operaciones que ha de realizar para resolver un problema.»
y la línea agregada para comparar se cuente como una sola operación, lo que cumple con la definición de tiempo polinómico: que se resuelve en tiempo de la forma n^k, con k=0 (pero «siendo k un número positivo» y 0 no está entre los positivos estrictamente…)
Pero no me convence.
No hay que redefinir nada. Comprobar es algo que se hace en tiempo lineal. Tú le das una entrada (la supuesta solución) eso se almacena en memoria como una cadena de 1 y 0. El algoritmo genera la solución, en tiempo polinómico y saca un resultado en forma de cadena de 1 y 0’s. Ahora lo único que hay que hacer es comprobar que las dos cadenas son iguales posición a posición. Eso es todo.
Con la idea de tener cadenas de 1 y 0’s y compararlas queda claro
Muchas Gracias
Lo único que me confunde siempre en esta disquisición es demostrar un negativo. Hasta donde yo se, que es prácticamente nada, en lógica se puede demostrar que algo EXISTE, pero demostrar que no existen los cisnes negros o los algoritmos que resuelven un problema, yo tenía entendido que era una labor imposible para la lógica, Y hasta donde tengo entendido, la matemática sigue siempre un razonamiento lógico. ¿me aclara alguien cómo se demuestra en matemáticas que algo no existe?
Suele hacerse por contradicción: supones que ese algo existe, y si llegas a una contradicción con los axiomas o teoremas que tienes por hipótesis entonces ese algo no existe(en algunas pruebas básicas de geometría puede verse el método).
En efecto, las demostraciones de inexistencia son complicadas, filosóficamente incómodas por eso de que hay que encontrar una contradicción y no siempre es evidente, pero existen. Y es el meollo de este problema, porque hay que demostrar que un problema NP-completo no se puede resolver en tiempo polinomial.
Pero uno puede pensar en teoremas chorra de inexistencia que son muy fáciles de aceptar. Por ejemplo:
Teorema: Ningún número primo acabará en 0, 2, o 5.
Lo sé es muy chorra pero es un teorema de inexistencia con todas las de la ley.
Además muchos teoremas se pueden establecer como teoremas de inexistencia.
Teorema: No existe ninguna función continua definida en un intervalo cerrado [a,b] tal que f(a) y f(b) sean de distinto signo para la que no exista al menos un valor intermedio c en dicho intervalo que cumpla que f(c)=0.
No suele haber problemas con los teoremas de inexistencia hasta que la hay como en el caso P/NP
Pingback: ¿Comprobar o resolver? Esa es la cuesti&...
¿Se debe demostrar que P=NP para que «te quiten de la vista»?
Si se tuvieran computadoras cuánticas de verdad, implementando el algoritmo de Shor para números del tamaño de las claves usadas en la actualidad (o superiores) (no las primeras demostraciones que factorizan 15) ¿no bastaría?
Queda el algoritmo de encriptación que usa logaritmo discreto.
Según la página de la wikipedia
Logaritmo discreto
https://es.wikipedia.org/wiki/Logaritmo_discreto
Shor también hizo un algoritmo cuántico eficiente para el Logaritmo discreto, por lo que sistemas criptográficos basados en la dificultad del problema podrían ser vulnerables si se tuviera una computadora cuántica de verdad
Cierto. Ahí mismo dicen que el Criptosistema de McEliece está basado en un problema tipo NP y que el algoritmo de Shor no funciona con el.
Esto quiere decir que la computación cuántica logra reducir ciertos problemas NP pero no los problemas NP-Completos.
En efecto, la computación cuántica establece nuevas clases de complejidad y se sabe que hay ciertos problemas que ahora no sabemos resolver en tiempo polinomial que podrán ser resueltos en tiempo razonable con computadoras cuánticas. Pero eso no resuelve el problema, porque como ha dicho geextra los NP-completos se quedan fuera del juego, así que hemos de seguir estudiando.
No hace falta esperar a la computación cuántica. Con Técnicas bio-inspiradas (Técnicamente se conocen como metaheurísticas (Talbi, 2009) y comprenden diversos algoritmos de la computación evolutiva (De Jong, 2006), la computación inmune (Dasgupta y Niño, 2009), la inteligencia de enjambres (Bonabeau, Dorigo y Theraulaz, 1999; Dorigo y Stützle, 2004), la computación neuronal (Forbes, 2004) y la computación con membranas (Pǎun, 2005; 2006). para resolver problemas complejos (NP y NP-completos) relacionados con optimización, búsqueda, programación de rutas, asignación de espacios, descubrimiento de patrones y toma de decisiones.
Maldonado y Gómez Cruz, en 2009 aproximan a la idea de que la vida misma es un problema NP
Extraido de: http://www.carlosmaldonado.org/articulos/bi112web.pdf
Los dos últimos párrafos, sin duda, alborotan la imaginación conspiretas, por ejemplo:
Basados en que el anonimato en internet es prácticamente imposible, aquel que encuentre una respuesta afirmativa se enfrentará a un problema NP. Esto, porque el «afortunado» debe tratar de asegurar su anonimato y al mismo tiempo asegurar su identidad; todo con el fin de no ser perseguido mientras consigue la fama. ¡Gran dilema!
Esto lleva a pensar en que en el planteamiento de los problemas NP siempre está el dilema en forma subyacente. Y como un dilema es un ciclo o bucle infinito (computacionalmente hablando), tomará tiempo infinito concluir dicha tarea.
Por lo tanto, la diferencia subyacente entre P y NP es el dilema; concluyendo así que son problemas diferentes.
Así que la respuesta es negativa y el pobre afortunado se salva de una vida de locura.
Fin de la fábula.