Per problemi NP si intende l'insieme di quei problemi per cui non è ancora stato trovato un algoritmo in grado di risolverli in tempo polinomiale (si crede fortemente che non sarà mai possibilie trovarne). Tuttavia se viene data la soluzione del problema NP questa si può verificare in tempo polinomiale.
Un esempio di problema NP è il Sudoku: per trovare la soluzione gli algoritmi attualmente conosciuti ci impiegano tempo esponenziale. Tuttavia se viene già fornita la soluzione (l'insieme delle cifre da immettere nelle rispettive caselle) questa si può verificare in tempo polinomiale, semplicemente riempiendo la tabella e verificando che non dia errori.

Spero di esserti stato d'aiuto....