P ≠ NP
Criptógrafos felices.P = NP
La mayor revolución en las matemáticas desde que se inventaron los números.
Interesante comentario de gromenawer (esto es sólo un extracto; el comentario entero podéis verlo aquí) en Menéame. La verdad es que Vinay Deolalikar ha causado un gran revuelo con su trabajo. ¿Qué pensáis vosotros sobre este comentario y sobre las implicaciones del trabajo de Deolalikar?
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.
Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.
Y si los símbolos < y > te dan problemas al escribir en LaTeX, te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.
Tienes un 20% de descuento y envío gratis en toda la web de La Tostadora con al menos dos artículos. Usa el código GAUSSIANOS entrando con el enlace de la imagen.
Y usando el código REBAJAS tienes un 30% de descuento hasta el 8 de agosto con al menos 3 artículos.
Si quieres recibir los artículos de Gaussianos en tu mail haz click en la imagen.
Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.
Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.
Información Bitacoras.com…
Valora en Bitacoras.com: P ≠ NP Criptógrafos felices. P = NP La mayor revolución en las matemáticas desde que se inventaron los números. Interesante comentario de gromenawer (esto es sólo un extracto; el comentario entero podéis verlo aquí) ……
[…] This post was mentioned on Twitter by gaussianos, redes sociales web. redes sociales web said: #hispaciencia Felicidad criptográfica: P NP Criptógrafos felices. P = NP La mayor revolución en las matemáticas d… http://bit.ly/bnbr90 […]
P!=NP. Criptografos felices y un gran ahorro de tiempo de investigador (todos los que intentan encontrar algoritmos eficientes para los casos difíciles de problemas NP-completos). «P=Np. La mayor revolución en las matemáticas desde que se inventaron los números». Hmmm…esto es un mantra que se repite mucho y es exagerado. Este problema tiene un interés básicamente teórico. Sobre sus consecuencias prácticas: Primero dependerá del grado del polinomio que exprese la complejidad del algoritmo. Si es lineal puede. Si es O(n^1000) o incluso O(n^4), pues no. Segundo, es posible que los problemas más interesantes tengan demostraciones tan largas que P=NP no cambie… Lee más »
Usted son mucho pero mucho mas conocedores que el tema, así que acudo a usted para que le den una mirada a este artículo en el que exponen algunos problemas con la demostración http://3.ly/qCP5
Saludos …
Espero que los Gaussianos expliquen la importancia de la demostración de P distinto a NP para evitar comentarios como el de proanouiq que se nota que no están muy enterados de su importancia. El tema es complejo, sí… Como ingeniero de teleco especializado en Criptografía, te aseguro proanouiq, que la demostración es una revolución. ¿Los NP son escasos? Ja! Coge una clasificación y aprende que los NP son abundantes y, especialmente, útiles en la práctica. Conforme la seguridad de las telecomunicaciones se vea cada vez más comprometida, las técnicas de cifrado -especialmente las relativas a la computación cuántica- serán fundamentales:… Lee más »
1. Agus: no digo que no sea una revolución; pero insisto en que más teorica que práctica. a que te refieres con los casos NP ? –NP es una clase de complejidad de problemas no de casos; –Algunos problemas en NP tienen determinadas propiedades y entonces son NP-completos. –Los casos de los problemas NP-completos pueden ser fáciles o difíciles (una explicación muy clara de este tema en http://en.wikipedia.org/wiki/Average-case_complexity) — en criptografía se requiere que el caso medio (aquel que saldria de una selección aleatoria eficiente) sea difícil. Un buen survey sobre las consecuencias del tema P Np para la criptografia… Lee más »
Uhm… @proaonuiq, en mi opinión, en el caso de ser P=NP, un buen puñado de gente lista se lanzaría a buscar una solución P a algún NP-completo y una vez encontrado P1, otro buscaría el P2 más óptimo y otro el siguiente P3, … hay muchos problemas como TSP que admiten aproximaciones y optimizaciones indeterminísticas, pero otros como SAT no y son en éstos casos en los que un algoritmo eficiente sería útil en la práctica. Creo que pasa algo similar a LP, el método Simplex es exponencial en la teoría, pero funciona «polinómicamente» bien en la práctica, sin embargo,… Lee más »
Muy buena apreciación, josejuan:
«Aunque también pienso (desde mi ignorancia) que a P vs NP se le da mucho^2^2^2 más bombo del que merece y se le equipara (incorrectamente a mi pobre juicio) con otros GRANDES problemas.»
estoy completamente de acuerdo (siempre que se valore el problema puramente por su interés matemático)
Mi nombre es Diego, he encontrado una hermosa forma de unificar en un mismo tipo especial de grafo los caminos eulerianos y hamiltonianos. Ello me ha conducido también a un único algoritmo que resolvería ambos bajo el punto de vista de ser dos casos particulares de este tipo especial de grafo general.
El algoritmo es de coste cúbico. Os pido consejo para saber donde llevar mi trabajo a revisión
sin riesgo a que me roben la paternidad de mi método de resolución, y la posible demostración de P=NP definitiva.
Un Saludo afectuoso.
WoW! Diego, Grigori Perelmán (ganador de uno de los premios del milenio) publicó su fantástico trabajo en ArXiv. Aunque aún tienes una forma más sencilla de captar la atención de todo el mundo ¡sin tener que publicar nada!. Si realmente puedes determinar en tiempo polinómico (de grado no excesivamente elevado) si un grafo admite un camino hamiltoniano (o euleriano), entonces estás en disposición de resolver problemas que nadie puede resolver en tiempo polinómico. Busca un problema NP-completo que no sea aproximable (ej. SAT) y resuelvelo en tiempo polinomial, da acceso a todo el mundo para proponer su problema (ej. enviándolo… Lee más »