P (Complexitat)

De Viquipèdia
Dreceres ràpides: navegació, cerca

En Teoria de complexitat computacional, P és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing determinista usant una quantitat de temps de computació polinòmic, temps polinòmic.

Es considera P com la classe de problemes que computacionalment són "eficientment resolubles" o "tractables", tot i que hi ha classes majors que es poden considerar tractables com RP o BPP. A més, hi ha problemes dins de P que són intractables en termes pràctics: per exemple, poden requerir n1000000 operacions.

Problemes notables dins de P[modifica | modifica el codi]

P és conegut per contenir molts problemes naturals, incloent-hi les versions de decisió de la programació lineal, calcular el major comú divisor o fer matching. L'any 2002 es va demostrar que el problema de determinar si un nombre és primer recau dins de P.[1]

Relació amb altres classes[modifica | modifica el codi]

Una generalització de P és NP, que és la classe de llenguatges decidibles en temps polinòmic en una màquina de Turing no determinista. Es veu de forma trivial que P és un subconjunt de NP. Tot i que no està provat, la majoria d'experts creuen que n'és un subconjunt estricte.[2]

Se sap que P és almenys tan gran com L, la classe de problemes decidibles en un espai de memòria logarítmic. Una màquina que usi O(log n) d'espai no pot usar més de 2O(log n)=nO(1) en temps, perquè aquestes són totes les possibles configuracions; per tant, L és un subconjunt de P. Un altre problema important és saber si L = P. Se sap que P = AL, el conjunt de problemes resolubles en espai de memòria logarítmic per Alternating Turing Machines. També se sap que P no és més gran que PSPACE, la classe de problemes decidibles en espai polinòmic. Altre cop, si P = PSPACE, és un problema obert. Per resumir:

\mbox{L} \subseteq \mbox{AL} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}

On EXPTIME és la classe de problemes resolubles en temps exponencial.

Referències[modifica | modifica el codi]

  1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2. Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education, page 458, ISBN 0-02-360692-4