Author: François Denis
Source: Information Processing Letters Vol. 69, No. 1, 1999, 1 - 5.
Abstract. In the learning from positive examples framework, finding minimal concepts consistent with a given positive sample is a natural way to avoid over-generalization. We show in this paper that finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete. We use random number generator techniques to prove this result.
©Copyright 1999, Elsevier Science, All rights reserved.