10
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Is $\sim$ even known to be in Ptime? $\;$ $\endgroup$
    – user6973
    Commented Jul 6, 2015 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
    Commented Jul 6, 2015 at 19:46
  • 2
    $\begingroup$ @RickyDemer: Yes, ~ can be decided in polynomial time. $\endgroup$
    – William Hoza
    Commented Jul 6, 2015 at 23:32
  • $\begingroup$ Thank you Ricky Demer, I did not know a systematic approach to this question existed. $\endgroup$
    – Marc
    Commented Jul 8, 2015 at 7:24
  • $\begingroup$ Why would a "negative answer to this question" "provide a separation result $PEq \neq Ker$"? $\hspace{.49 in}$ $\endgroup$
    – user6973
    Commented Jul 16, 2015 at 13:39

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jul 8, 2015 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
    Commented Jul 8, 2015 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
    Commented Jul 13, 2015 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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