¿Representación canónica del árbol de decisión binario en Ptime?

10

Me pregunto si puede existir una forma de dar una especie de "forma normal" para los árboles de decisión binarios (BDT) de forma manejable.

Más precisamente: una BDT es un árbol con nodos internos etiquetados por variables booleanas y hojas etiquetadas por o . Una BDT representa una función booleana de la manera obvia. Dos BDT son equivalentes ( ) cuando representan la misma función.1 A , B A B01A,BAB

¿Existe una función que ingrese una BDT y la convierta en alguna otra estructura de datos tal que:f

  1. f está en Ptime
  2. f(A)=f(B) si y solo siAB
  3. f tiene un pseudo-inverso , es decir , también en Ptimeg ( f ( A ) ) Agg(f(A))A

Por ejemplo, los diagramas de decisión binarios ordenados reducidos OBDD validan 2 y 3, pero no 1 porque con el orden incorrecto de la variable la salida puede ser de tamaño exponencial.

Tengo la sensación de que esto podría no ser posible, pero no he encontrado ninguna evidencia de eso en ningún lado.


Para comentar más sobre la sugerencia de Ricky Demer:

Este artículo define las clases (clases de equivalencia en Ptime) y (invariante completo en Ptime) y CF (forma canónica en Ptime). Estudian varias implicaciones (poco probables) de y pero no proporcionan una respuesta definitiva a estas preguntas.K e r P E q = K e r K e r = C FPEqKerPEq=KerKer=CF

Varias respuestas negativas (imposibilidad de 1 y 2, 1 y 2 y 3) a esta pregunta proporcionarían resultados de separación como o K e r C F ... que hasta ahora parece ser un problema abierto.PEqKerKerCF

Bagazo
fuente
1
¿Se sabe que está en Ptime?
1
Independientemente de ello, su pregunta es equivalente a "no tiene una forma canónica FP ?".
2
@RickyDemer: Sí, ~ se puede decidir en tiempo polinómico.
William Hoza
Gracias Ricky Demer, no sabía que existía un enfoque sistemático para esta pregunta.
Marc
¿Por qué una "respuesta negativa a esta pregunta" "proporcionaría un resultado de separación "?PEqKer

Respuestas:

9

A g ( f ( A ) ) | g ( f ( A ) ) | poli ( | A | ) B A g ( f ( A ) ) = g ( f ( B ) ) | g ( f ( A ) ) | poli (NPSUBEXPAg(f(A))|g(f(A))|poly(|A|)BAg(f(A))=g(f(B))|g(f(A))|N PS U B E X Ppoly(|B|)NPSUBEXP

William Hoza
fuente
Solo estaba al tanto de la "respuesta 2" de esa publicación. Por lo tanto, comencé el mismo razonamiento pero me quedé atrapado en el camino.
Marc
Sin embargo, sería bueno concluirlo de manera autónoma. Intentaré leer el artículo subyacente al reclamo de la publicación: investigcher.watson.ibm.com/researcher/files/us-vitaly/… y hacerlo.
Marc
1
Me temo que hay un problema con la "respuesta 3" de esta respuesta. Le pregunté al autor al respecto, pero no obtuve comentarios.
Marc