Hardness results for approximate pure Horn CNF formulae minimization

DOI10.1007/s10472-014-9415-9zbMath1320.68089arXiv1204.3529OpenAlexW2155269751WikidataQ59560498 ScholiaQ59560498MaRDI QIDQ2254607

Endre Boros, Aritanan Gruber

Publication date: 5 February 2015

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.3529

zbMATH Keywords

computational complexityartificial intelligenceBoolean functionshardness of approximationpropositional Horn logic

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (7)

A decomposition method for CNF minimality proofs ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Hydras: complexity on general graphs and a subclass of trees ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ On the hydra number of disconnected graphs ⋮ Approximating Minimum Representations of Key Horn Functions

Uses Software

• JBool
• Ltur

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition method for CNF minimality proofs
• Exclusive and essential sets of implicates of Boolean functions
• On the hardness of approximating label-cover
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Horn functions and their DNFs
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Hardness results for approximate pure Horn CNF formulae minimization
• The Design of Approximation Algorithms
• Proof verification and the hardness of approximation problems
• Two-query PCP with subconstant error
• On Approximate Horn Formula Minimization
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimal Representation of Directed Hypergraphs
• Unification as a complexity measure for logic programming
• Probabilistic checking of proofs
• Minimum Covers in Relational Database Model
• Interactive proofs and the hardness of approximating cliques
• Computational Complexity
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• The complexity of theorem-proving procedures
• On the complexity of \(k\)-SAT
• On the hardness of approximating spanners

This page was built for publication: Hardness results for approximate pure Horn CNF formulae minimization