I problemi che una (TM) macchina di Turing può risolvere date certe risorse di tempo e spazio si possono dividere in due classi di complessità:
- Classe P: problemi che una TM può risolvere con un algoritmo in tempo polinomiale.
- Classe NP (Non deterministic Polynomial time): problemi per cui posso verificare una soluzione in tempo efficiente. Esempio: Fattorizzare dove e sono primi di bit (problema di factoring).
P NP
Tutti i problemi in NP sono in realtà in P? (domanda ancora aperta)
Se il factoring fosse rivelato essere in P, la maggior parte dei sistemi crittografici salterebbero. Il problema del factoring potrebbe stare in (Q)P nel contesto dei computer quantistici teorici (“Quantum Polynomial time”).