Detecting Embedded Horn Structure in Propositional Logic.pdf.pdf' (115.49 kB)
Detecting Embedded Horn Structure in Propositional Logic
journal contribution
posted on 1977-07-01, 00:00 authored by V. Chandru, John N. HookerWe show that the problem of finding a maximum renamable Horn problem within a propositional satisfiability problem is NP-hard but can be formulated as a set packing and therefore a maximum clique problem, for which numerous algorithms and heuristics have been developed.