# Canonical representation of binary decision trees in Ptime?

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:

1. $f$ is computable in Ptime
2. $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: 1. 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:

https://cstheory.stackexchange.com/questions/31918/canonical-representation-of-binary-decision-tree-in-ptime