¿Cuál es la complejidad del problema de equivalencia para los árboles de decisión de lectura única?

Un árbol de decisión de lectura única se define de la siguiente manera:

y son árboles de decisión de una sola lectura. $True$ $False$
Si y son árboles de decisión de lectura única es una variable que no ocurre en y , entonces también es un árbol de decisión de lectura única. $A$ $B$ $x$ $A$ $B$ $(x \land A) \lor (\bar x \land B)$

Entrada: Dos lectura una vez que los árboles de decisión y . $A$ $B$
Salida: ¿Es ? $A \equiv B$

Motivación:

Este problema surgió mientras miraba el problema de equivalencia de prueba (permutación de reglas) de un fragmento de lógica lineal.

cc.complexity-theory lo.logic decision-trees boolean-formulas Bagazo
fuente

¿No puedes usar diagramas de decisión binarios reducidos? Editar: err tal vez no, sus variables no están ordenadas ...

Sylvain

@Kaveh No, ocurre en la teoría de la prueba: estoy mirando el problema de equivalencia de prueba (permutación de reglas) de un fragmento de lógica lineal. Se reduce a este problema booleano. Como no soy especialista, pensé en preguntar si alguna vez fue una pregunta bien conocida / fácil. Por lo tanto, sí, inventé el nombre porque no sé nada mejor.

Marc

@Marc, generalmente es una buena idea explicar por qué está interesado en un problema. Edité la pregunta. Eche un vistazo para asegurarse de que esté bien. (También elimino mis comentarios anteriores ya que ya no son necesarios.)

Kaveh

@Kaveh Sí, lo siento por eso. Edité su reformulación para acercarla a mi argumento original (no pude calcular de inmediato si la suya estaba bien, así que parecía más fácil hacer esto)

Marc

Respuestas:

Encontré una solución parcial. El problema está en L.

La negación de es equivalente a que es equivalente a si ambos y son. $A \leftrightarrow B$ $(\bar A \land B) \lor (A \land \bar{B})$ $False$ $(\bar A \land B)$ $(A \land \bar{B})$

El árbol de decisión para una vez leído- puede obtenerse a partir del árbol de decisión de lectura una vez por por conmutación y en . Esto se puede hacer en el espacio de registro. $\bar{A}$ $A$ $True$ $False$ $A$

Para verificar si es equivalente a (y de manera similar para ) revisamos todos los pares de hojas de , una de cada árbol, y verificamos si son compatibles (eso es que no hay en una de las rutas y en la otra). Es equivalente a si no encontramos un par compatible. Esto se puede hacer en el espacio de registro. $\bar A \land B$ $False$ ${A} \land \bar{B}$ $True$ $x$ $\bar x$ $False$

Entonces el problema es al menos en L.

EDITAR: Tengo algunas ideas para demostrar que esto es L-completo, probablemente bajo la reducción . Pero necesitaría verificar los detalles y no encajará aquí. ¡Publicaré un enlace al artículo que estoy escribiendo si todo funciona! $AC_0$

EDIT2: ahí está, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

Entonces, el problema es Logspace-complete.

Bagazo
fuente

¿Cómo se obtiene esta negación? La negación de

debería ser

, es decir,

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: Creo que esto fue un error tipográfico, su fórmula se simplifica a

, entonces la negación se calcula volteando el 0 y el 1 en las hojas.

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$

Una forma más fácil de decir esto es: cada ruta es un término mínimo o un término máximo dependiendo de la etiqueta de su hoja. Verificamos si tienen los mismos términos mínimos. Podemos enumerar los términos mínimos en el espacio logarítmico y verificar si dos términos mínimos son iguales en el espacio logarítmico.

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
fuente

x, y, z

$x,y,z$

x, \bar{y}, z

$x,\bar y,z$

x, y, \bar{z}

$x,y,\bar z$

Ah sí, lo olvidé, estoy agregando una solución esperando que funcione ahora.

Denis

No te olvides de reclamar tu millón de dólares si funciona :)

Marc

L

$L$