Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete

DOI10.1016/S0020-0190(98)00185-9MaRDI QIDQ294591zbMATH OpenOpenAlexFDO

Authors François Denis

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001859?np=y

zbMATH Keywords

computational complexityalgorithmic learning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Three \(\sum^ P_ 2\)-complete problems in computational learning theory
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• scientific article; zbMATH DE number 4092808

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1301789 (Why is no real title available?)
• PAC learning with simple examples
• Simple Constructions of Almost k-wise Independent Random Variables

This page was built for publication: Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294591)