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

  • 1
    $\begingroup$ Is $\sim$ even known to be in Ptime? $\;$ $\endgroup$ – user6973 Jul 6 '15 at 19:31
  • 1
    $\begingroup$ Independently of that, your question is equivalent to "Does $\sim$ have an FP canonical form?". $\hspace{.54 in}$ $\endgroup$ – user6973 Jul 6 '15 at 19:46
  • 2
    $\begingroup$ @RickyDemer: Yes, ~ can be decided in polynomial time. $\endgroup$ – William Hoza Jul 6 '15 at 23:32
  • $\begingroup$ Thank you Ricky Demer, I did not know a systematic approach to this question existed. $\endgroup$ – Marc Jul 8 '15 at 7:24
  • $\begingroup$ Why would a "negative answer to this question" "provide a separation result $PEq \neq Ker$"? $\hspace{.49 in}$ $\endgroup$ – user6973 Jul 16 '15 at 13:39

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, if I understand correctly.

| cite | improve this answer | |
  • $\begingroup$ I was only aware of "answer 2" from that post. Hence I started the same reasoning but got stuck along the way. $\endgroup$ – Marc Jul 8 '15 at 7:29
  • $\begingroup$ 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: researcher.watson.ibm.com/researcher/files/us-vitaly/… and do it. $\endgroup$ – Marc Jul 8 '15 at 7:39
  • 1
    $\begingroup$ I am afraid there is a problem with "answer 3" from this answer. I asked the author about it, but got no feedback. $\endgroup$ – Marc Jul 13 '15 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.