On the complexity and inapproximability of shortest implicant problems

DOI10.1007/3-540-48523-6_65MaRDI QIDQ4938653zbMATH OpenFDO

Authors Christopher Umans

Publication date 23 February 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48523-6_65

zbMATH Keywords

approximabilityBoolean functionscircuit minimizationcomplexityoptimizationpolynomial hierarchyshortest implicants

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The minimum equivalent DNF problem and shortest implicants
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• Boolean functions with long prime implicants
• Complexity of finding short resolution proofs
• Hardness of approximate two-level logic minimization and PAC learning with membership queries

Cited in

(10)

• Approximability of minimum AND-circuits
• The minimum equivalent DNF problem and shortest implicants
• Belief functions and rough sets: survey and new insights
• Uncertainty representation in dynamical systems using rough set theory
• Rough set-based feature selection for weakly labeled data
• Boolean functions with long prime implicants
• Feature selection and disambiguation in learning from fuzzy labels using rough sets
• Complexity of finding short resolution proofs
• Approximability of Minimum AND-Circuits
• Information Acquisition Under Resource Limitations in a Noisy Environment

This page was built for publication: On the complexity and inapproximability of shortest implicant problems

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