P (complessità)
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/310px-P_np_np-complete_np-hard.svg.png)
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.
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 , tale che
- Per ogni , prende n bit come input e restituisce 1 bit in output
- Per ogni x in L,
- Per ogni x non in L,
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
- ^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
- ^ Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, 1999, ISBN 0-387-98600-6.
V · D · M | |
---|---|
P · NP · co-NP · NP-C · co-NP-C · NP-hard · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · Co-RE · RE-C · Co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)