Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492876zbMATH OpenOpenAlexFDO

Authors J. Goldsmith, Matthias Hagen, Martin Mundhenk

Publication date 20 October 2006

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

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of DNF minimization and isomorphism testing for monotone formulas
• Evaluation of monotone DNF formulas
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the incompressibility of monotone DNFs
• Fundamentals of Computation Theory
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• On DNF approximators for monotone Boolean functions
• Discovery Science
• On a relation between the depth and complexity of monotone Boolean formulas
• The complexity of DNF of parities

Cited in

(13)

• On the fixed-parameter tractability of the equivalence test of monotone normal forms
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments
• On k-Term DNF with the Largest Number of Prime Implicants
• scientific article; zbMATH DE number 3978379 (Why is no real title available?)
• scientific article; zbMATH DE number 4047104 (Why is no real title available?)
• Adventures in monotone complexity and TFNP
• On DNF approximators for monotone Boolean functions
• On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
• Discovery Science
• An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
• On computing probabilistic explanations for decision trees
• Complexity of DNF minimization and isomorphism testing for monotone formulas

This page was built for publication: Mathematical Foundations of Computer Science 2005

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