Worst case bounds for some NP-complete modified Horn-SAT problems

DOI10.1007/11527695_20MaRDI 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

(hidden) Horn formulafixed-parameter tractabilityminimal vertex coverNP-completenessquadratic formulasatisfiability

Mathematics Subject Classification ID

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

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)

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

Describes a project that uses

Uses Software

• Ltur
• BerkMin

This page was built for publication: Worst case bounds for some NP-complete modified Horn-SAT problems

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