Básicamente son cosas completamente diferentes, aunque están relacionadas porque ambas son formas que a veces hacen que los problemas “difíciles de calcular” sean un poco más fáciles.
Considere el siguiente problema: dada una lista de ciudades que desea visitar, suponiendo que sea fácil encontrar la tarifa aérea más barata entre dos de ellas, averigüe en qué orden visitar las ciudades que tiene la tarifa total más barata mientras visita cada ciudad en menos una vez. (Las personas familiarizadas con la teoría de la complejidad lo reconocerán como el problema del Vendedor Viajero). Un algoritmo de aproximación para esto sería un algoritmo que se garantiza que le dará un conjunto de boletos de avión que podrían no ser los más baratos, pero no serán más que ( por ejemplo) 5% más caro que la opción más barata. Dicho esto, si ejecuta el algoritmo de aproximación varias veces para las mismas ciudades, le dará el mismo resultado cada vez, y si eso no es lo más barato, no tiene suerte. Un algoritmo no determinista no le dará el mismo resultado cada vez, pero si enumera todos los resultados posibles que podría darle, uno de ellos sería el conjunto más barato.
- ¿Es un cierre una función o el entorno en el que se definió dicha función?
- Como estudiante de secundaria, ¿cómo puedo aprender Matemáticas para la informática?
- ¿Cuál es el concepto de anti-cadenas en la teoría de la complejidad computacional?
- ¿Qué pasaría si alguien prueba P = NP o P! = NP?
- Si el universo es una simulación, ¿no estaría sujeto al problema de detención?
