Detecting embedded Horn structure in propositional logic

DOI10.1016/0020-0190(92)90098-GzbMath0780.68055OpenAlexW1991253226MaRDI QIDQ1198035

S. Singh

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90098-g

zbMATH Keywords

NP-hardmaximum clique problemset packing problempropositional satisfiability problemmaximum renamable Horn problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Related Items (7)

Variable and term removal from Boolean formulae ⋮ Testing heuristics: We have it all wrong ⋮ Tradeoffs in the Complexity of Backdoor Detection ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Maximum renamable Horn sub-CNFs ⋮ Mixed logical-linear programming ⋮ Recognizing renamable generalized propositional Horn formulas is NP- complete

Cites Work

• Unnamed Item
• An exact algorithm for the maximum clique problem
• On renamable Horn and generalized Horn functions
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Finding a Maximum Clique in an Arbitrary Graph
• Recognizing disguised NR(1) instances of the satisfiability problem

This page was built for publication: Detecting embedded Horn structure in propositional logic