A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression
Source: arxiv.org/abs/2611.14471
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.14471
curl -X POST /api/v1/records/arxiv/2611.14471/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.14471/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'