On Some Aspects of Mixed Horn Formulas

DOI10.1007/978-3-642-02777-2_11MaRDI QIDQ3637161zbMATH OpenOpenAlexFDO

Authors Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer

Publication date 7 July 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-02777-2_11

zbMATH Keywords

exact algorithmmixed Horn formulaNP-completenesspolynomial time reductionsatisfiability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Satisfiability of mixed Horn formulas
• Theory and Applications of Satisfiability Testing
• Simple but hard mixed Horn formulas
• On the complexity of the maximum satisfiability problem for Horn formulas
• Satisfiability on mixed instances

Cites work

• A faster clause-shortening algorithm for SAT with no restriction on clause length
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
• A satisfiability formulation of problems on level graphs
• Linear CNF formulas and satisfiability
• Nested satisfiability
• Satisfiability of mixed Horn formulas
• STACS 2004
• The complexity of satisfiability problems

Cited in

(3)

• Simple but hard mixed Horn formulas
• Theory and Applications of Satisfiability Testing
• Satisfiability of mixed Horn formulas

This page was built for publication: On Some Aspects of Mixed Horn Formulas

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