Tipos de sistemas

P vs NP
El pasado 7 de agosto Vinay Deolalikar, quien es un matemático que trabaja para los laboratorios de HP en su cuartel general ubicado en Sillicon Valley asegura tener la respuesta a uno delos llamados problemas del milenio en ciencias de computación. La respuesta a la que llego es que P no es igual a NP. Este problema era considerado uno de los más grandes problemas sin resolver en elcampo de la computación teórica y se ofrecía un millón de dólares a quien encontrara la solución.
La solución de Vinay Deolalikar trabaja conectando ciertas ideas en ciencias de computación y teoríade modelos finitos con ideas en mecánica estadística. La solución demuestra que si ciertos problemas conocidos están en NP estuvieran también en P, entonces esos problemas tendrían propiedadesestadísticas imposibles. Los científicos de computadoras y matemáticos han expresado una variedad de opiniones acerca de esta solución que van desde el optimismo hasta asegurar que esta solución es incorrecta.En pocas palabras este problema plantea la pregunta de si todos los problemas que sus soluciones pueden ser verificadas eficientemente por una computadora, pueden ser también eficientementeresueltos por una computadora. Fue introducido en el año de 1971. El hecho de que se haya resuelto este problema significa un gran paso hacia adelante en el área de la computación y la programación, puesabre la puerta a nuevas preguntas y a plantear, programar, o dejar de intentar programar problemas imposibles de ser resueltos por la computación actual. Este problema se cuestiona si los problemaspueden ser verificados de manera “rápida”. ¿Entonces estas soluciones pueden en si mismas pueden ser computadas de manera rápida? Esta noción teórica de “rapidez” es básicamente el uso de un algoritmo quese ejecuta en tiempo polinomial, a los problemas que pueden proveer una respuesta en tiempo polinomial se es a lo que se le llama “P”. Para algunos problemas no es posible encontrar una solución...