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 ( ), jeśli reprezentują tę samą funkcję. $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:

$f$ jest w czasie Ptime
$f(A)=f(B)$ wtedy i tylko wtedy, gdy $A\sim B$
$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. $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. $PEq\neq Ker$ $Ker\neq CF$

cc.complexity-theory decision-trees

— Marc
źródło

Czy wiadomo, że jest w Ptime?

\sim

$\sim$

$\;$

Niezależnie od tego twoje pytanie jest równoważne z „Czy ma kanoniczną postać FP ?”.

\sim

$\sim$

$\hspace{.54 in}$

@RickyDemer: Tak, ~ można określić w czasie wielomianowym.

— William Hoza,

Dziękuję Ricky Demer, nie wiedziałem, że istnieje systematyczne podejście do tego pytania.

— Marc

Dlaczego „negatywna odpowiedź na to pytanie” „zapewnia wynik separacji ”?

P E q \neq K e r

$PEq \neq Ker$

$\hspace{.49 in}$

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. $\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}$

— William Hoza
źródło

Byłem świadomy „odpowiedzi 2” z tego postu. Dlatego zacząłem to samo rozumowanie, ale utknąłem po drodze.

— Marc

Dobrze byłoby jednak zakończyć to w sposób autonomiczny. Spróbuję przeczytać artykuł leżący u podstaw roszczenia posta: researchcher.watson.ibm.com/researcher/files/us-vitaly/... i zrób to.

— Marc

Obawiam się, że istnieje problem z „odpowiedzią 3” z tej odpowiedzi. Zapytałem o to autora, ale nie otrzymałem żadnej opinii.

— Marc