Jaka jest złożoność problemu równoważności drzew decyzyjnych do odczytu?

Drzewo decyzyjne do odczytu definiuje się następująco:

and się do odczytu po drzew decyzyjnych. $True$ $False$
Jeśli i są drzewami decyzyjnymi do odczytu, a jest zmienną nie występującą w i , to jest również drzewem decyzyjnym do odczytu. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Dane wejściowe: dwa drzewa decyzyjne i odczytu . $A$ $B$
Wyjście: Czy ? $A \equiv B$

Motywacja:

Ten problem pojawił się, gdy patrzyłem na problem równoważności dowodu (permutacja reguł) fragmentu logiki liniowej.

cc.complexity-theory lo.logic decision-trees boolean-formulas Marc
źródło

Czy nie możesz użyć zredukowanych diagramów decyzji binarnych? Edycja: może nie, twoje zmienne nie są uporządkowane ...

Sylvain,

@Kaveh Nie, występuje w teorii dowodu: patrzę na problem równoważności dowodu (permutacja reguł) fragmentu logiki liniowej. Sprowadza się do tego problemu boolowskiego. Ponieważ nie jestem specjalistą, pomyślałem, że zapytam, czy kiedykolwiek było to dobrze znane / łatwe pytanie. Stąd tak, wymyśliłem nazwę, bo nie znam nic lepszego.

Marc

@Marc, ogólnie dobrze jest wyjaśnić, dlaczego jesteś zainteresowany problemem. Zredagowałem pytanie. Sprawdź, czy wszystko jest w porządku. (Usuwam także moje poprzednie komentarze, ponieważ nie są już potrzebne.)

Kaveh

@Kaveh Tak, przepraszam za to. Zredagowałem twoje przeformułowanie, aby zbliżyć się do mojego pierwotnego argumentu (nie mogłem od razu ustalić, czy twój był w porządku, więc wydawało mi się to łatwiejsze)

Marc

Odpowiedzi:

Znalazłem częściowe rozwiązanie. Problem tkwi w L.

Negacja jest równoważna z który jest równoważny z zarówno i są. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

Odczytu jednokrotnego drzewo decyzyjne o może być otrzymana z odczytu raz drzewo decyzyjne dla przez włączenie and w . Można to zrobić w przestrzeni dziennika. $\bar{A}$ $A$ $True$ $False$ $A$

$\bar A \land B$ $False$ ${A} \land \bar{B}$ $True$ $x$ $\bar x$ $False$

Więc problem jest przynajmniej w L.

$AC_0$

EDIT2: tam jest, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Tak więc problem jest rzeczywiście kompletny w Logspace.

Marc
źródło

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}$

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

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

x

$x$

\bar{x}

$\overline{x}$

1

$1$

L

$L$

Łatwiejszym sposobem na stwierdzenie tego jest: Każda ścieżka jest terminem minimalnym lub maksymalnym, w zależności od etykiety liścia. Sprawdzamy, czy mają one te same minimalne warunki. Możemy wyliczyć min-terminy w przestrzeni dziennika, a sprawdzenie, czy dwa min-terminy są takie same, znajduje się w przestrzeni dziennika.

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
źródło

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ach tak, zapomniałem o tym, dodaję poprawkę z nadzieją, że teraz zadziała.

Denis,

Nie zapomnij odebrać miliona dolarów, jeśli to działa :)

Marc

L

$L$