{"id":"arxiv/2611.14471","url":"https://arxiv.org/abs/2611.14471","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression","domain":"cs.DM","source":"arxiv","authors":["Oscar Defrain","Corentin Jazeron","Kazuhisa Makino"],"reviews":0,"subject":"cs.DM","summary":"We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}