1
$\begingroup$

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:

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)

Lev Reyzin's answer to 'Algorithm for optimizing decision trees'

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Cross-posted from cstheory.stackexchange.com/q/31918 , where it already got a conditional negative answer. $\endgroup$ Commented Jul 13, 2015 at 17:54
  • $\begingroup$ The answer posted there relies on an other answer with an argumentation gap not addressed by its author. $\endgroup$ Commented Jul 13, 2015 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$ Commented Oct 10, 2015 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$ Commented Oct 14, 2015 at 20:20

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.