# Canonical representation of Binary Decision Tree in Ptime?

I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.

More precisely: a BDT is a tree with internal nodes labelled by boolean variables and leaves labelled by $0$ or $1$. A BDT represents a boolean function in the obvious way. Two BDT $A,B$ are equivalent ($A\sim B$) when they represent the same function.

Does there exist a function $f$ that inputs a BDT and turns it into some other data structure such that:

1. $f$ is in Ptime
2. $f(A)=f(B)$ if and only if $A\sim B$
3. $f$ has a pseudo-inverse $g$, that is $g(f(A))\sim A$, also in Ptime

For instance reduced ordered binary decision diagrams OBDD validate 2 and 3, but not 1 because with the wrong variable ordering the output might be of exponential size.

I have a feeling that this might not be possible, but have not found any evidence of that anywhere.

To comment further on Ricky Demer's suggestion:

This paper defines the $PEq$ (equivalence classes in Ptime) and $Ker$ (complete invariant in Ptime) and CF (canonical form in Ptime) classes. They study various (unlikely) implications of $PEq=Ker$ and $Ker=CF$ but do not provide a definite answer to these questions.

Various negative answers (impossibility of 1&2, 1&2&3) to this question would provide separation results as $PEq\neq Ker$ or $Ker\neq CF$... which seems to be an open problem so far.

• Is $\sim$ even known to be in Ptime? $\;$ – user6973 Jul 6 '15 at 19:31
• Independently of that, your question is equivalent to "Does $\sim$ have an FP canonical form?". $\hspace{.54 in}$ – user6973 Jul 6 '15 at 19:46
• @RickyDemer: Yes, ~ can be decided in polynomial time. – William Hoza Jul 6 '15 at 23:32
• Thank you Ricky Demer, I did not know a systematic approach to this question existed. – Marc Jul 8 '15 at 7:24
• Why would a "negative answer to this question" "provide a separation result $PEq \neq Ker$"? $\hspace{.49 in}$ – user6973 Jul 16 '15 at 13:39

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $A$, then $g(f(A)) = g(f(B))$, so $|g(f(A))|$ is $\text{poly}(|B|)$. Such an approximation algorithm implies that $\mathsf{NP} \subseteq \mathsf{SUBEXP}$, according to an answer on another post, if I understand correctly.