Direkt zum Inhalt

Lexikon der Mathematik: NC

(Nick’s Class, benannt nach Nick Pippenger), eine Sprachklasse.

Mit NC wird innerhalb der nichtuniformen Komplexitätstheorie die Vereinigung der Klassen NCk bezeichnet und damit die Klasse der von Schaltkreisen mit beschränktem Fan-in in polynomieller Größe und polylogarithmischer Tiefe darstellbaren Booleschen Funktionen.

Innerhalb der Algorithmentheorie bezeichnet NC die Klasse der Probleme, die mit einer parallelen Registermaschine mit polynomiell vielen Prozessoren in polylogarithmischer Zeit gelöst werden können und damit die Klasse der effizient paral- lelisierbaren Probleme.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos