Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437682 | Theoretical Computer Science | 2015 | 17 Pages |
We study the complexity of isomorphism testing for boolean functions that are represented by decision trees or decision lists. Our results are the following:•Isomorphism testing of rank 1 decision trees is complete for logspace.•For any constant r≥2r≥2, isomorphism testing for rank r decision trees is polynomial-time equivalent to Graph Isomorphism. As a consequence of our reduction, we obtain our main result for decision trees: A 2n(logs)O(1) time algorithm for isomorphism testing of decision trees of size s over n variables.•The isomorphism problem for decision lists admits a Schaefer-type trichotomy: depending on the class of base functions, the isomorphism problem is either in LL, or polynomial-time equivalent to Graph Isomorphism, or coNPcoNP-hard.