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 f ≤1g, 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.
Copyright Springer Verlag GmbH Deutschland 2017
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.