Charakterisierung von einmal lesbaren Formeln über die gesamte Binärbasis

15

Hintergrund

Eine Read-Once-Formel über eine Reihe von Gattern (auch Basis genannt) ist eine Formel, in der jede Eingabevariable einmal vorkommt. Einmal-Lese-Formeln werden üblicherweise über die De Morgan-Basis (die die 2-Bit-Gatter AND und OR und das 1-Bit-Gatter NOT aufweist) und die vollständige Binärbasis (die alle 2-Bit-Gatter aufweist) untersucht.

So kann zum Beispiel das UND von 2 Bits als Einmal-Lese-Formel auf jeder Basis geschrieben werden, aber die Parität von 2 Bits kann nicht als Einmal-Lese-Formel auf der De Morgan-Basis geschrieben werden.

Die Menge aller Funktionen, die als einmal lesbare Formel über die De Morgan-Basis geschrieben werden können, hat eine kombinatorische Charakterisierung. Siehe zum Beispiel die kombinatorische Charakterisierung von Einmallese -Formeln von M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.

Frage

Gibt es eine alternative Charakterisierung des Satzes von Funktionen, die durch eine Einmallese-Formel über die gesamte Binärbasis berechnet werden können?

Einfachere Frage (hinzugefügt in Version 2)

Obwohl ich immer noch an einer Antwort auf die ursprüngliche Frage interessiert bin, dachte ich, da ich keine Antworten erhalten habe, werde ich eine einfachere Frage stellen: Was sind einige Techniken für untere Schranken, die für Formeln über die gesamte Binärbasis funktionieren? (Andere als die, die ich unten aufführe.)

Beachten Sie, dass ich jetzt versuche, die Formelgröße (= Anzahl der Blätter) zu verringern. Für einmal lesbare Formeln haben wir Formelgröße = Anzahl der Eingaben. Wenn Sie also nachweisen können, dass eine Funktion eine Formel benötigt, deren Größe streng größer als n ist, bedeutet dies auch, dass sie nicht als Einmallese-Formel dargestellt werden kann.

Ich kenne die folgenden Techniken (zusammen mit einer Referenz für jede Technik aus Boolean Function Complexity: Advances and Frontiers von Stasys Jukna ):

  • Nechiporuks Methode für universelle Funktionen (Abschn. 6.2): ​​Zeigt eine Untergrenze von für eine bestimmte Funktion. Dies hilft Ihnen jedoch nicht dabei, untere Grenzen für eine bestimmte Funktion zu finden, an der Sie interessiert sein könnten.n2-Ö(1)
  • Ω(n2/Log⁡n)
cc.complexity-theory circuit-complexity lower-bounds formulas Robin Kothari
quelle
Haben Sie sich mit BDDs und binären Entscheidungsdiagrammen befasst ? Sind sie nicht ziemlich komplex? Habe aber noch keinen Spec-Ref auf dem Subj. gesehen.
vzn

Antworten:

-2

Es gibt auch eine Methode namens Krapchenko-Untergrenze, die "etwas größer sein kann als die Nechiporuks-Methode". siehe John E Savage, Berechnungsmodelle, Abschnitt 9.4.2. (Dies wird direkt nach der Nechiporuk-Methode in Abschnitt 9.4.1 behandelt.)

vzn
quelle
2
Vielen Dank für den Hinweis, aber Krapchenkos Methode funktioniert nur über die De Morgan-Basis (in Savages Buch als "Standardbasis" bezeichnet). Meine Frage ist über die volle binäre Basis.
Robin Kothari
Wenn die Nechiporuks-Methode über die gesamte Binärbasis funktioniert und die Methode im Savages-Buch als über die De Morgan- / Standardbasis arbeitend gezeigt wird, warum funktioniert Krapchenkos dann nicht auch über beide? aber einig Savage hat kein Beispiel für die Krapchenko / volle binäre Basis.
vzn
1
Die vollständige binäre Basis ist eine Obermenge der De Morgan-Basis. Alle Untergrenzen, die gegen die vollständige Binärbasis arbeiten, funktionieren auch gegen die De Morgan-Basis.
Robin Kothari
ok, fein, was schließt die Krapchenko Methode aus, die auf der vollen binären Basis arbeitet? Ich vermute, dass die Nechiporuk-Methode wahrscheinlich zuerst auf die de Morgan-Basis angewendet und dann auf die vollständige Basis erweitert wurde, oder? Was schließt das für die Krapchenko-Methode aus?
vzn