Felicidad criptográfica

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?

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

8 Comentarios

  1. 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 nada.

    Tercero, desde el punto de viasta algorítmico, actualmente nos defendemos bien independientemente de la solución a este problema: experimentalmente los casos difíciles de los problemas NP-completos suelen ser escasos.

    Publica una respuesta
  2. 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 …

    Publica una respuesta
  3. 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: comercio, seguridad militar, seguridad corporativa, transacciones de todo tipo, etc. serán susceptibles de intromisión. Esto no es un teorema de Godel, de escasa aplicación práctica… Ni un teorema de Turing… P!=NP es un punto y aparte. No obstanet, NP=P sería la revolución total aunque dudo que una demostración mostrara también cómo transformar los NP en P… Aunque sería cuestión de tiempo que alguien o algo lo demostrara.

    Publica una respuesta
  4. 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 aparece en este paper de Impagliazzo (autor que por casualidad está saliendo mucho en mis comentarios pero al que no tengo el gusto de conocer): “A personal view of average case complexity”. Hay un escenario posible Heuristica que puede ser de tu interés. De hecho parte del último cambio del paper del autor de la demostración entiendo que intenta contestar a la pregunta sobre que consecuencias tendría la demostración para el caso medio de los problemas NP-completos. Se lo han preguntado.
    –el que en la práctica en muchas aplicaciones los casos difíciles no aparecen con frecuencia es un hecho (experimental no probado). Un ejemplo, quizás no adecuado pues es un problema que está en P: se sabe que hay problemas de programación lineal que con el algorimto del Simplex son exponenciales, pero no aparecen mucho en la práctica y este algoritmo se sigue utilizando (aunque hay otros que son polinómicos en caso peor).

    2. Una matización a mi comentario anterior: cuando digo “Segundo, es posible que los problemas más interesantes tengan demostraciones tan largas que P=NP no cambie nada”, quiero decir que el tamaño de la demostración mínima posible con respecto al de la proposición sea exponencial.

    3. No contesto a más preguntas en ese tono.

    Publica una respuesta
  5. 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, cuando el número de variables y ecuaciones es muy grande, son métodos como el punto interior los que se usan.

    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.

    Publica una respuesta
  6. 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)

    Publica una respuesta
  7. 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.

    Publica una respuesta
  8. 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 por e-mail) ¡y listo!, todo el mundo sabrá que dispones (sino de un algoritmo), sí de un medio para resolver el problema de forma eficiente.

    Con aplicar directamente el problema del viajante (con un número muy grande de nodos) creo que sería suficiente, existen métodos de aproximación, ¡pero tú siempre mejorarías la solución! (si la hay).

    ¡Suerte!

    PD: y no te olvides de darnos acceso a tus resultados ¿eh?.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: P ≠ NP Criptógrafos felices. P = NP La mayor revolución en las matemáticas…
  2. Tweets that mention Felicidad criptográfica | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos, redes sociales web. redes sociales web said: #hispaciencia Felicidad criptográfica: P…

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.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *