Ir al contenido

Discusión:Clases de complejidad P y NP

Contenido de la página no disponible en otros idiomas.
De Wikipedia, la enciclopedia libre

El texto está incompleto a partir de la línea:

El grafo resultante queda como:

Debe haberse eliminado por error u omitido un gráfico


La parte relativa a los NP-duros es un texto mal traducido y lleno de equívocos. ¿Realmente ahora el problema del viajero es NP-completo? Yo creía que sólo era duro. Creo que hay que hacer revisiones.

A propósito, he publicado un libro con varias respuestas: http://www.trafford.com/07-1729

Quizá debáis arrancar la página 189 de este libro, y ser coherentes con lo que habéis hecho; pues es la parte menos rigurosa y es en ese punto donde se sobreentiende un error clave. El problema sigue abierto, aunque hay muchos más que lo están sin que se sepa y que pueden esclarecerse con ayuda de ese libro.

Intentaré pasarme por esta página a menudo por si surgen dudas; si no, aquí tienen mi correo: jumadaru@gmail.com

Otro punto que quiero citar es que para participar en el concurso del Claymath del milenio hace falta haber publicado durante dos años en una revista de matemáticas específica; pero si la revista no ve las matemáticas en el documento, entonces no publican tu trabajo, así que piensen que el problema no es de matemáticos, sino de informáticos (teóricos). Por tanto, se exige un lenguaje y un compromiso posiblemente distintos.

Aquí expongo la independencia entre P y NP, publicado en el American Open Computer Science Journal. http://rekpub.com/American%20Open%20Computer%20Science%20Journal/Current%20Issue.php

Solucion al dilema ¿P equivalente a NP?

La solucion es que NO. La explicacion tiene que ver con la base primitiva de las matematicas. Los simbolos terminales y la composicion de terminales para formar expresiones. Por ejemplo un "+" seria un simbolo terminal en el espacio matematico definido en el ambito de las operaciones. Ahora imaginemos un "+" como operacion entre imagenes pues es otra idea, aunque compartan la misma simbologia. Antes de que existiera el simbolo "+" que existia, estoy hablando en el plano de la Matematica como ciencia, ni siquiera habia un hueco para el!, surgio de la nada. Se han hecho esfuerzos por intentar desmostrar los elementos atomicos en si mismo, pero a la conclusion que se llego es que puedes agregar mas complejidad a la definicion, mas relaciones pero al final se llega a la conclusion de que algo existe porque se diferencia del resto para el sujeto que lo analiza. Cobra una entidad, un forma, esto implica que existe un hecho, un proceso y un sujeto. Y dos sujetos no son iguales por lo tanto no tienen que estar deacuerdo en el simbolo. Pero una composicion de simbolos tambien puede ser atomica, existe la composicion minima de simbolos atomicos "que tambien es minima y unica". Lo que quiere decir que desde el punto de vista de las Matematicas hay elementos que surgen de la nada y otros que son asociaciones. obvio.

Cuando se dice que si a NP se le introduce un simbolo "magico, surgido de la nada" se puede comprobar que se llega rapidamente a la solucion. Lo que se esta diciendo es que el conjunto del problema y su solucion forman un todo. Un sistema en el cual existen elementos atomicos y elementos compuestos. En la Matematica ha proliferado la composicion de elementos terminales en relacion a las operaciones para hallar la solucion. No en tanto pensar en la solucion como un elemento mas del sistema "magico, o terminal en si mismo". Es logico pensar que la solucion de un problema tiene las mismas propiedades que la teoria de formacion de las propias ecuaciones. Es decir, hereda el concepto de elementos terminales en este caso soluciones terminales y soluciones de composicion. La matematica ha primado el hecho de llegar a las soluciones por composicion pero no quiere decir que no tengan que existir las soluciones terminales. Soluciones a las que no se llegue por ningun proceso discreto. Soluciones "magicas" y por ende geniales. Ejemplo los numeros primos (como proceso). Son numeros surgidos como solucion a la composicion o en si terminales del sistema?. Parecen mas bien terminales, no? Conclusion, por lo anterior. P en relacion con NP no tiene la misma complejidad. Puesto de los simbolos terminales creados tienen que ver con el sistema y su solucion. El proceso seguido y la solucion forman un todo. Forman un trio: algoritmo, finalidad, solucion. Realmente saco la solucion del algoritmo porque esta mas alla de este o "dentro segun se mire" o esta en dos sitios a la vez. Dentro y fuera.

Hanllel


  • ¿Tan sólo 1 millón de dólares por resolver el problema? la relatividad nos enseña cuan pequeñas pueden parecer las recompensas cuando se trata de aportar soluciones que mejorarían ciertos problemas de incalculable precio humano, ecológico, económico, etc...

--eHelper (discusión) 01:31 22 may 2008 (UTC) Si resulta ser P distinto a NP entonces no veo cual sea el aporte además de que todos los investigadores paren de buscar la respuesta a este problema.[responder]


"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 complejidad computacional"

Esa información ya es erronea,la pregunta ya fue respondida hace poco acaba de demostrarse que P no es igual que NP por un matematico, prometo publicar una fuente de un paper en estos dias solo debo conseguirlo.

Pará de mentir che.

Informe de error

[editar]

Al comienzo del texto dice: "La relación entre las clases de complejidad P y NP es una pregunta que aún no se ha podido responder por la teoría de la complejidad computacional."

Pero esa respuesta la dio Vinay Deolalikar en 2010 y dijo que P≠NP.

Saludos. - --190.189.139.247 (discusión) 07:45 6 feb 2016 (UTC)  Trasladado desde Wikipedia:Informes de error por Jembot (discusión) 00:13 12 feb 2016 (UTC)[responder]

Y poco tiempo después la comunidad matemática descartó la demostración de Deolalikar, porque contenía errores que la hacían inviable.