P (complexiteitsklasse)

In de complexiteitstheorie is P, ook bekend als PTIME en DTIME(n^O(1)), een complexiteitsklasse die alle beslissingsproblemen bevat die in polynomiale tijd opgelost kunnen worden door een deterministische turingmachine. Als vuistregel hanteert men dat de problemen die tot de complexiteitsklasse P behoren "efficiënt" oplosbaar zijn; er bestaan uitzonderingen hierop maar deze regel geldt over het algemeen wel.

Verbanden tussen complexiteitsklassen.

Enkele problemen die tot P behoren zijn het testen of een getal een priemgetal is, vraagstukken op het gebied van lineair programmeren en het berekenen van de grootste gemene deler.

Kenmerken

P is een deelverzameling van de complexiteitsklasse NP, de klasse met beslissingsproblemen die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine. Het vermoeden bestaat dat P een strikte deelverzameling is van NP. Enkele deelverzamelingen van P zijn L, NL, NC en SC. Er geldt tevens dat ${\text{P}}\subseteq {\text{PSPACE}}$, waarbij PSPACE de beslissingsproblemen bevat die op een deterministische turingmachine opgelost kunnen worden met polynomiale ruimte.

P kan gedefinieerd worden in termen van DTIME: $\cup _{k=1}^{\infty }{\text{DTIME}}(n^{k})$.

P is gelijk aan AL, ook bekend als Alternating L, de beslissingsproblemen die oplosbaar zijn met logaritmische ruimte door een alternerende turingmachine.

Referenties

• (en) P, Complexity Zoo