# 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

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

• Cross-posted from cstheory.stackexchange.com/q/31918 , where it already got a conditional negative answer. – Emil Jeřábek Jul 13 '15 at 17:54
• The answer posted there relies on an other answer with an argumentation gap not addressed by its author. – Marc Jul 13 '15 at 21:21
• Firstly, you should provide a reference to the cstheory.SE version of your question, and describe here why you are not satisfied by the answer you got there; secondly, you might consider adding a top-level- / arXiv tag to increase visibility of this question. – Stefan Kohl Oct 10 '15 at 10:41
• I edited the question with link on the version in cstheory. But I can't put cs.CC (the arXiv tag for complexity) in the list of MO. Am I doing it wrong? – Marc Oct 14 '15 at 20:20