P (complexiteitsklasse)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Verbanden tussen complexiteitsklassen.

In de complexiteitstheorie is P, ook bekend als PTIME en DTIME(nO(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.

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[bewerken]

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[bewerken]