Theory and Applications of Satisfiability Testing

DOI10.1007/11527695MaRDI QIDQ5714756zbMATH OpenOpenAlexFDO

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

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)

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

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

Describes a project that uses

Uses Software

• Ltur
• BerkMin

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)