Definição – O que significa Tempo Polinomial Não Determinístico (NP)?
O tempo polinomial não determinístico (NP) é na verdade 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.
Definirtec 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 ser executado dentro de certos limites relevantes para a velocidade. O tempo polinomial surgiu como uma forma de falar sobre a viabilidade de trabalho e desenvolvimento de algoritmos.
Se um problema está em um tempo polinomial não determinístico, a máquina de Turing não determinística pode primeiro adivinhar a solução e, em seguida, executar um algoritmo verificável que confirmará se essa estimativa foi correta ou não. A definição baseada em verificador ou os programas de definição de máquina irão, em essência, testar as escolhas iniciais da máquina de Turing não determinística para verificar os resultados.
Tudo isso é uma estrutura de computação altamente teórica. Embora o aprendizado de máquina tenha feito incursões para ir além dos sistemas determinísticos, a ideia de verificar escolhas não determinísticas ainda está em sua infância. Procure mais desenvolvimento nesta fronteira da computação.