Boolescher Formelausgleich in

10

Ich suche nach Referenzen über die Komplexität des Booleschen Formelausgleichsproblems . Speziell,

  1. War bekannt, dass Boolesche Formeln in ausgeglichen werden können ?AC0
  2. Gibt es einen einfachen Beweis dafür, dass der Boolesche Formelausgleich in ?AC0

Mit "einfach" meine ich einen Beweis, der einfacher ist als der unten erwähnte, insbesondere suche ich einen Beweis, der nicht davon abhängt, dass die Bewertung der Booleschen Formel in vorliegt .NC1


Hintergrund

Hier sind alle genannten Komplexitätsklassen einheitlich.

BFB (Boolean Formel Balancing):
eine Boolesche Formel , findet eine äquivalente ausgewogene Boolesche Formel.φ

Ich interessiere mich für die Komplexität dieses Problems, insbesondere für einfache Beweise, die zeigen, dass das Problem in (oder sogar T C 0 oder N C 1 ) vorliegt. Die gängigen Ausgleichsargumente, wie sie auf Spiras Lemma basieren, wenden wiederholte strukturelle Modifikationen auf den Formelbaum an, die nur B F B N C 2 zu ergeben scheinen .AC0TC0NC1BFBNC2

BFBAC0BFENC1


φτφ
τφτφ

BFENC1=ALogTime

BFBNC1

φBFEφAC0BFEφ

φλp.Eval(φ,p)

Motivation

Ein einfacheres Argument für in (oder oder sogar ) würde einen neuen einfacheren Beweis für da es leicht zu erkennen ist, dass die ausgeglichene Version von BFE in gelöst werden kann und wir sie mit komponieren können und das Ergebnis in .BFBAC0TC0NC1BFENC1NC1BFBNC1


Fragen

  1. War bekannt, dass Boolesche Formeln in ( ) ausgeglichen werden können ?AC0BFBAC1
  2. Gibt es ein einfacheres Argument (z. B. ohne ) für ?BFENC1BFBAC0
Kaveh
quelle
3
Welche Definition von "Gleichgewicht" verwenden Sie?
Dana Moshkovitz
1
@Dana, wir können so etwas wie (dh mit bestimmten Konstanten) verwenden. Siehe auch Bonnet und Buss 'Artikel " Size-Depth Tradeoff for Boolean Formulas ", 2002.Depth<10lgSize+100Depth=O(lgSize)
Kaveh
vereinbart, dass die Definition des "Ausgleichs" klargestellt werden sollte. ähnelt dies dem Konzept des Balancierens in binären Bäumen? zB "selbstausgeglichene Bäume"
vzn

Antworten:

3

Ich bin mir nicht sicher, ob dies sehr relevant ist, aber in Log-Space-Algorithmen für Pfade und Übereinstimmungen in k-Bäumen ( basierend auf einer langen Geschichte früherer Arbeiten und speziell auf Arithmetisierungsklassen um NC1 und L von Limaye-Mahajan-Rao) zeigen wir So finden Sie rekursive ausgeglichene Trennzeichen für einen Baum in Logspace. Diese Grenze kann sehr gut zu verbessert werden, wenn der Eingabebaum direkt in der Zeichenfolgendarstellung angegeben ist.NC1

Die Grundidee besteht darin, den Baum als Klammerausdruck darzustellen und ausgewogene Trennzeichen für diese zu finden. Beachten Sie, dass wir Blatttrennzeichen finden, dh Teilbäume, die nach Anzahl der Blätter ausgeglichen sind.

SamiD
quelle