Title: Deciding the K-dimension is PSPACE-complete
Published: March 2000
Authors: Marcus Schaefer
Abstract: In 1988 Littlestone introduced the optimal mistake-bound learning model to learning theory. In this model the difficulty of learning a concept from a concept class is measured by the K-dimension of the concept class, which is a purely combinatorial notion. This is similar to the situation in PAC-learning, where the difficulty of learning can be measured by the Vapnik-Cervonenkis dimension.We show that determining the K-dimension of a concept class is a PSPACE-complete 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 PSPACE-hard.
Full Paper: [postscript]