Diferencia entre revisiones de «P (clase de complejidad)»

En [[complejidad computacional|teoría de la complejidad]], la [[clase de complejidad]] de los [[problema de decisión|problemas de decisión]] que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una [[máquina de Turing]] determinista es llamada '''P'''. Cuando se trata de una máquina de Turing no-determinista, la clase sees llamallamada [[NP (clase de complejidad)|NP]]. Una de las preguntas abiertas más importantes en la actualidad es descubrir si estas clases son diferentes o no. El [[Clay Mathematics Institute]] ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.