Finding a Minimal 1-DNF Consistent with a Positive Sample is LOGSNP-Complete

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.