P (Complexitat)
De Viquipèdia
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 na quantitat de temps de computació polinòmic, temps polinòmic.
Es considera P com la classe de problemes computacionalment que 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.
[edita] Problemes notables dins de P
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. A l'any 2002, es va demostrar que el problema de determinar si un nombre és primer recau dins P.[1]
[edita] Relació amb altres classes
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. És veu de forma trivial que P és un subconjunt de NP. Tot i que no està provat, la majoria d'experts creuen que es un subconjunt estricte.[2]
P se sap que és almenys tant 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 son 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 solubles 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:
On EXPTIME és la classe de problemes resolubles en temps exponencial
