P (complessità)

Nella Teoria della complessità computazionale la classe P identifica l'insieme di quei problemi (ovvero linguaggi, insiemi; problemi la cui decisione consiste nella verifica di appartenenza di un dato elemento, o stringa, al linguaggio) decidibili in un numero polinomiale, rispetto alla lunghezza della stringa di input, di passi da una Macchina di Turing deterministica.
Per saperne di più visita Wikipedia.org...