Índice:
- Definição - O que significa Tempo Polinomial Não-Determinístico (NP)?
- Techopedia explica o tempo polinomial não determinístico (NP)
Definição - O que significa Tempo Polinomial Não-Determinístico (NP)?
O tempo polinomial não determinístico (NP) é realmente um marcador usado para apontar para um conjunto de problemas e limites da capacidade de certos tipos de computação. NP refere-se ao conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing não determinística.
Techopedia explica o tempo polinomial não determinístico (NP)
O tempo polinomial não determinístico é baseado na frase "tempo polinomial", que se refere a se um algoritmo pode executar dentro de certos limites relevantes para a velocidade. O tempo polinomial surgiu como uma maneira de falar sobre a viabilidade do trabalho e desenvolvimento de algoritmos.
Se um problema está no tempo polinomial não determinístico, a máquina de Turing não determinística pode adivinhar a solução e depois executar um algoritmo verificável que confirmará se essa suposição estava correta ou não. Os programas de definição com base em verificador ou de definição de máquina testarão, em essência, as escolhas iniciais da máquina de Turing não determinística para verificar os resultados.
Tudo isso é estrutura de computação altamente teórica. Embora o aprendizado de máquina esteja fazendo incursões para ir além dos sistemas determinísticos, a idéia de verificar escolhas não determinísticas ainda está engatinhando. Procure mais desenvolvimento nessa fronteira da computação.
