<p>I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $A$, then $g(f(A)) = g(f(B))$, so $|g(f(A))|$ is $\text{poly}(|B|)$. Such an approximation algorithm implies that $\mathsf{NP} \subseteq \mathsf{SUBEXP}$, according to <a href="https://cstheory.stackexchange.com/a/7963/34371">an answer on another post</a>, if I understand correctly.</p>

CC BY-SA 3.0
2015-07-13T21:22:42.430Z
I am afraid there is a problem with "answer 3" from this answer. I asked the author about it, but got no feedback.
Marc
CC BY-SA 3.0
2015-07-08T07:29:57.183Z
I was only aware of "answer 2" from that post. Hence I started the same reasoning but got stuck along the way.
Marc
CC BY-SA 3.0
2015-07-08T07:39:11.247Z
It would be good to wrap it up in an autonomous way though. I'll try to read the article underlying the post's claim:
http://researcher.watson.ibm.com/researcher/files/us-vitaly/ABFKP_Proper_Hardness_08.pdf
and do it.
Marc
CC BY-SA 3.0
2015-07-07T00:07:29.400Z
2015-07-07T20:04:43.370Z
2017-04-13T12:32:28.167Z
William Hoza
<p>I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.</p>

<p>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\sim B$) when they represent the same function.</p>

<p>Does there exist a function $f$ that inputs a BDT and turns it into some other data structure such that:</p>

<ol>
<li>$f$ is in Ptime</li>
<li>$f(A)=f(B)$ if and only if $A\sim B$</li>
<li>$f$ has a pseudo-inverse $g$, that is $g(f(A))\sim A$, also in Ptime</li>
</ol>

<p>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.</p>

<p>I have a feeling that this might not be possible, but have not found any evidence of that anywhere.</p>

<hr>

<p>To comment further on Ricky Demer's suggestion:</p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/equiv.pdf" rel="nofollow">This paper</a> defines the $PEq$ (equivalence classes in Ptime) and $Ker$ (complete invariant in Ptime)  and CF (canonical form in Ptime) classes. They study various (unlikely) implications of $PEq=Ker$ and $Ker=CF$ but do not provide a definite answer to these questions.</p>

<p>Various negative answers (impossibility of 1&amp;2, 1&amp;2&amp;3) to this question would provide separation results as $PEq\neq Ker$ or $Ker\neq CF$... which seems to be an open problem so far.</p>

CC BY-SA 3.0
2015-07-16T14:00:14.793Z
The equivalence of BDT $\sim$ is in $PEq$. So if it is not in $Ker$ (ie. it is impossible to find $f$ fulfilling 1,2) we have an example of an equivalence relation living in $PEq\setminus Ker$. If we can fulfil 1,2 but not 3 then it is in $Ker\setminus CF$ ($CF$ being the class with canonical forms, stronger than invariants) etc.
Marc
CC BY-SA 3.0
2015-07-16T15:57:18.557Z
I agree, that was confusing, sorry. Either way I'd be also interested in an impossibility for only 1&2. And $Ker\neq CF$ is also left open at the end of their article.
Marc
CC BY-SA 3.0
2015-07-06T23:32:34.753Z
@RickyDemer: Yes, ~ [can be decided in polynomial time.](http://www.cs.uu.nl/research/techreps/repo/CS-1998/1998-14.pdf)
William Hoza
CC BY-SA 3.0
2015-07-08T07:24:45.680Z
Thank you Ricky Demer, I did not know a systematic approach to this question existed.
Marc
<cc.complexity-theory><decision-trees>
Canonical representation of Binary Decision Tree in Ptime?
Marc
# Canonical representation of Binary Decision Tree in Ptime?

(Asked by: username_0 on 2015-07-06)

I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.

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\sim B$) when they represent the same function.

Does there exist a function $f$ that inputs a BDT and turns it into some other data structure such that:

1. $f$ is in Ptime
2. $f(A)=f(B)$ if and only if $A\sim B$
3. $f$ has a pseudo-inverse $g$, that is $g(f(A))\sim A$, also in Ptime

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 have a feeling that this might not be possible, but have not found any evidence of that anywhere.

---

To comment further on Ricky Demer's suggestion:

[This paper](http://people.cs.uchicago.edu/~fortnow/papers/equiv.pdf) defines the $PEq$ (equivalence classes in Ptime) and $Ker$ (complete invariant in Ptime) and CF (canonical form in Ptime) classes. They study various (unlikely) implications of $PEq=Ker$ and $Ker=CF$ but do not provide a definite answer to these questions.

Various negative answers (impossibility of 1&2, 1&2&3) to this question would provide separation results as $PEq\neq Ker$ or $Ker\neq CF$... which seems to be an open problem so far.

**Tags:** cc.complexity-theory, decision-trees
> **Comments:**
> **username_1**: @RickyDemer: Yes, ~ [can be decided in polynomial time.](http://www.cs.uu.nl/research/techreps/repo/CS-1998/1998-14.pdf)  
> **username_0**: Thank you Ricky Demer, I did not know a systematic approach to this question existed.  
> **username_0**: The equivalence of BDT $\sim$ is in $PEq$. So if it is not in $Ker$ (ie. it is impossible to find $f$ fulfilling 1,2) we have an example of an equivalence relation living in $PEq\setminus Ker$. If we can fulfil 1,2 but not 3 then it is in $Ker\setminus CF$ ($CF$ being the class with canonical forms, stronger than invariants) etc.  
> **username_0**: I agree, that was confusing, sorry. Either way I'd be also interested in an impossibility for only 1&2. And $Ker\neq CF$ is also left open at the end of their article.  

---

## 1 answers

### Answer by username_1 on 2015-07-07. Score: 9

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $A$, then $g(f(A)) = g(f(B))$, so $|g(f(A))|$ is $\text{poly}(|B|)$. Such an approximation algorithm implies that $\mathsf{NP} \subseteq \mathsf{SUBEXP}$, according to [an answer on another post](https://cstheory.stackexchange.com/a/7963/34371), if I understand correctly.

> **Comments:**
> **username_0**: I was only aware of "answer 2" from that post. Hence I started the same reasoning but got stuck along the way.  
> **username_0**: It would be good to wrap it up in an autonomous way though. I'll try to read the article underlying the post's claim: http://researcher.watson.ibm.com/researcher/files/us-vitaly/ABFKP_Proper_Hardness_08.pdf and do it.  
> **username_0**: I am afraid there is a problem with "answer 3" from this answer. I asked the author about it, but got no feedback.  

---

