Kanonische Darstellung des binären Entscheidungsbaums in Ptime?

Ich frage mich, ob es eine Möglichkeit gibt, eine Art "Normalform" für binäre Entscheidungsbäume (BDT) auf nachvollziehbare Weise zu geben.

Genauer gesagt: Ein BDT ist ein Baum mit internen Knoten, die durch boolesche Variablen gekennzeichnet sind, und Blättern, die mit $0$ oder $1$ . Ein BDT repräsentiert auf offensichtliche Weise eine boolesche Funktion. Zwei BDT $A,B$ sind äquivalent ( $A\sim B$ ), wenn sie dieselbe Funktion darstellen.

Gibt es eine Funktion $f$ , die ein BDT eingibt und in eine andere Datenstruktur umwandelt, so dass:

1. $f$ ist in Ptime
2. $f(A)=f(B)$ genau dann, wenn$A\sim B$
3. $f$ hat ein pseudo-inverses$g$ ,dh$g(f(A))\sim A$ , ebenfalls in Ptime

Zum Beispiel validieren reduzierte geordnete binäre Entscheidungsdiagramme OBDD 2 und 3, aber nicht 1, da die Ausgabe bei falscher Variablenreihenfolge möglicherweise exponentiell groß ist.

Ich habe das Gefühl, dass dies möglicherweise nicht möglich ist, habe aber nirgendwo Beweise dafür gefunden.

Um den Vorschlag von Ricky Demer weiter zu kommentieren:

$PEq$$Ker$$PEq=Ker$$Ker=CF$

$PEq\neq Ker$$Ker\neq CF$

$\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$$A \mapsto g(f(A))$$|g(f(A))|$$\text{poly}(|A|)$$B$$A$$g(f(A)) = g(f(B))$$|g(f(A))|$$\text{poly}(|B|)$$\mathsf{NP} \subseteq \mathsf{SUBEXP}$