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:


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)


  • 1
    $\begingroup$ Cross-posted from cstheory.stackexchange.com/q/31918 , where it already got a conditional negative answer. $\endgroup$ – Emil Jeřábek Jul 13 '15 at 17:54
  • $\begingroup$ The answer posted there relies on an other answer with an argumentation gap not addressed by its author. $\endgroup$ – Marc Jul 13 '15 at 21:21
  • $\begingroup$ 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. $\endgroup$ – Stefan Kohl Oct 10 '15 at 10:41
  • $\begingroup$ 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? $\endgroup$ – Marc Oct 14 '15 at 20:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.