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:
- $f$ is in Ptime
- $f(A)=f(B)$ if and only if $A\sim B$
- $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.