摘要
我们学习布尔可满足性问题(坐)在输入上限制了有线性算术限制，在发生在一样的子句的变量的索引上强加的为公式。这能被看作在一样的子句在变量的分配的值上与另外的限制学习容纳的问题的Schaefers两分定理的一个结构的对应物。更精确，让坐k(m，一)\left({m，\mathcal{一}}\right)表示在k-CNF公式的例子上限制的容纳的问题，从\mathcal在最后km变量的索引被第一m完全通过一些线性方程决定的每个子句选择{一}。例如，如果\mathcal{一}包含i3=i1+2i2并且i4=i2i1+1，那么到4-SAT的输入的一个子句(2，\mathcal{一})有形式yi1yi2yi1+2i2yi2i1+1，与yi一起是xi或[“(xi)]\overline{xi}。我们获得下列结果：1)如果m2，那么为任何东西设置\mathcal{一}线性限制，限制问题坐k(m，\mathcal{一})是在P或NP完全的假定PNP的任何一个。而且，相应#SAT问题总是是#P完全的，并且坐最大的问题不允许假定PNP的一个多项式时间近似计划。2)m=1，也就是说，在每个子句，仅仅一个索引能自由地被选择。在这种情况中，我们为为限制容纳的问题设计多项式时间算法和一些技术开发一个一般框架。用这些，我们为任何A证明那\mathcal{一}，坐#2(1，\mathcal{一})并且Max-2-SAT(1，\mathcal{一})两个都是多项式时间可解决，它在有坐#2的将军和Max-2-SAT的坚硬结果的鲜明对比。为固定k3，我们获得重要限制的一个大班\mathcal{一}，在下面它这些问题坐k(1，\mathcal{一})，坐#k(1，\mathcal{一})并且Max-k-SAT(1，\mathcal{一})都能在多项式时间或伪多项式时间被解决。
出版日期
2012年04月14日（中国期刊网平台首次上网日期，不代表论文的发表时间）
