En programación de computadoras , un algoritmo no determinista es un algoritmo que, incluso para la misma entrada, puede exhibir diferentes comportamientos en diferentes ejecuciones, a diferencia de un algoritmo determinista . Hay varias formas en que un algoritmo puede comportarse de manera diferente de una ejecución a otra. Un algoritmo concurrente puede funcionar de manera diferente en diferentes ejecuciones debido a una condición de carrera . El comportamiento de un algoritmo probabilístico depende de un generador de números aleatorios . Un algoritmo que resuelve un problema en tiempo polinómico no determinista puede ejecutarse en tiempo polinómico o exponencial dependiendo de las elecciones que haga durante la ejecución. Los algoritmos no deterministas se utilizan a menudo para encontrar una aproximación a una solución, cuando la solución exacta sería demasiado costosa de obtener utilizando una determinista.
La noción fue introducida por Robert W. Floyd en 1967. [1]
A menudo, en teoría computacional , el término "algoritmo" se refiere a un algoritmo determinista . Un algoritmo no determinista se diferencia de su contraparte determinista más familiar en su capacidad para llegar a resultados utilizando varias rutas. Si un algoritmo determinista representa un camino único desde una entrada a un resultado, un algoritmo no determinista representa un camino único que deriva de muchos caminos, algunos de los cuales pueden llegar a la misma salida y otros pueden llegar a salidas únicas. Esta propiedad se captura matemáticamente en modelos de computación "no deterministas" , como el autómata finito no determinista . En algunos escenarios, se permite que todas las rutas posibles se ejecuten simultáneamente.
En el diseño de algoritmos, los algoritmos no deterministas se utilizan a menudo cuando el problema resuelto por el algoritmo permite inherentemente múltiples resultados (o cuando hay un único resultado con múltiples caminos por los cuales se puede descubrir el resultado, cada uno de ellos igualmente preferible). Fundamentalmente, todos los resultados que produce el algoritmo no determinista son válidos, independientemente de las elecciones que haga el algoritmo mientras se ejecuta.
En la teoría de la complejidad computacional , los algoritmos no deterministas son aquellos que, en cada paso posible, pueden permitir múltiples continuaciones (imagine a una persona caminando por un sendero en un bosque y, cada vez que da un paso más, debe elegir qué bifurcación en el camino desea tomar). Estos algoritmos no llegan a una solución para todos los caminos computacionales posibles; sin embargo, se garantiza que llegarán a una solución correcta para algún camino (es decir, la persona que camina por el bosque sólo puede encontrar su cabaña si elige alguna combinación de caminos "correctos"). Las elecciones pueden interpretarse como conjeturas en un proceso de búsqueda .
Se puede conceptualizar una gran cantidad de problemas mediante algoritmos no deterministas, incluida la cuestión no resuelta más famosa de la teoría de la computación, P vs NP .
Una forma de simular un algoritmo no determinista N utilizando un algoritmo determinista D es tratar conjuntos de estados de N como estados de D. Esto significa que D rastrea simultáneamente todas las rutas de ejecución posibles de N (consulte la construcción del conjunto de poderes para conocer esta técnica en uso para autómatas finitos ).
Otra es la aleatorización , que consiste en dejar que todas las opciones sean determinadas por un generador de números aleatorios . El resultado se denomina algoritmo determinista probabilístico .