Was ist die Komplexität des Äquivalenzproblems für einmal gelesene Entscheidungsbäume?

Ein einmal gelesener Entscheidungsbaum ist wie folgt definiert:

und sind einmal gelesene Entscheidungsbäume. $True$ $False$
Wenn und einmal gelesene Entscheidungsbäume sind und eine Variable ist, die in und nicht vorkommt , dann ist auch ein einmal gelesener Entscheidungsbaum. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Input: Zwei schreib einmal Entscheidungsbäume und . $A$ $B$
Ausgabe: Ist ? $A \equiv B$

Motivation:

Dieses Problem trat auf, als ich das Problem der Beweisäquivalenz (Permutation von Regeln) eines Fragments der linearen Logik betrachtete.

cc.complexity-theory lo.logic decision-trees boolean-formulas Marc
quelle

Können Sie keine reduzierten binären Entscheidungsdiagramme verwenden? Edit: äh vielleicht nicht, deine Variablen sind nicht geordnet ...

Sylvain

@Kaveh Nein, es kommt in der Beweistheorie vor: Ich betrachte das Beweisäquivalenzproblem (Permutation von Regeln) eines Fragments der linearen Logik. Es läuft auf dieses boolesche Problem hinaus. Da ich kein Spezialist bin, dachte ich mir, ich würde fragen, ob dies jemals eine bekannte / einfache Frage war. Daher habe ich mir den Namen ausgedacht, weil ich es nicht besser weiß.

Marc

@Marc, es ist im Allgemeinen eine gute Idee zu erklären, warum Sie an einem Problem interessiert sind. Ich habe die Frage bearbeitet. Bitte schauen Sie, um sicherzustellen, dass es in Ordnung ist. (Entfernen Sie auch meine vorherigen Kommentare, da sie nicht mehr benötigt werden.)

Kaveh

@ Kaveh Ja, tut mir leid. Ich habe Ihre Neuformulierung bearbeitet, um sie meinem ursprünglichen Argument näher zu bringen (ich konnte nicht sofort herausfinden, ob Ihre in Ordnung war, daher schien es einfacher, dies zu tun)

Marc

Antworten:

Ich habe eine Teillösung gefunden. Das Problem ist in L.

Die Negation von ist äquivalent zu was äquivalent ist, wenn sowohl als auch sind. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

Der einmal gelesene Entscheidungsbaum für kann aus dem einmal gelesenen Entscheidungsbaum für durch Umschalten von und in . Dies kann im Protokollbereich erfolgen. $\bar{A}$ $A$ $True$ $False$ $A$

Um zu überprüfen, ob gleich (und ähnlich wie bei ), durchlaufen wir alle Paare von Blättern, eines von jedem Baum, und prüfen, ob sie kompatibel sind (das gibt es kein auf einem der Pfade und auf dem anderen). Es ist äquivalent zu wenn wir kein kompatibles Paar finden. Dies kann im Protokollbereich erfolgen. $\bar A \land B$ $False$ ${A} \land \bar{B}$ $True$ $x$ $\bar x$ $False$

Das Problem liegt also zumindest in L.

EDIT: Ich habe einige Ideen, um zu beweisen, dass dies L-vollständig ist, wahrscheinlich unter -Reduktion. Aber ich müsste die Details überprüfen und es passt nicht hierher. Ich werde einen Link zu dem Artikel posten, den ich schreibe, wenn alles klappt! $AC_0$

EDIT2: da ist es, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Das Problem ist also tatsächlich vollständig.

Marc
quelle

Wie kommst du zu dieser Negation? Die Negation von

sollte

, das heißt

x . A + \bar{x} . B

$x.A+\overline{x}.B$

(\bar{x} + \bar{A}) . (x + \bar{B})

$(\overline{x}+\overline{A}).(x+\overline{B})$

x . \bar{A} + \bar{x} . \bar{B} + \bar{A} . \bar{B}

$x.\overline{A}+\overline{x}.\overline{B}+\overline{A}.\overline{B}$

Denis

@Denis: Ich glaube das war ein Tippfehler, deine Formel vereinfacht sich zu

, also wird die Negation tatsächlich berechnet, indem die 0 und 1 an den Blättern umgedreht werden.

x . \bar{A} + \bar{x} . \bar{B}

$x.\bar A+\bar x.\bar B$

Nicolas Perrin

x

$x$

\bar{x}

$\overline{x}$

1

$1$

L

$L$

Eine einfachere Möglichkeit, dies anzugeben, ist: Jeder Pfad ist ein Min- oder Max-Term, abhängig von der Beschriftung seines Blattes. Wir prüfen, ob sie die gleichen Mindestlaufzeiten haben. Wir können die Min-Terme im Protokollbereich aufzählen und prüfen, ob zwei Min-Terme identisch sind, im Protokollbereich.

Kaveh

N C^{1}

$NC^1$

A C^{0}

$AC^0$

A C^{0}

$AC^0$

$\phi$

$0$ $1$ $1$ $\{x,\overline{y},z\}$ $\{x,\overline{y},z\}$ $\{x,y,z\}$ $\{x,z\}$ $y$ $\{x,\overline{y},z,t\}$ $\{x,y,z\}$

$\{x_1,\dots,x_n\}$ $i$ $x_i$ $\{\vec x,x_i,x_j\},\{\vec x,\overline{x_j}\}$ $\{\vec x,x_i\},\{\vec x,\overline{x_i},\overline{x_j}\}$ $i<j$ $\vec x$ $x_i$ $x_j$ $j-i$

$P$

Denis
quelle

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ah ja, das habe ich vergessen. Ich füge ein Update hinzu und hoffe, dass es jetzt funktioniert.

Denis

Vergessen Sie nicht, Ihre Million Dollar zu beanspruchen, wenn es funktioniert :)

Marc

L

$L$