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

François Denis

Published in: Inf. Process. Lett. (1999)

Keyphrases

learning algorithm
positive and negative
theoretical analysis
uniform distribution
sample size
positive samples
special case
learning problems
sample points
noise tolerant
positively correlated