کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437682 | 690174 | 2015 | 17 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 590, 26 July 2015, Pages 38–54