Significa que cada problema NP puede convertirse en el problema NP completo en tiempo polinómico, es decir, a medida que el “tamaño” del problema aumenta, el tiempo de ejecución aumenta en alguna función polinómica del tamaño.
OK, entonces, ¿qué significa NP? Significa que si tiene una solución candidata , puede verificar que es una solución en tiempo polinómico. N significa no determinista. Este término surge porque el solucionador es una máquina de Turing no determinista, adivina o intuye la respuesta, solo queremos validarla.
Muchos problemas abiertos muy difíciles se pueden probar en tiempo polinómico. Del mismo modo, si hay un contraejemplo de una conjetura famosa que se propone, a menudo se puede probar en tiempo polinómico. Es por eso que la mayoría de la gente cree que P [math] \ neq [/ math] NP. ¡Parece increíble si una máquina de Turing pudiera demostrar teoremas difíciles!
- ¿Qué es una función de punto fijo y cuándo son útiles?
- ¿Qué es una mónada?
- ¿Cómo convertiría estos datos matemáticos a la función por partes?
- ¿Es posible tener una máquina de Turing que sea capaz de construir otra máquina de Turing (diferente) a partir de bits puramente aleatorios?
- Cómo escribir un programa en C para verificar si para cualquier triplete entero (x, y, z) y otro entero n, [matemática] n ^ x + n ^ y = n ^ z [/ matemática] ocurre para (a, b) siendo la entrada donde [matemáticas] a \ leq n \ leq b [/ matemáticas]
