Komplexitätstheorie

...für parallele Algorithmen

Klassen:

• NC = polylogarithmische Zeit, polynomielle Anzahl von Prozessoren

• P = polynomielle Zeit

• NC ⊆ P

Reduktionen:

• ≤_L logspace-Reduktion, Eigenschaften
• P-vollständige Probleme