P (complessità)

Diagramma di Eulero-Venn per le classi di complessità P, NP, NP-completo e NP-hard

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 ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$, tale che

• Per ogni ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle C_{n}}$ prende n bit come input e restituisce 1 bit in output
• Per ogni x in L, ${\displaystyle C_{|x|}(x)=1}$
• Per ogni x non in L, ${\displaystyle 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^[1]. La classe relativa di problemi funzionali è FP

Diversi problemi naturali sono completi per P, inclusa la raggiungibilità su grafi^[2]. L'articolo su problemi P-completi lista ulteriori problemi rilevanti in P.

Note

1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
2. Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, 1999, ISBN 0-387-98600-6.