Paperlane

no. 13 · Wednesday 11 November 2026

A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression

Oscar Defrain, Corentin Jazeron and Kazuhisa Makino

math.CO · via cs.DM · 6 pp

Abstract

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.

comments
6 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.14471 ↗