Title:  Deciding the Kdimension is PSPACEcomplete 
Authors:  Marcus Schaefer 
Abstract:  In 1988 Littlestone introduced the optimal mistakebound
learning model to learning theory. In this model the difficulty of
learning a concept from a concept class is measured by the Kdimension
of the concept class, which is a purely combinatorial notion. This is
similar to the situation in PAClearning, where the difficulty of
learning can be measured by the VapnikCervonenkis dimension.We show
that determining the Kdimension of a concept class is a PSPACEcomplete
problem where the concept class is given as a circuit. This also
implies that any optimal learner (making the least number of mistakes)
that works on all concept classes over finite universes has to be
PSPACEhard.

Full Paper:  [ps] 