Article ID Journal Published Year Pages File Type
437682 Theoretical Computer Science 2015 17 Pages PDF
Abstract

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(log⁡s)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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,