P (complessità)
classe di complessità / Da Wikipedia, l'enciclopedia encyclopedia
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità. Contiene tutti i problemi decisionali che possono essere risolti da una macchina di Turing deterministica usando una quantità polinomiale di tempo di computazione, o tempo polinomiale.
Questa voce sull'argomento teorie dell'informatica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
La tesi di Cobham asserisce che P è la classe di problemi computazionali che sono "risolvibili efficientemente" o "trattabili"; in pratica, qualche problema che non si sa essere in P ha soluzioni pratiche, e qualche problema in P non ne ha.