10

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.

Marc
  • 686
  • 4
  • 12
  • 1
    Is $\sim$ even known to be in Ptime? $;$ –  Jul 06 '15 at 19:31
  • 1
    Independently of that, your question is equivalent to "Does $\sim$ have an FP canonical form?". $\hspace{.54 in}$ –  Jul 06 '15 at 19:46
  • 2
    @RickyDemer: Yes, ~ can be decided in polynomial time. – William Hoza Jul 06 '15 at 23:32
  • Thank you Ricky Demer, I did not know a systematic approach to this question existed. – Marc Jul 08 '15 at 07:24
  • Why would a "negative answer to this question" "provide a separation result $PEq \neq Ker$"? $\hspace{.49 in}$ –  Jul 16 '15 at 13:39
  • 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 Jul 16 '15 at 14:00
  • However, it's far from clear to me that the impossibility of fulfilling 1&2&3 implies $: PEq \neq Ker ;$. $::$ –  Jul 16 '15 at 14:26
  • 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 Jul 16 '15 at 15:57

1 Answers1

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

Community
  • 1
William Hoza
  • 1,733
  • 11
  • 23
  • I was only aware of "answer 2" from that post. Hence I started the same reasoning but got stuck along the way. – Marc Jul 08 '15 at 07:29
  • 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 Jul 08 '15 at 07:39
  • 1
    I am afraid there is a problem with "answer 3" from this answer. I asked the author about it, but got no feedback. – Marc Jul 13 '15 at 21:22