Abstract.
We study the computational power of decision lists over AND-functions versus \( \hbox{threshold-}\oplus \) circuits. AND-decision lists are a natural generalization of formulas in disjunctive or conjunctive normal form. We show that, in contrast to CNF- and DNF-formulas, there are functions with small AND-decision lists which need exponential size unbounded weight \(\hbox{threshold-}\oplus \) circuits. Consequently, it is questionable if the polynomial learning algorithm for DNFs of Jackson (1994), which is based on the efficient simulation of DNFs by polynomial weight \( \hbox{threshold-}\oplus \) circuits (Krause & Pudlák 1994), can be successfully applied to functions with small AND-decision lists. A further result is that for all k ≥ 1 the complexity class defined by polynomial length AC 0 k -decision lists lies strictly between AC 0 k+1 and AC 0 k+2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Manuscript received 18 November 2003
Rights and permissions
About this article
Cite this article
Krause, M. On the computational power of Boolean decision lists. comput. complex. 14, 362–375 (2006). https://doi.org/10.1007/s00037-005-0203-0
Issue Date:
DOI: https://doi.org/10.1007/s00037-005-0203-0