Cuprins:
- Definiție - Ce înseamnă timpul polinomial nedeterminist (NP)?
- Techopedia explică timpul polinomial nedeterminist (NP)
Definiție - Ce înseamnă timpul polinomial nedeterminist (NP)?
Timpul polinomial nedeterminist (NP) este de fapt un marker folosit pentru a indica un set de probleme și limite ale capacității anumitor tipuri de calcul. NP se referă la ansamblul de probleme care pot fi rezolvate în timp polinomial de către o mașină de Turing nedeterministă.
Techopedia explică timpul polinomial nedeterminist (NP)
Timpul polinomial nedeterminant se bazează pe expresia „timp polinomial”, care se referă la faptul că un algoritm poate efectua în anumite limite relevante pentru viteză. Timpul polinomial a apărut ca o modalitate de a vorbi despre fezabilitatea muncii și dezvoltării algoritmilor.
Dacă o problemă se află într-un timp polinomial nedeterminist, mașina de Turing nedeterministă poate ghici mai întâi la soluție, apoi poate rula un algoritm verificabil care va confirma dacă acea ghicire a fost corectă sau nu. Programele de definire pe bază de verificare sau de definire a mașinii vor testa, în esență, alegerile inițiale ale mașinii Turing nedeterministe pentru a verifica rezultatele.
Toate acestea sunt o structură de calcul extrem de teoretică. În timp ce învățarea mașină a reușit să depășească sistemele deterministe, ideea verificării alegerilor non-deterministe este încă la început. Căutați mai multe dezvoltări pe această frontieră a calculului.
