.png){kind=icon}
返回
Linear Planar 3-SAT
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115834.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
文献中已研究可满足性问题的多个片段。其中，线性3-SAT是一种满足性问题，其中每个子句（视为文字集合）最多与另一个子句相交；此外，任意两个子句最多共享一个文字。平面3-SAT是要求所谓变量-子句图是平面的片段。这两个片段均为NP完全，并应用于编码NP难规划问题。本文研究了结合这两种特征的片段的复杂度与应用。我们定义了线性平面3-SAT，并证明了其NP完全性。我们还研究了线性平面3-SAT的重构问题，并证明其为PSPACE完全。
Keyword:
Complexity theory
Planar 3-SAT
Linear 3-SAT
Planar graphs
Planning
期刊
IF:
1
论文数:
273
被引数:
1.0W
机构
.png){kind=icon}
查看更多内容