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

DOI10.1016/S0020-0190(98)00185-9zbMATH Open1339.68131OpenAlexW2043133719MaRDI QIDQ294591FDOQ294591

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

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

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)

Cites Work

• Simple Constructions of Almost k-wise Independent Random Variables
• Title not available (Why is that?)
• Title not available (Why is that?)
• PAC learning with simple examples

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)