Theory and Applications of Satisfiability Testing

DOI10.1007/11527695zbMATH Open1122.68614OpenAlexW2483910514MaRDI QIDQ5714756FDOQ5714756

Authors: Stefan Porschen, Ewald Speckenmeyer 

Publication date: 16 December 2005

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

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

Recommendations

• Satisfiability of mixed Horn formulas
• On Some Aspects of Mixed Horn Formulas
• Simple but hard mixed Horn formulas
• On the complexity of the maximum satisfiability problem for Horn formulas
• Satisfiability on mixed instances

zbMATH Keywords

NP-completenessfixed-parameter tractabilitysatisfiabilityquadratic formula(hidden) Horn formulaminimal vertex cover

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (7)

• Satisfiability of mixed Horn formulas
• Simple but hard mixed Horn formulas
• Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
• On the complexity of the maximum satisfiability problem for Horn formulas
• SAT-Based Horn Least Upper Bounds
• On Some Aspects of Mixed Horn Formulas
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors

Uses Software

• BerkMin
• Ltur

This page was built for publication: Theory and Applications of Satisfiability Testing

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