Obere und untere Schranken für eingeschränkte Parity-Branchingprogramme

Abstract

Eine Boolesche Funktion wird einer Komplexitätsklasse zugeordnet, über die oberen und unteren Schranken des Ressourcenverbrauchs bei ihrer Berechnung in einem festen Berechungsmodell. Deshalb wird nach Methoden zur Bestimmung von oberen und unteren Schranken für die Größe von eingeschränkten Branchingprogrammen gesucht.Intensiv studiert wurden Branchingprogramme mit einmaligen geordneten Tests (OBDDs) und Parity-Akzeptierungsmodus. Der Parity-Akzeptierungsmodus und die Forderung nach einmaligen geordneten Tests erlaubt es, die Komplexität einer Booleschen Funktion, die mit OBDDs dargestellt werden sollen, mit Mitteln der linearen Algebra zu beschreiben. Diese Methode wird auf graphgesteuerte und wohlstrukturierte graphgesteuerte Branchingprogramme angewendet, bei denen das Lesen der Eingabe durch einen speziellen Graphen reglementiert wird. Aus der algebraischen Beschreibung wird ein Kriterium für untere Schranken abgeleitet, mit dessen Hilfe superpolynomielle untere Schranken für diese beiden Modelle bewiesen werden.Die Verwendung von arithmetischen OBDDs über Halbringen, von denen alle betrachteten OBDDs Spezialfälle sind, ermöglicht es, alle Akzeptierungsmodi gleichzeitig zu betrachten und Ergebnisse aus der Algebra auf OBDDs anzuwenden.Nichtdeterministische OBDDs mit Parity- und existenziellem Akzeptierungsmodus sind unvergleichbar. Es gibt Funktionen, die jeweils von OBDDs mit dem einen Akzeptierungsmodus in polynomieller Größe darstellbar sind, aber für die es nur OBDDs exponentieller Größe mit dem anderen Akzeptierungsmodus gibt. Es wird gezeigt, dass bezüglich der Approximation nichtdeterministische OBDDs mit Parity-Akzeptierungsmodus stärker sein könnten. Für jede Funktion, die von einem nichtdeterministischen OBDD quasipolynomieller Größe mit existenziellem Akzeptierungsmodus dargestellt werden kann, gibt es ein nichtdeterministisches OBDD gleicher Größenordnung mit Parity-Akzeptierungsmodus, das dieselbe Funktion darstellt, bis auf einen kleinen Anteil aller Eingaben.Eine Möglichkeit die Darstellungskraft von OBDDs zu vergrößern, ist mehrfache Tests der Eingabe zuzulassen. OBDDs mit k-fachen Tests erlauben das k-fache Lesen der Eingabe, allerdings immer in derselben Reihenfolge. Für die Darstellungskraft von deterministischen OBDDs mit k-fachen Tests gibt es eine strenge Hierarchie. Es wird gezeigt, dass konstant viele mehrfache Tests weder für nichtdeterministische OBDDs mit existenziellem, universellem oder Parity-Akzeptierungsmodus noch für randomisierte OBDDs zu einer größeren Darstellungskraft führen.