P = NP enigma resuelto? Científico indio propone prueba por Bipin Shah

Nueva Delhi: Un científico llamado Vinay Deolalikar en Hewlett-Packard (HP) laboratorios en California ha llegado con una posible prueba de la famosa P = problema NP en matemáticas. La hazaña puede hacerle ganar $ 1 millón (Rs. 4,6 millones de rupias) para la solución de uno de los siete Matemáticas Clay Institute Problemas del Milenio, informa Samanth Subramanian de menta.

En un correo electrónico a sus colegas investigadores Deolalikar escribió que tenía hecho varios intentos fallidos intentan otras combinaciones de ideas antes de empezar este trabajo.

Antes de aceptar por la comunidad matemática, el documento tiene que ser publicado en una importante revista arbitrada. Tiene que ser aceptado por la comunidad matemática dentro de los dos años de la publicación de Deolalikar para recoger su premio Clay.

Según Stephen Cook, quien ha escrito la descripción oficial de la P = problema NP para el Instituto Clay, Deolalikar ha hecho una afirmación muy seria haber resuelto P vs NP.

La P = problema NP es un meta-problema con especial relevancia con la informática. El 'P' en esta ecuación se refiere a una clase de problemas; Si el tiempo necesario para resolver un problema no crece exponencialmente con los datos dados, el problema es un problema de tipo-P. Un problema NP, por otro lado, es uno de los que se puede comprobar si una solución propuesta es realmente una solución en un plazo razonable.

La P = NP preguntas problema si un problema NP es lo mismo que un problema P. En otras palabras, si un problema tiene soluciones que se pueden verificar en tiempo polinómico, entonces puede el problema también puede resolverse en tiempo polinomial?

Desde que el problema se afirmó, de forma independiente, por Cook y Leonid Levin en 1971, los matemáticos han pensado que P no lo hace, de hecho, igual NP - pero se ha encontrado ninguna prueba aceptable de que la desigualdad prueba de

Deolalikar, que pretende demostrar que P no es igual a NP, tiene, en sólo unos pocos días, revuelto considerable entusiasmo entre la comunidad matemática. Prueba de

Deolalikar será el segundo de los siete problemas del milenio que han caído en los últimos años, si se publica y se encuentra el "aceptación general" que la arcilla