Hardness results for approximate pure Horn CNF formulae minimization (Q2254607): Difference between revisions

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