Homomorphisms of conjunctive normal forms.

DOI10.1016/S0166-218X(02)00411-0zbMATH Open1033.68095MaRDI QIDQ1408387FDOQ1408387

Authors: Stefan Szeider 

Publication date: 15 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 2165693
• Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.
• The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
• The complexity of resolution with generalized symmetry rules
• scientific article; zbMATH DE number 1962837

zbMATH Keywords

unsatisfiable formulasunsatisfiability\(p\)-simulation

Mathematics Subject Classification ID

Computability and recursion theory (03D99)

Cites Work

• The complexity of facets resolved
• Title not available (Why is that?)
• The relative efficiency of propositional proof systems
• The Complexity of Propositional Proofs
• Solving satisfiability in less than \(2^ n\) steps
• The intractability of resolution
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• Short proofs for tricky formulas
• Investigations on autark assignments
• A perspective on certain polynomial-time solvable classes of satisfiability
• Tractability through symmetries in propositional calculus
• Theorem-Proving for Computers: Some Results on Resolution and Renaming
• The symmetry rule in propositional logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• Formula simplification via invariance detection by algebraically indexed types
• The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Disproof of the neighborhood conjecture with implications to SAT
• The Lovász Local Lemma and Satisfiability
• Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable

This page was built for publication: Homomorphisms of conjunctive normal forms.

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