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 (Bsp: Tiefensuchreihenfolge)

(vgl. für sequentielle Algorithmen: Klasse NP, Polynomialzeitreduktion ≤_P, NP-Vollständigkeit)