Tiempo polinomial no determinista (NP)
¿Qué significa el tiempo polinomial no determinista (NP)?
El tiempo polinomial no determinista (NP) es en realidad un marcador que se usa 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 pueden resolverse en tiempo polinomial mediante una máquina de Turing no determinista.
Techopedia explica el tiempo polinomial 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 polinomial surgió como una forma de hablar sobre la viabilidad del trabajo y desarrollo de algoritmos.
Si un problema está en un tiempo polinomial 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. Los programas de definición de máquina o de definición basados en verificadores probarán en esencia 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 más allá de los sistemas deterministas, la idea de verificar opciones no deterministas aún está en su infancia. Busque más desarrollo en esta frontera de la informática.