Tabla de contenido:
- Definición: ¿Qué significa el tiempo polinómico no determinista (NP)?
- Techopedia explica el tiempo polinómico no determinista (NP)
Definición: ¿Qué significa el tiempo polinómico no determinista (NP)?
El tiempo polinomial no determinista (NP) es en realidad un marcador utilizado para señalar un conjunto de problemas y límites de la capacidad de ciertos tipos de computación. NP se refiere al conjunto de problemas que una máquina de Turing no determinista puede resolver en tiempo polinómico.
Techopedia explica el tiempo polinómico no determinista (NP)
El tiempo polinomial no determinista se basa en la frase "tiempo polinomial", que se refiere a si un algoritmo puede funcionar dentro de ciertos límites relevantes para la velocidad. El tiempo polinómico surgió como una forma de hablar sobre la viabilidad del trabajo y desarrollo de algoritmos.
Si un problema se encuentra en un tiempo polinómico no determinista, la máquina de Turing no determinista puede primero adivinar la solución y luego ejecutar un algoritmo verificable que confirmará si esa suposición fue correcta o no. La definición basada en verificador o los programas de definición de máquina probarán esencialmente las elecciones iniciales de la máquina de Turing no determinista para verificar los resultados.
Todo esto es una estructura informática altamente teórica. Si bien el aprendizaje automático ha ido avanzando en ir más allá de los sistemas deterministas, la idea de verificar elecciones no deterministas aún está en pañales. Busque más desarrollo en esta frontera de la informática.
