WikiDer > P (Komplexitätsklasse)

Beziehungen zwischen Komplexitätsklassen.

In dem Komplexitätstheorie ist p, auch bekannt als PTIME und DTIME(nein^Ö(1)), ein Komplexitätsklasse diese alle Entscheidungsprobleme enthält das in Polynomzeit kann gelöst werden durch a deterministische Turingmaschine. Als Faustregel gilt, dass die Probleme der Komplexitätsklasse p sollte "effizient" lösbar sein; Davon gibt es Ausnahmen, aber diese Regel gilt grundsätzlich.

Einige Probleme, die zu führen p gehören testet, ob eine Zahl a . ist Primzahl ist, Probleme im Zusammenhang mit Lineares Programmieren und berechnen die größter gemeinsamer Teiler.

Eigenschaften

p ist ein Teilmenge der Komplexitätsklasse NP, die Klasse mit in polynomieller Zeit lösbaren Entscheidungsproblemen durch a nichtdeterministische Turingmaschine. Es wird vermutet, dass p ein strenge Teilmenge ist von NP. Einige Teilmengen von p sein l, NL, NC und SC. Es gilt auch, dass ${displaystyle { ext{P}}subsetq { ext{PSPACE}}}$, bei welchem PSPACE enthält die Entscheidungsprobleme, die auf einer deterministischen Turingmaschine mit Polynomraum gelöst werden können.

p kann definiert werden in DTIME: ${displaystyle cup _{k=1}^{infty }{ ext{DTIME}}(n^{k})}$.

p entspricht BEREITS, auch bekannt als Abwechselndes L, die mit logarithmischem Raum lösbaren Entscheidungsprobleme durch eine Tür alternierende Turingmaschine.

Verweise

• (und) p, Komplexität Zoo