P se refiere al conjunto de problemas que se pueden resolver en tiempo polinómico. Esto significa que si tenemos un problema (por ejemplo, ordenar una lista de números), y el tamaño de los datos de entrada es [matemática] n [/ matemática], entonces el tiempo que se tarda en resolver el problema puede expresarse como una función polinómica en [matemáticas] n [/ matemáticas].
Informalmente, digamos que son problemas que pueden resolverse con bastante rapidez (en comparación con el tiempo exponencial).
Hablando en términos generales, NP es el conjunto de problemas que pueden verificarse rápidamente como verdaderos si ya conoce la respuesta, pero tomará una cantidad de tiempo poco práctica para resolver en las computadoras clásicas.
- Regresión logística, función softmax. ¿Por qué utiliza la función exponencial en la función sigmoidea?
- Cómo entender el concepto matemático de la máquina de turing
- ¿Por qué la informática teórica es tan seca en los trabajos, a excepción de la academia? Aunque todas las empresas se enfrentan a desafíos, no hay una guerra muy reñida contra problemas difíciles, y las personas tienden a elegir la forma fácil de resolver cada problema.
- ¿Cómo se llega a una estructura de datos totalmente nueva?
- ¿Qué oración en el lenguaje de la aritmética de Peano es equivalente a decir que un programa dado se detendrá?
El problema P = NP básicamente pregunta si existen algoritmos que puedan ejecutarse en tiempo polinómico para problemas de NP .
