title: P (complessità)
text: # P (complessità)
  
  Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o $DTIME(n^{O(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.
  
  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.
  
  ## Definizione
  
  Un linguaggio L è in P se e solo se esiste una macchina di Turing deterministica M tale che
  
  * M viene eseguita in tempo polinomiale per tutti gli input
  * Per tutti gli x in L, M restituisce in output 1
  * Per tutti gli x non in L, M restituisce in output 0
  
  P può anche essere vista come una famiglia uniforme di circuiti booleani. Un linguaggio L è in P se e solo se esiste una famiglia di circuiti booleani a tempo polinomiale uniforme $\{C_{n}:n\in \mathbb {N} \}$, tale che
  
  * Per ogni $n\in \mathbb {N}$, $C_{n}$ prende n bit come input e restituisce 1 bit in output
  * Per ogni x in L, $C_{|x|}(x)=1$
  * Per ogni x non in L, $C_{|x|}(x)=0$
  
  ## Problemi notevoli in P
  
  Si sa che P contiene molti problemi naturali, incluse le versioni decisionali di programmazione lineare, calcolare il massimo comun divisore e trovare la corrispondenza massima. Nel 2002 è stato mostrato che il problema del determinare se un numero è primo è in P. La classe relativa di problemi funzionali è FP
  
  Diversi problemi naturali sono completi per P, inclusa la raggiungibilità su grafi. L'articolo su problemi P-completi lista ulteriori problemi rilevanti in P.
  
  