Representação canônica da árvore de decisão binária no Ptime?

10

Gostaria de saber se pode existir uma maneira de fornecer uma espécie de "forma normal" para árvores de decisão binária (BDT) de maneira tratável.

Mais precisamente: um BDT é uma árvore com nós internos rotulados por variáveis ​​booleanas e folhas rotuladas por 0 0 ou 1 1 . Um BDT representa uma função booleana da maneira óbvia. Dois BDT UMA,B são equivalentes ( UMAB ) quando representam a mesma função.

Existe uma função f que insere um BDT e o transforma em alguma outra estrutura de dados, como:

  1. está em Ptimef
  2. se e somente se A Bf(UMA)=f(B)UMAB
  3. tem um pseudo-inverso g , que é g ( f ( A ) ) A , também em Ptimefgg(f(UMA))UMA

Por exemplo, diagramas de decisões binárias ordenadas reduzidas, o OBDD valida 2 e 3, mas não 1, porque com a ordem incorreta da variável, a saída pode ter tamanho exponencial.

Sinto que isso pode não ser possível, mas não encontrei nenhuma evidência disso em nenhum lugar.


Para comentar ainda mais a sugestão de Ricky Demer:

Este documento define o (classes de equivalência em óptimos) e K e r as classes (invariante completa em óptimos) e CF (forma canónica em óptimos). Eles estudam várias implicações (improváveis) de P E Q = K e R e K e r = C F , mas não fornecem uma resposta definitiva a estas perguntas.PEqKerPEq=KerKer=CF

Vários respostas negativas (impossibilidade de 1 & 2, 1 & 2 & 3) para esta questão iria proporcionar resultados de separação como ou K e r C F ... que parece ser um problema até agora aberto.PEqKerKerCF

Marc
fonte
11
É mesmo conhecido por ser em óptimo?
11
Independentemente disso, sua pergunta é equivalente a "Does tem uma forma canônica FP ?".
2
@ RickyDemer: Sim, ~ pode ser decidido em tempo polinomial.
William Hoza
Obrigado Ricky Demer, eu não sabia que existia uma abordagem sistemática para essa pergunta.
Marc
Por que uma "resposta negativa a esta pergunta" "forneceria um resultado de separação "?PEqKer

Respostas:

9

Penso que, assumindo que , essa representação canônica não existe. Prova: suponha que essa representação canônica exista. Então a função A g ( f ( A ) ) = g ( f ( B ) ) , então | gNPSUBEXP pode ser calculada em tempo polinomial, portanto, em particular | g ( f ( A ) ) | é poli ( | A | ) . Mas se considerarmos B como um BDT mínimo equivalente a A , entãoAg(f(A))|g(f(A))|poly(|A|)BAg(f(A))=g(f(B))é poli ( | B | ) . Tal algoritmo de aproximação implica que N PS U B E X P , de acordo comuma resposta em outro post, se bem entendi.|g(f(A))|poly(|B|)NPSvocêBEXP

William Hoza
fonte
Eu só sabia da "resposta 2" desse post. Por isso, comecei o mesmo raciocínio, mas fiquei preso ao longo do caminho.
Marc
Seria bom encerrá-lo de forma autônoma. Vou tentar ler o artigo subjacente à reivindicação da postagem: researcher.watson.ibm.com/researcher/files/us-vitaly/… e fazê-lo.
Marc
11
Receio que exista um problema com a "resposta 3" desta resposta. Perguntei ao autor sobre o assunto, mas não obtive retorno.
Marc