Direkt zum Inhalt

Lexikon der Mathematik: NC1-Reduktion

Begriff aus der Theorie Boolescher Funktionen.

Eine Folge f = (fn) Boolescher Funktionen ist auf eine Folge g = (gn) Boolescher Funktionen NC1-reduzierbar, Notation f1g, wenn f = (fn) durch Schaltkreise Sn berechnet werden kann, die neben Bausteinen vom fan-in 2 auch Bausteine für gi, die zur Größe i und zur Tiefe ⌈ld(i)⌉ beitragen, enthalten dürfen. Dabei müssen die Schaltkreise Sn polynomielle Größe und logarithmische Tiefe haben.

NC1-Reduktionen sind das angemessene Reduktionskonzept für die Sprachklasse non-uniform-NCk.

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