NC (Komplexitätsklasse)

NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme. Die Motivation zur Bildung und Untersuchung der Klasse NC ergibt sich daraus, Probleme zu identifizieren, die auf einem Parallelrechner in deutlich besserer Zeit als auf einer sequentiell arbeitenden Maschine bei einer vertretbar großen Zahl von Prozessoren gelöst werden können.