When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames

会议论文
发表日期：

2026年

查看全文

Andreas Krebs,
Arne Meier

摘要

Hemaspaandra et al. [JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in polynomial time. We refute this for S5 frames, by proving NP-hardness.

Hemaspaandra&#xa0;et al.&#xa0;[JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in polynomial time. We refute this for S5 frames, by proving NP-hardness.

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames

摘要

Hemaspaandra et al. [JCSS 2010] conjectured that satisfiability for multi-modal logic restricted to the connectives XOR and 1, over frame classes T, S4, and S5, is solvable in polynomial time. We refute this for S5 frames, by proving NP-hardness.