Schaltungskomplexität: monotone Schaltung der Mehrheitsfunktion

8

Wie in der Arbeit "Monotone Schaltungen für die Mehrheitsfunktion" gezeigt, ist es möglich, eine monotone boolesche Schaltung für die Mehrheitsfunktion auf n Variablen mit der Größe O (n ^ 3) und der Tiefe 5,3 log (n) + O (1) zu konstruieren.

http://link.springer.com/chapter/10.1007/11830924_38

Meine Frage ist, wie zeitlich komplex eine solche Konstruktion ist. (dh die Zeit, die benötigt wird, um die Schaltung aufzubauen, gegeben mit n in unär)

Alan Carneiro
quelle

Antworten:

-1

Zeitkomplexität wird oft als "Anzahl der Operationen im schlimmsten Fall für eine Turing-Maschine" definiert. Das monotone Schaltungsmodell der Berechnung ist nicht das Turing-Zeitmodell. Daher ist es nicht sinnvoll zu sagen, wie zeitlich komplex eine solche Schaltung ist.

Wenn wir andererseits das monotone Schaltungsmodell als ein Modell tatsächlicher Schaltungen betrachten, dann ist ein "Zeitaufwand" der Berechnung die Tiefe einer solchen Schaltung. In diesem Sinne beträgt die zeitliche Komplexität der von Ihnen erwähnten Schaltung 5,3 log (n).

Natürlich gibt es in realen Schaltkreisen neben "Tiefe" noch andere Faktoren, die dazu beitragen, "wie lange es dauert, die Berechnung durchzuführen". Beispielsweise ist der längste Draht in einer Schaltung häufig ein Engpass bei der tatsächlichen VLSI-Berechnung, da das Laden seiner größeren Kapazität länger dauert.

Chris Blake
quelle
6
Die Frage fragt nach der zeitlichen Komplexität "der Konstruktion". Obwohl es unklar ist, habe ich es als die Zeit verstanden, die zum Aufbau der Schaltung benötigt wird, wenn n in unär angegeben wird. Das klingt für mich nach einer vernünftigen Frage. Insbesondere ist die Konstruktion eine randomisierte Polytime, und es ist interessant zu fragen, ob sie deterministisch subexponentiell gemacht werden kann.
Emil Jeřábek