Efficient Parallel Learning in Classifier Systems

Classifier systems are simple production systems working on binary messages of a fixed length. Genetic algorithms are employed in classifier systems in order to discover new classifiers. We use methods of the computational complexity theory in order to analyse the inherent difficulty of learning in classifier systems. Hence our results do not depend on special (possibly genetic) learning algorithms. The paper formalises this rule discovery or learning problem for classifier systems which has been proved to be hard in general. It will be proved that restrictions on two distinct learning problems lead to problems in NC, i.e. problems which are efficiently solvable in parallel.