On the Isomorphism Problem for Decision Trees and Decision Lists

摘要

We study the complexity of isomorphism testing for Boolean functions that are represented by decision trees or decision lists. Our results include a 2 s~(1/2)(ls s)~(O(1)) time algorithm for isomorphism testing of decision trees of size s. Additionally, we show:1. Isomorphism testing of rank-1 decision trees is complete for logspace.2. For r ≥ 2, isomorphism testing for rank-r decision trees is polynomial-time equivalent to Graph Isomorphism. As a consequence we obtain a 2 s~(1/2)(lg s)~(O(1)) time algorithm for isomorphism testing of decision trees of size s.3. The isomorphism problem for decision lists admits a Schaefer-type dichotomy: depending on the class of base functions, the isomorphism problem is either in polynomial time, or equivalent to Graph Isomorphism, or coNP-hard.