Theory and Applications of Satisfiability Testing

DOI10.1007/11527695zbMath1122.68614OpenAlexW2483910514MaRDI QIDQ5714756

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-completenesssatisfiabilityfixed-parameter tractabilityquadratic 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)

Related Items (3)

A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors ⋮ Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances ⋮ Satisfiability of mixed Horn formulas

Uses Software

• BerkMin
• Ltur

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