Quelle est la complexité du problème d'équivalence pour les arbres de décision à lecture unique?

Un arbre de décision à lecture unique est défini comme suit:

et sont des arbres de décision à lecture unique. $True$ $False$
Si et sont des arbres de décision à lecture unique et que est une variable pas dans et , alors est également un arbre de décision à lecture unique. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Entrée: Deux fois en lecture des arbres de décision et . $A$ $B$
Sortie: Est-ce que ? $A \equiv B$

Motivation:

Ce problème est survenu alors que je regardais le problème d'équivalence de preuve (permutation des règles) d'un fragment de logique linéaire.

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

Ne pouvez-vous pas utiliser des diagrammes de décision binaires réduits? Edit: euh peut-être pas, vos variables ne sont pas ordonnées ...

Sylvain

@Kaveh Nope, cela se produit dans la théorie de la preuve: je regarde le problème d'équivalence de preuve (permutation des règles) d'un fragment de logique linéaire. Se résume à ce problème booléen. Comme je ne suis pas un spécialiste, j'ai pensé que je demanderais si jamais c'était une question bien connue / facile. Par conséquent, oui, j'ai inventé le nom parce que je ne sais pas mieux.

Marc

@Marc, c'est généralement une bonne idée d'expliquer pourquoi vous êtes intéressé par un problème. J'ai édité la question. Veuillez regarder pour vous assurer que tout va bien. (Supprimer également mes commentaires précédents car ils ne sont plus nécessaires.)

Kaveh

@Kaveh Ouais, désolé pour ça. J'ai modifié votre reformulation pour la rapprocher de mon argument d'origine (je ne pouvais pas comprendre immédiatement si le vôtre était OK, donc cela semblait plus facile à faire)

Marc

Réponses:

J'ai trouvé une solution partielle. Le problème est dans L.

La négation de est équivalente à qui est équivalente à si à la fois et sont. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

$\bar{A}$ $A$ $True$ $False$ $A$

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

Le problème est donc au moins en L.

$AC_0$

EDIT2: le voilà, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Donc, le problème est en effet Logspace-complet.

Marc
la source

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$

Une façon plus simple de le dire est la suivante: chaque chemin est un terme minimum ou maximum selon l'étiquette de sa feuille. Nous vérifions s'ils ont les mêmes termes min. Nous pouvons énumérer les termes min dans l'espace journal et vérifier si deux termes min sont identiques se trouve dans l'espace journal.

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
la source

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ah oui, j'ai oublié ça, j'ajoute un correctif en espérant que ça marche maintenant.

Denis

N'oubliez pas de réclamer votre million de dollars si cela fonctionne :)

Marc

L

$L$