Boolescher Formelausgleich in

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

1. War bekannt, dass Boolesche Formeln in ausgeglichen werden können ?$\mathsf{AC^0}$
2. Gibt es einen einfachen Beweis dafür, dass der Boolesche Formelausgleich in ?$\mathsf{AC^0}$

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 .$\mathsf{NC^1}$

Hintergrund

Hier sind alle genannten Komplexitätsklassen einheitlich.

BFB (Boolean Formel Balancing):
eine Boolesche Formel , findet eine äquivalente ausgewogene Boolesche Formel.$\varphi$

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 .$\mathsf{AC^0}$$\mathsf{TC^0}$$\mathsf{NC^1}$$BFB \in \mathsf{NC^2}$

$BFB \in \mathsf{AC^0}$$BFE \in \mathsf{NC^1}$

$\varphi$$\tau$$\varphi$
$\tau$$\varphi$$\tau \vDash \varphi$

$BFE$$\mathsf{NC^1} = \mathsf{ALogTime}$

$BFB$$\mathsf{NC^1}$

$\varphi$$BFE$$\varphi$$\mathsf{AC^0}$$BFE$$\varphi$

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 .$BFB$$\mathsf{AC^0}$$\mathsf{TC^0}$$\mathsf{NC^1}$$BFE \in \mathsf{NC^1}$$\mathsf{NC^1}$$BFB$$\mathsf{NC^1}$

Fragen

1. War bekannt, dass Boolesche Formeln in ( ) ausgeglichen werden können ?$\mathsf{AC^0}$$BFB\in \mathsf{AC^1}$
2. Gibt es ein einfacheres Argument (z. B. ohne ) für ?$BFE\in \mathsf{NC^1}$$BFB\in\mathsf{AC^0}$

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.$\mathsf{NC}^1$

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.