新论文 · v1arXiv:2611.14471
关于枚举Horn表达式极大可满足子公式难处理性的注记
A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression
Oscar Defrain, Corentin Jazeron, Kazuhisa Makino
AI 速读 基于摘要
作者证明判定Horn表达式是否还存在另一个极大可满足子句子集是NP完全的，从而说明除非P=NP，否则不存在输出多项式时间的枚举算法。
cs.DM · cs.DS · math.CO
查看原文摘要
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.