Nov 2, 12:00, WeH 1327 NP-Completeness of Searches for Smallest Consistent Feature Sets Scott Davies (*) In many learning problems, the learning system is presented with values for features that are actually irrelevant to the concept it is trying to learn. The FOCUS algorithm, due to Almuallim and Dietterich, performs an explicit search for the smallest possible input feature set S that permits a consistent mapping from the features in S to the output feature. The FOCUS algorithm has superpolynomial runtime, but Almuallim and Dietterich leave open the question of tractability of the underlying problem. We will show that the underlying problem is NP-complete. We will also describe briefly some experiments that demonstrate the benefits of using smallest possible feature sets. (*) joint work with Stuart Russell