¿Una prueba de que P≠NP?

El ingeniero y matemático Vinay Deolalikar (HP Labs) ha anunciado que ha demostrado que P ≠ NP.

La teoría de complejidad computacional es parte de la teoría de la computación que analiza los recursos utilizados durante el cálculo asociado a la resolución de un problema.  Los recursos más estudiados suelen ser el tiempo de ejecución del algoritmo y el espacio -memoria- utilizado por el ordenador durante el proceso.

Un problema de decisión -cuestión en algún sistema formal con una respuesta sí o no- es:

  1. de tipo P  si puede resolverse en una máquina de Turing determinista -por ejemplo, un ordenador- en tiempo polinómico; de otro modo, la relación entre el tamaño del problema y el tiempo de ejecución es polinómica;
  2. de tipo NP si puede resolverse en una máquina de Turing no determinista en tiempo polinómico, es decir, al contrario que las de tipo P, no puede resolverse en un ordenador en un tiempo razonable (con los algoritmos conocidos).

La pregunta ¿P = NP? es uno de los famosos Problemas del Milenio premiados con un millón de dólares por el Clay Mathematics Institute.

Parece que la demostración dada por Vinay Deolalikar -más de 100 páginas de física estadística y varias áreas de las matemáticas-  tiene buen aspecto para los especialistas en la materia, aunque quedan aún muchas comprobaciones por realizar…  

Más información:

1 Response to “¿Una prueba de que P≠NP?”



  1. 1 Arte TSP | :: ZTFNews.org Trackback en 27/10/2013 en 05:52

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




UPV/EHU
Premio Mejor Post en la VII Edición del Carnaval de Humanidades..Gracias a Marta Macho
Premio a la Mejor Entrada de la Edición 4.1231 del Carnaval de Matemáticas.

Sigue nuestro Twitter ...

Egutegia | Calendario

agosto 2010
L M X J V S D
« jul   sep »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Estatistika | Estadística

  • 1,011,571 sarrerak | visitas

The scientific cartoonist

Viñetas
rss

RSS UPV/EHU Albisteak

  • Ha ocurrido un error; probablemente el feed está caído. Inténtalo de nuevo más tarde.

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 827 seguidores

%d personas les gusta esto: