caa a22 4500 467909733 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060301xx s 000 0 eng 10.1007/s00037-005-0203-0 doi (NATIONALLICENCE)springer-10.1007/s00037-005-0203-0 Krause Matthias Lehrstuhl Theoretische Informatik, Universität Mannheim, 68131, Mannheim, Germany aut On the computational power of Boolean decision lists [Elektronische Daten] [Matthias Krause] 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 AC0k-decision lists lies strictly between AC0k+1 and AC0k+2. Birkhäuser Verlag, Basel, 2005 Decision lists nationallicence AC 0 nationallicence learnability nationallicence lower bounds nationallicence 68Q15 nationallicence 94C05 nationallicence 94C10 nationallicence 06E30 nationallicence computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 362-375 1016-3328 14:4<362 2006 14 37 https://doi.org/10.1007/s00037-005-0203-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-005-0203-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Krause Matthias Lehrstuhl Theoretische Informatik, Universität Mannheim, 68131, Mannheim, Germany aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 14/4(2006-03-01), 362-375 1016-3328 14:4<362 2006 14 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer