P (complexitate)

Diagrama Euler-Venn pentru clasele de complexitate P, NP , NP-complete și NP-hard

În teoria complexității de calcul , P , cunoscut și ca PTIME sau DTIME ( n ^{O (1)} ), este una dintre cele mai importante clase de complexitate . Conține toate problemele de decizie care pot fi rezolvate de o mașină determinantă de Turing folosind o cantitate polinomială de timp de calcul sau timp polinomial .

Teza lui Cobham afirmă că P este clasa problemelor de calcul care sunt „rezolvabile eficient” sau „tratabile”; în practică, o problemă despre care nu știm că este în P are soluții practice, iar unele probleme în P nu au niciuna.

Definiție

Un limbaj L este în P dacă și numai dacă există o mașină determinantă Turing M astfel încât

M se execută în timp polinomial pentru toate intrările
Pentru toate x în L , ieșirile M 1
Pentru toate x-urile care nu sunt în L , M produce 0

P poate fi de asemenea văzut ca o familie uniformă de circuite booleene . Un limbaj L este în P dacă și numai dacă există o familie de circuite booleene uniforme în timp polinomial $\{C_{n}:n\in \mathbb {N} \}$ ${\ displaystyle \ {C_ {n}: n \ in \ mathbb {N} \}}$ $\ {C_n: n \ in \ mathbb {N} \}$ , astfel încât

Pentru fiecare $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ $n \ in \ mathbb {N}$ , $C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ ia n biți ca intrare și returnează 1 bit ca ieșire
Pentru fiecare x în L , $C_{|x|}(x)=1$ ${\ displaystyle C_ {| x |} (x) = 1}$ $C_ {| x |} (x) = 1$
Pentru orice x care nu este în L , $C_{|x|}(x)=0$ ${\ displaystyle C_ {| x |} (x) = 0}$ $C_ {| x |} (x) = 0$

Probleme notabile în P

Se știe că P conține multe probleme naturale, inclusiv versiuni de decizie ale programării liniare , calculând cel mai mare divizor comun și găsind cea mai mare potrivire . În 2002 s-a arătat că problema determinării dacă un număr este prim se află în P ^[1] . Clasa relativă de probleme funcționale este FP

Mai multe probleme naturale sunt complete pentru P, inclusiv accesibilitatea pe grafice ^[2] . Articolul despre P- probleme complete enumeră alte probleme relevante pentru P.

Notă

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

Portal IT

Portalul de matematică

[1] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, " PRIMES is in P ", Annals of Mathematics 160 (2004), nr. 2, pp. 781–793.

[Immerman_Reachability-2] Neil Immerman , Complexitate descriptivă , New York, Springer-Verlag, 1999, ISBN 0-387-98600-6 .

[1]

[2]