Kanoniczna reprezentacja binarnego drzewa decyzyjnego w czasie?

Zastanawiam się, czy może istnieć sposób na nadanie pewnego rodzaju „normalnej formy” binarnym drzewom decyzyjnym (BDT) w sposób możliwy do wdrożenia.

Mówiąc dokładniej: BDT jest drzewem z wewnętrznymi węzłami oznaczonymi zmiennymi logicznymi i liśćmi oznaczonymi przez lub . BDT reprezentuje funkcję logiczną w oczywisty sposób. Dwa BDT są równoważne ( A \ sim B ), jeśli reprezentują tę samą funkcję.1 A , B A ∼ $0$$1$$A,B$$A\sim B$

Czy istnieje funkcja $f$ która wprowadza BDT i przekształca ją w inną strukturę danych, taką jak:

1. $f$ jest w czasie Ptime
2. $f(A)=f(B)$ wtedy i tylko wtedy, gdy $A\sim B$
3. $f$ ma pseudo-odwrotność $g$ , czyli $g(f(A))\sim A$ , również w Ptime

Na przykład zmniejszone uporządkowane binarne diagramy decyzyjne OBDD sprawdzają poprawność 2 i 3, ale nie 1, ponieważ przy niewłaściwym uporządkowaniu zmiennej wyjście może mieć rozmiar wykładniczy.

Mam wrażenie, że może to nie być możliwe, ale nigdzie nie znalazłem na to dowodów.

Aby skomentować dalej sugestię Ricky Demer:

W tym dokumencie zdefiniowano klasy (klasy równoważności w Ptime) i (całkowity niezmiennik w Ptime) i CF (forma kanoniczna w Ptime). różne (mało prawdopodobne) implikacje i ale nie podają jednoznacznej odpowiedzi na te pytania.K e r P E q = K e r K e r = C $PEq$$Ker$$PEq=Ker$$Ker=CF$

Różne negatywne odpowiedzi (niemożność 1 i 2, 1 i 2 i 3) na to pytanie przyniosłyby wyniki separacji jako lub ... co wydaje się jak dotąd otwartym problemem.K e r ≠ C $PEq\neq Ker$$Ker\neq CF$

Myślę, że przy założeniu, że , taka reprezentacja kanoniczna nie istnieje. Dowód: załóżmy, że taka reprezentacja kanoniczna istnieje. Następnie funkcję można obliczyć w czasie wielomianowym, a więc w szczególnościto . Ale jeśli weźmiemy jako minimalną wartość BDT równoważną , to , więcto . Taki algorytm aproksymacji implikuje, że , zgodnie z odpowiedzią na inny post , jeśli dobrze rozumiem. A ↦ g ( f ( A ) ) | g ( f ( A ) ) | poli ( | A | ) B A g ( f ( A ) ) = g ( f ( B ) ) | g ( f ( A ) ) | poli $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$$A \mapsto g(f(A))$$|g(f(A))|$$\text{poly}(|A|)$$B$$A$$g(f(A)) = g(f(B))$$|g(f(A))|$$\text{poly}(|B|)$$\mathsf{NP} \subseteq \mathsf{SUBEXP}$