[Teoria] classe NP e classe P - dubbio

[Kioru19]

Salve,

data la definizione di classe $NP$ e classe $P$ mi chiedo: se prendo i problemi che sono in $NP$ ma non in $P$ allora è corretto dire che sono problemi per i quali, se provo a risolverli con una macchina deterministica (che sono quelle che esistono nella realtà), allora non impiego tempo polinomiale bensì esponenziale?

Grazie

[giuspeppe94]

Premesso che l'esistenza di tali problemi è una congettura, uno dei 7 problemi del millennio, puoi dire che non impieghi tempo polinomiale nella dimensione dell'input qualunque essa sia. Conviene dirlo con i simboli matematici che è più chiaro, non esiste un polinomio in n che limita superiormente il tempo necessario per risolvere il problema di dimensione n per ogni n. Questo NON vuol dire che il tempo come minimo sia esponenziale, basta guardare il problema "graph isomorphism" che allo stato attuale potrebbe essere in NP, ma non in P, che è risolubile in tempo quasi-polinomiale.

http://jeremykun.com/2015/11/12/a-quasi ... e-details/

[Kioru19]

Ok grazie penso di aver capito.