I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.

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∼B) when they represent the same function (this equivalence is can be decided in Ptime).

A Ptime representation of BDTs is a function $f$ that inputs a BDT and turns it into another data structure/mathematical object, such that:

- $f$ is computable in Ptime
- $A\sim B$ if and only if $f(A)=f(B)

Additionally, we may require that we have a way to reconstruct a BDT from a representation:

- there is a function $g$, also computable in Ptime, such that $g(f(A))\sim A$

The question is

```
Can a Ptime representation of BDT exist?
```

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 looked up the literature but did not find a complete answer to this question (see below).

An element of answer I have: if we moreover assume that the *size* of the objects produced by $f$ and $g$ is linear in the size of the input, we get that $g(f(A))$ produces a constant factor approximation of the smallest BDT equivalent to $A$, which is impossible unless P=NP.

Can we say anything more general, is it something already known?

This question was asked on cstheory.stackexchange:

but the answer it got there is not satisfactory: the answer relies on a claim in another post which is not well justified. I asked the author about this but got no satisfactory answer: (answer 3 and comments)

https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees/7963#7963