CNF基础超图的宽度算法：时间复杂度和自动定理证明器改进

1饱和度、麸皮h-宽度和Tseitin重言式我是亚历山大·阿列赫诺维。Razborov和 2002年9月Abstra t对于一个CNF，设w b（）为其基础超图的bran h-宽度。本文设计了一个求解SAT的算法，时间为nO（1）2O（wb（））. 这特别意味着一个多项式算法，用于测试树宽为O（logn）的实例的满意度。我们的算法是基于宽度的自动定理证明器（WBATP）的一种改进，WBATP是一种流行的（至少在理论水平上）证明器，用于确定不满意的CNF的分辨率反驳。我们表明，而不是穷举所有可证明的Lauses等人提出的基于Robertson-Seymour算法的图的bran h-宽度的逼近方法。我们都得到了基于Bran h-宽度的自动定理证明器（BWBATP）。与WBATP相反，它总是产生定期的拒绝。也许更重要的是，我们的算法的运行时间是有界的一个精益的combinatorial hara teristi，一个有效的近似，该算法也produes，在同一时间内，一个令人满意的分配，如果碰巧是满意的。在文章的第二部分，我们研究了BWBATP在Tseitin重言式类上的行为。我们认为，在这种情况下，BWBATP比WBATP更好也就是说，我们展示了它的运行时间对任何蔡廷重言式是j j O（1）2O（w（`;）），与WBATP提供的明显的结合nO（w（`;））麻省理工学院计算机科学实验室，mishka理论。s.mit.eduyInstitute for Advan ed Study，Prin eton，US，razborov ias.edu.在莫斯科斯捷克洛夫数学研究所休假冯·诺依曼基金会（von Neumann Fund）2这特别意味着归结在那些我们知道关系w（`;）O（logS（））的Tseitin重言式上是可自动化的。我们确定了一个这样的子类，并证明了部分结果建立这种关系的大lasses图。1.产品介绍满意度问题可能是最重要的NP完全问题之一，各种广告策略都是针对这一问题设计的。 这些算法之所以如此受欢迎，主要有两个原因：首先，SAT是最困难的NP完全问题;其次，许多实际应用需要满意的赋值或不满意的能力证明，并且不满意近似解，从而排除了使用近似算法理论中强大工具在计算机科学中，人们越来越多地关注-对这些ad-ho程序的理论研究和判断。看来，尽管它（普遍认为）最坏的情况下，硬度，仍然有许多有趣的问题，萨提斯能力，在那里取得进展。本文从基本超图的bran h-宽度（bran h-宽度等价于图的树宽度的常数因子）的角度研究了SAT的硬度。在这方面已经做了大量的前期相关工作，我们甚至不会试图给所有的参考，而只给最相关的参考。将一个图分解成若干个较小的单元，通过分块求解来解决一个关联的难题技术最初是由Lipton和Tarjan [LT80]提出的。利用他们所阐明的平面分离定理[LT79]的一种形式，本文给出了求解平面图上NP完全问题的一系列算法，其时间复杂度为2O（pn），比经典的算法要快得多。 那就好本文从提高材料力学性能的角度进行了理论研究。位置sear honesti s，以及应用这些技术，为更广泛一系列问题（例如，参见[Bod93]调查）。关于SAT问题本身，Khanna和Motwani [KM96]曾作过一个工作，除此之外，还把CNF看作是一个二部图，并在树宽不变的情况下处理了这个问题.然而，他们的目标是近似满意的lauses的数量，而不是精确地解决它。类似地，在工作[CMR01]中，SAT的硬度为3研究了所谓的图的宽度。这个结果比我们的结果更一般，因为它可以应用于更广泛的一类图，但它给出了相当弱的上界（只有nO（1） f（w），其中f是n-宽度w的非特殊递归函数）。最后，一些经验丰富的 SAT 专 家 利 用 树 分 解 来 找 到 令 人 满 意 的 分 配 （ 例 如 ， 参 见[AM01]）。本文应用Robertson-Seymour bran h-宽度逼近，本文给出了求解归结系统中满足性和自动证明问题的一个算法（推广到超图）。 也就是说，我们构造了一个基于Bran h-宽度的自动定理证明器（BWBATP），它能在nO（1）2O（wb（））的时间内证明一个CNF 的满足性，其中wb（）是图的Bran h-宽度.如果输入是不满意的，它产生一个正则归结反驳，其大小几乎相同，宽度为O（wb（））。论文的第二部分致力于解决更理论化的自动化问题。简而言之，如果任何重言式的证明都可以在时间多项式中以其最短证明1的大小被有效地找到， 则命题证明系统是可自动化的。Alekhnovih 和Razborov [AR01b]表明，从参数化复杂性理论中对合理的硬度假设取模，分辨率不是自动化的。然而，这篇论文中使用的例子看起来有些随意和孤立。因此，很自然地想知道（特别是对于那些通常对最糟糕的复杂性持理性态度的人来说）这些例子在多大程度上与实际相关。我们在这方面的主要（非正式的）目标是通过确定在上述意义下归结可由BWBATP自动化的重言式的一些自然类来解决这个问题，即在时间内失去最优的证明者和反驳。我们的主要目标是蔡廷的女儿。然而，用这种方法所得到的结果可能具有更广泛的适用性。为了使它们公式化，让我们通过下面的结构定义来确定在归结证明sear hististi的构造中自然出现的两个问题。[1]应该注意到，自动化的概念在某种意义上与证明系统的有效性的概念是“正交的”。 特别是，如果最优证明往往具有更大的尺寸，那么在这个定义的精神下，由于算法允许更多的运行时间，因此可能更容易找到它们。4假设不满意的CNF的C类是宽度可自动化的，如果存在确定性，算法，对于每个2 C构造其分辨率，2）求一个函数O（时间复杂度O（1）2O（w（`;））. 说C是smooth，如果对于2Cwehavew（`;）KClogS（），对于某个绝对onstantKC>0. 因此，每个同时具有宽度可自动化和光滑性的C类都是可自动化的。众所周知，一般来说，分辨率是既不是宽度自动化的（模一个合理的假设，[AR01 b]），也不是smoooth（见Bonet，Galesi [BG 9 9]和Atserias，Bonet[AB 02]）。 我们将针对更窄的类别单独解决这些问题。相对于第一个，我们的主要结果（定理2.8）表明所有Tseitin重言式的类是宽度自动化的。我们通过证明在这种情况下wb（）=（w（`;））来证明这一点。到目前为止，我们对第二个问题（平滑）的贡献要有限得设图G的y度（G）是G的边最多能被y条覆盖的最小值，使得G的每条边最多属于y条.证明了（定理2.10）基于有界线性图的Tseitin重言式类是光滑的.在结合定理2.8，这意味着， 类可自动化关于决议。特殊环中的有界度图类涵盖了平面图中的有界度图类，其中格（文[Tse68]中考虑的）是典型的例子。即使我们在Y的定义中放弃了第二个限制（即， 不要限制y les an edge may belong to），我们仍然证明了相应的Tseitin重言式类是拟光滑的，也就是说，西（ `;）log S（）O（1）（定理2.12）. 特别是，类是准自动化的。我们还给出了一个弱的部分结果，证明了所有Tseitin重言式类的（拟）-光滑性（定理2.13）。本文的结构如下。在第2部分中，我们给出了必要的并对主要结果进行了分析。在第三节中，我们构造了主要的算法并研究了其性能.第4节包含Tseitin Tau的宽度可自动化性的构造和证明tologies，而第5节致力于证明我们的平滑结果。最后，本文在第6节中提到了一些悬而未决的问题。5def Sdef P2.分类和结果设x是B的一个不变量，即：变量的范围超过集合f0;1 g. x的字面量是x（有时表示为x 1）或x（有时表示为x 0）。Lause是字面量的分解。一个CNF是成对不同的Lauses的集合，通常与这些Lauses的集合一致。用于 lause C，Vars（C）是出现在C中的变量的集合。用于CNF，let V ars（）=fVars（C）jC2 g.对变量集V的 赋 值 是一个映射：V！ f0;1 g. 一个 约束是一个映射：V！ f0;1;？G. 用Cj[j]表示的LauseC或CNF的定义是从C [ j]得到的Lause [CNF]，分别将eahx21（f0; 1g）的值设为（x），并留下eahx 2 1（？）作为变量。假设CNF语义上蕴涵一个Lause C（记为j= C），如果对V的每个赋值都满足所有劳斯因 ，将C发送到1。归结是最简单也是研究最广泛的命题证明系统之一，它与Lauses一起工作，并具有一个不等式规则A_x B _x：A _B我们说变量x在归结规则的这个例子中被归结。一个归结证明是正则的，如果沿着每一条h路径，每个变量至多在e上归结。（正则）归结是隐含的合理和完备的，即C from存在的（正则）归结证明当且仅当j=C。一个CNF的归结反驳是从中出现的Lause中归结出空Lause的证明。一个归结证明的大小是其中的lause的总数为一个不可满足的CNF，S（）是其归结反驳的最小规模。Lause C的宽度w（C）是C中文字的数量。一个Lause集合的宽度w（）（特别是归结证明的宽度）是出现在这个集合中的Lause的最大宽度对于一个不可满足的CNF，w（`;）将表示其归结反驳的最小宽度。也让n（）是出现在 ，j j是变量的总数量，即，j j =C2w（C）.F或n，一个非线性的整数整数令[n∈d=eff1;2;：;n g.超图是一对H =（V; E），其中V是顶点的集合，E是其元素（称为超边）是V的子集的集合alled解析规则：61mdefdefB bS Sno(thus允许多个边缘超图（V; E）是一个图，如果所有的边E2 E具有基数2，其中它们将被表示为小写字母E。顶点v的星是S（v）d=effE2Ejv2E g，以及它的degre是deg（v）d=ef jS（v） jHH 是超图H.H. 对偶超图fSH（v）j v2Vg在E上。 r（H）d=efmaxE2EjEj是一个H边的最大长度.超图的bran h-宽度的以下定义与[RS 91]中的定义基本相同;我们对它所做的唯一（osmeti）改变是：以二叉树代替三叉树。定义2.1超图H =（V; E）的一个bran h-de合成是一个对（Ti），其中T是一个二元根树，是E和T的叶子集合之间的一个分支。对于T的任意节点t，设E（t）=E（t）d=efE2Ej（E）是tg的一个端点，设E？（t）d=efEn E（t）。设V（t）=fEj E 2 E（t）g和V？（t）=E E 2 E？（t）。t的ut是Cut（t）d=efV（t）\V？（t）。t的顺序是切割（t）。bran h-de-composition（Ti）的宽度w（Ti）是T中节点的最大 阶 数 ， 而 H 的 bran h- 宽 度 ， 记 为 wb （ H ） 是 H 的 所 有 bran h-de-composition的最小宽度。给定一个CNF =C1^：：^Cm，我们把它与超图联系起来，Hd=effVars（C）;：：;Vars（C）g在V ars（）上。设的bran h-宽度w b（）是该hy-图的bran h-宽度：w（）d=efw（H）。备注1已知麸皮的h-宽度是相等的（直到一个乘数）。[1991年10月19日]，《易经》第一卷。然而，我们更喜欢陈述我们的结果在前一个措施，因为我们将使用Robertson-Seymour算法的推广近似bran h-宽度。此外，在我们的特殊背景下，与麸皮H宽度相关的epts和构造看起来更自然。下面的结果基本上说明了bran h-de命题可以用来构造有效的归结反驳。定理2.2存在一个确定性算法，在时间上运行p在j j+2wb（）中的多项式，并且：71. 如果是unsat- is able，则返回其宽度为O（wb2. 返回一个满意的赋值，如果是令人满意的。重新定义了[BPR00]中关于自动化的所有一般定义。我们在这里只给出了解决方案的特殊情况;另一方面，它是针对不满意的CNF的任意lasses（与[BPR 00]中所有不满意的CNF的lasses相反定义2.3不满意CNF类C是（准）自动化的（与Resolution有关），如果存在一个确定性自动化算法，给定一个不满意CNF 2 C，返回其在时间上的归结反驳，其中h是j j + S（）中的（准）多项式。注意，任何自动化算法构造的归结反驳的大小也必然是jj + S（）中的（拟）多项式现在，我们沿着同样的思路介绍以下关于ept，technal但非常有用的内容。定义2.4 C类不满意的CNF是宽度自动化的，如果存在一个确定性算法，给定一个不满意的CNF 2，C，返回其在时间上的宽度为O（w（`;））的归结反驳，其中h是j j+ 2w（`;）中的多项式。请注意，该程序穷举地生成所有宽度的可证明的子句，1、1、2、3、4、5、6、7、10、11、12、13、14、15、16、17、18、19、19、19、（基于宽度的自动定理证明器）a在时间j jO（w（`;））内完成了这个任务，也就是说，所有unsat的类，CNF是准宽度自动化的。Ben-Sasson和Wigderson在[BW 0 1]中证明了w（`;）O（logST（）），其中ST（）是树型归结反驳的最小长度.在此基础上，我们介绍了以下几个方面.定义2.5如果存在绝对常数KC>0，满足w（`;）KClogS（）[w（` ;）（logS（））KC，对于所有2个C分别为零，则不满意的CNF类C是smooth [准smooth]。以下是从定义中直接得出的。8LeM^T（Gi）=PARITY：图1每一类不满意的CNF，同时是宽度自动化和光滑的是自动化的。每一个准光滑类都是准自动化的。定理2.2特别地包含了有界w（`;）O（wb（））.我们现在确定一种情况，其中这个界是紧的。定义2.6设G =（V（G）; E（G））是（普通）有向图，且：V（G）！ f0;1 g是奇数权函数，即，因此v2V（G）（v）=1. 给每个边e2E（G）赋一个区别变量xe. 对于v 2 V（G）和2f0;1g，令P ARIT Yv;d=ef^（_xa（e）M（a（e）1）6=）e3v e3v是布尔函数的直接CNF表示xe =：（1）e3vG的Tseitin重言式和是由下式给出的不满意CNFdefv;（v）v2 V注2：在证明复杂性的研究中，常常假设G的顶点度是有界的，并且G具有一定的扩张性质。这两个假设既不需要，也与我们的目的无关注3：与Tseitin重言式T（G1）相联系的超图HT（G1）就是对偶超图G，其直径为每一个r长的超边重复自身2r1次.定理2.7 wb（T（Gi））=（w（T（Gi）`;））.与定理2.2相比，我们立即得到关于-宽度自动化。定理2.8所有Tseitin重言式的类是宽度自动化的。现在让我们转向我们的第二个问题，平滑度。9定义2.9对于一个普通图G，定义它的y为最小的“因为G的边缘可以被y les以这样的方式覆盖，y le的长度最多为`，每条边最多属于` y les。定理2.10w（T（G;）`;）`（G）O（1）log S（T（G;））：特别地，所有的Tseitin重言式T（G）的类（其中h `（G）由某个绝对常数有界）是光滑的。定理2.8和2.10意味着定理2.11所有Tseitin重言式T（G; ）for whi h `（G） 是可自动化的。我们注意到这类图在特殊的集合中是所有面都有界度的平面图的集合。设~（G）是G的边为 安贝 覆盖长度的类型（对这个的倍数没有限制）。我们还有以下内容：定理2.12w（T（G;）`;）（`~（G）logS（T（G;））O（`~2（G））：特别是， 所有Tseitin重言式T（G; ），`~（G）是拟光滑的，因而是拟自动化的。最后，让我们提到一个简单的部分结果，以显示所有Tseitin重言式的lass的光滑性：定理2.13 w（T（G i）i）O（log S（T（G i））+ jV（G）j）.3.基于Bran h宽度的自动定理证明器本文证明了定理2.2。我们构造的算法将支持-分两个相对独立的阶段进行。在第一阶段，我们展示了如何10deomposition（T^;^）是另一个部分branh-deomposition的一个元素a 几乎最优的bran h-de组合（引理3.1）;这将通过将Robertson-Seymour算法相当直接地适应超图来完成。在第二阶段，我们展示了如何使用任何窄bran h- de合成来构造有效归结反驳（引理3.2）。引理3.1存在一个决定性算法，使得对于任意超图H =（V; E），h在时间内输出其宽度为O（wb（H））（jVj+jEj）O（1）2O（wb（H））.引理3.1的证明让我们首先观察到，degH（v）1不影响bran h-宽度，可以立即删除。 因此，我们可以假设w.l.o.g. 对于所有v 2 V，都是H（v）2。 这特别意味着（通过观察叶片或对应于超边缘最大尺寸），wb（H） r（H）：（2）设Fd=eff（v;v0）j9E2E（fv ;v0 gE） g，定义同一顶点集V上的有向图G =（V; F）：我们的基本思想是将Robertson-Seymour算法应用于G，以近似普通图的bran h-宽度[RS 95]。这种从H到G的缩减并不是绝对直接的（因为我们必须小心不要删除原来的超边），所以我们更愿意用一种方便我们进一步目的的语言给出一个独立的描述。此外，我们不试图优化乘法常数，这将使算法实际上更简单。让一个部分的bran h-de组合被定义为相同的方式作为一个（总）bran h-de组合，与不同的是，我们需要的功能，仅仅是一对一而不是一对一。 一部分麸皮-（Ti）如果T是T^的子树，并且对于T的每个节点t，E（t）= E^（t）。算法试图结构宽度（总）宽度组成w，当参数w一次递增一个时。 给定w的特定值，该算法从平凡的部分branh_de合成开始（即，当T是一个单节点树时），并以这种方式保持它的宽度永远不会超过w，直到它到达一个完成麸皮h-de成分或得到stu k. 的 关键是11（66F\（V1 V2）=;且jV1\ Zj; jV2\ Zj1jZj）do开始(1)如果jVj 4 r（H）返回任意branh-de组合else（2），其中w =4 r（H）; 4 r（H）+1;：：do开始T：= frootg（单节点树）;：=将每个E2 E发送到root的函数(3)如果是一对一，然后返回（T; ）elset：= T的任意叶，其中j1（t）j > 1; Z：=Cut（t）;(4)如果jZj w r（H）确实开始在t时将h T麸皮化成两片新叶t1;t2;对于E21（t）do（E）：=t1if E =E1t2否则1（t）的任意固定元素;转到（3）端其中，E1是一* *(5)如果（存在分区V = C[V1[V2，其中j1jZj su h开始(6)pi k任何su h分区;注意，特别是每个超边E21（t）既不插入V1，也不插入V2，将t处的T分成两个新叶t1，t2;对于E21（t）do (E)：= t3得双曲余切值.则E\ V =;;如果E\V1 = E\V2 =;，则任意选择;转到（3）端Go to（2）在所有其他情况下，该算法都会被卡住，返回到运算符（2），将w的值重赋值1。在这种情况下，我们将所有的当前值Z一个障碍;端端12图1：在超图H中构造bran h-宽度分解131111111211111WW在后一种情况下，该算法将发现将保证不等式wb（H）的“障碍”。（w）。 该算法的形式见第11页。让我们分析一下这个算法。 首先观察到它保持了性质w（Ti）w。实际上，如果按照算子（4）进行计算，则对于2f1; 2g w，有一个cut（t）Z[E1]，其中蕴涵jCut（t）j（w r（H））+ r（H）w。如果该元素向运算符（5）进行排序，则Cut（t 1）C [（V 1\（V2[Z））]= C [（V 1\Z）]，并且jCj + jV 1\Z j16参数表明jCut（t2）j W.接下来，注意，除了运算符（5）、（6）之外，该算法的所有步骤都可以在jVj + jEj中的时间多项式内执行。但是，这些操作器可以在时间2O（w）内实现，只需彻底地烧蚀通过所有不相交的子集对Z1;Z2Z表示jZ1 j; jZ2 j6jZj它们之间的G没有边。 对于每个suh对（Z1;Z2），我们找到分隔Z1和Z2的最小顶点ut C，并返回此ut在运算符（6）中，如果jCj6jZj。 因此，算法的时间复杂度为（jV j + jE j）O（1）2O（w），其中w是bran h-de合成算法 奈利回来了。我们只需要证明w O（wb（H））。如果算法将bran h-de组合a返回给运算符（1），或者如果w = 4 r（H），则从（2）得出。否则，设Z为使算法在第（w1）阶段中止的障碍.注意，由于算子（4）的存在，jZj w r（H）。设（T; ）是总的麸皮H-组合物2 的H，其宽度为wb（H）。F或T的一个nodet，令Z（t）d=efV（t）\Z和Z？（t）d=efV吗？（t）Z. 显然，Z（root）= Z且对于任何叶t，jZ（t）jr（H）<3（w）r（H））3jZj.因此，存在内部节点t，满足jZ（t）j>3jZj，而jZ（t1）j3jZj和jZ（t2）j3jZj对于其hilt1和t2。 尤其是，jZ（t）jjZ（t1）j + jZ（t2）j3 jZj whi h implies jZ？（t）j3 jZj（sin e Z（t）[Z？（t）= Z）。 我们让C ：=切割（t）。 然后，在删除C之后，Z（t）n C和Z？（t）n C在图G中不存在. Sin e Z是一个障碍，我们必须有jCj>6jZj，其中h意味着所需的界限：w b（H）联系我们6jZj6（w） r（H））6（w）4）=jZj +（jZjjV2\ Zj）jZj通过归纳假设。 类似的148 .第八条。引理3.1是完全证明。2（T;）与算法在流产时刻构造的部分branh-de合成无关，并且后者将不会被使用在接下来的论证中151r现在我们展示如何将bran h-de合成转化为resolution refutations。引理3.2存在一个决定论算法whi h为每个unsat-是可CNF的，并且超图H的每一个branh-分解（Ti）都返回一个正则归结反驳P，P是关于j和2w（Ti）的时间多项式。此外，P具有宽度O（w（Ti））。引理3.2的证明 我们需要以下众所周知的构造。定义3.3对于一个Lauses集C，设ker（C）是它的存在极小Lauses（对于引用）的子集.让Cxd=fkerfC_DjC_x;D_x2C g[fC2C jx62Vars（C） gbe的一组Lauses 从C获得的所有可能的决议上的变量x。不难验证（Cx）y =（C y）x;因此，对于一组变量V=fx;：;xg，我们有一个模糊的定义CVd=ef（（Cx1）x2 **）xr。直观地说，CV是所有\信息”可在变量V ars（C）n V中表达的，我们从C中得到额外的t：为了简单起见，我们将把中的Lauses与H中相应的超边标识出来。我们的算法以向上（从叶子到根）的顺序遍历T的节点，比如说，深度-rst sear h。对于每个访问节点t，算法在变量Cut（t）中递归地构造一组Lauses C（t），如图2所Sin e jCut（t）j对于每个节点，j C（t）j2O（w（T;））;因此，算法在时间上为jjO（1） 2O（w（Ti）），并产生C（root）的一个宽度为O（w（Ti））的归结逆（后者要么是空集，要么只包含空集）.其次，很容易看出，如果s不是t的行列式，那么V0（t）\V（s）=;：（3）特别地，对于每两个不同的未知数t; s，V0（t）\V0（s）=1，这意味着该不等式是正则的。最后我们证明了，如果是unsatisable，那么;2 C（root）.为此，我们将在算法进行期间保持跟踪以下辅助CNF 电 流。初始urrent=[fC（t）]t是叶g，并且每个16(C(t）[C（t））[（C（t）[C（t））V0（t）.然而，观察结果（3）意味着开始对于所有的叶t，如果1（t）包含一个变量，该变量不出现在任何其他的方程中，则C（t）：= ; else C（t）：=f1（t）g;对于T中所有按向上顺序访问的内部节点t，t1;t2：=两个 t的门V0（t）：=（Cut（t1）[Cut（t2））nCut（t）;(1)C（t）：=（C（t1）[C（t2））V（t）;结束结束0图2：将bran h-de组合转换为正则解析反驳在应用运算符（1）时，我们用C（t）代替当前t中的LausesC（t1）[C（t2）。我们声称目前的情况一直令人不满意。实际上，初始值[fC（t）]t是当前t的叶g，由下式获得：通过删除所有包含未在其他地方出现的变量的Lauses。显然，这个较短的CNF的不满意能力暗示着（每个被移除的lause都可以通过适当地设置其单个变量来满足）的不满意能力。在每一个单独的步骤（1）中，d=ef（urrentn1 2 1 20即Vars（urre ntn（C（t1）[C（t2）\V0（t）=;，因此0urre nt=（urre nt）V（t）。现在，从以下简单的方法中立即得出indu tive步骤(see例如[Kra95，定理4.2.1]：语句3.4如果是一个不可满足的CNF，并且x是一个变量，那么x是不可满足的。在算法的最后， 电 流= C（根），其不满意的能力意味着;2 C（根）。这就完成了引理3.2的证明。值得注意的是，虽然它不是从描述中直接得出的，但证据表明，我们所构造的反驳实际上属于戴维斯-普特南程序的范畴，17GV如在[BG 99]正如我们在上面已经观察到的，定理2.2直接由引理3.1和3.2得出，需要注意的是，如果算法在某个点被卡住（例如，C（root）不包含任何Lauses），那么我们可以跟踪该过程，并直观地找到一个令人满意的分配。4.Tseitin拓扑的宽度自动化现在我们来证明定理2.7。为此，我们需要下面的高斯宽度的概念（尽管它对任意线性方程组都有意义，但我们在这里仅对蔡廷互变的部分情形用公式表示）。定义4.1F或普通图G与VV（G），设Cut（V）d=eff（v;v0）2E（G）jv2V;v062Vg.定义4.2与蔡廷重言式T（G i）相关联的高斯演算中的直线是以下形式的模2线性方程：Ld=ef0Mxe=M（v）1;E2CutG（V）v2VA其中VV（G）. LV是初始公理（1）的模2之和;注意，如果G是奇数权，则V由LV唯一确定。 高斯分布唯一的不规则是LV1LV2：LV14 V2T（G i）的高斯反驳是LV（G）的证明（即，0 = 1）从公理Lv（即，(1))在与T（G;）相关联的高斯分布中。线的宽度Lv是它的变量的数量jCutG（V）j，高斯反驳的宽度是它的所有线的最大宽度，并且T（G;）的高斯宽度，由wg（G;）表示是T（G;）的高斯反驳的最小宽度。18111def第一作者在论文[ABRW00]的工作中观察到以下情况，并在[BI99]中成功地用于对模2线性方程组的多项式代数反驳的次数进行限制提案4.32w（T（G;）`;）wg（G;）w（T（G;）`;）.现在我们来证明定理2.7。给定命题4.3，我们必须证明wb（T（G;））=（wg（G;））。正如我们已经观察到的，与CNFT（Gi）相关联的超图HT（Gi）就是G，其直径是每个超边重复自己几次。很容易看出，从超图中去除重复的边并不改变其bran h宽度。 因此，该定理现在由以下公式得出：声明：引理4.4 wb（G）=（wg（G;））：证据通过检查定义，可以看出，wb（G）与wg（G i）基本相同，唯一的区别是我们只允许读上e（树状）高斯反驳，即，这些反驳中的每一个公理(1)在E上使用得很好。 这一点证明了wb（G）wg（G;）.对于相反的方向，我们不再参考图1所示的出租分析。首先注意到（2）可以推广到wg（G;）r（G）（r（G）是G的最大顶点度）. 因此，就像引理3.1的证明一样，有必要证明障碍3ZE（G）使算法在第（w1）步中止，则蕴含更强的不等式wO（wg（G;））.这是通过用具有高斯宽度wg（Gi）的T（Gi）的（也是最佳的）高斯反驳P直接替换最佳bran h-分解（Ti）来完成的。设T是P的底层树，对于T的节点t，设LV（t）是P的底层树。在这个节点上。接下来，设E（t）def=Sv2V（t）SG（v），类似地，艾薇？（t）=Sv2oV（t）SG（v）（注意，Cu tG（V（t））=E（t）\E？（t））李克伯-记Z（t）d=efZ\E（t），Z？（t）d=efZ\E？（t）。如果t是一个内部节点，T和t1，t2是零点，则V（t）= V（t1）4V（t2）V（t1）[V（t2）]，此时仍有E（t）E（t1）[E（t2）和jZ（t）jjZ（t1）j + jZ（t2）j. 争论和以前一样，我们 nd节点t使得jZ（t）j= jZj，jZ？（t）j3jZj. 出现在LV（t）中的边的集合是割G（V（t）），并且这3重要的是要记住，在证明引理或对应于对偶超图G的符号，现在顶点和边交换平面，19是否有一条边ut将Z（t）n切割G（V（t））与Z分开？（t）n割G（V（t））。其余的证明重复了前面的论证。5.Tseitin拓扑的（拟）光滑类本文证明了定理2.10，2.12和2.13。所有的证明都遵循[BP96]中提出的相同思想。也就是说，我们将定义一个随机约束，它将具有以下两个属性：1. 以高概率，不减少w（T（G;）`;）太多h;2. 每个大宽度的Lause都被杀死（也具有高概率）。则性质1将允许我们根据w（T（G;）j“;）上界w（T（G;）j”;），性质2将根据S（）给出后一个量的上界。定理2.10的证明这个证明使用了一个类似于[Ale01]中的构造。让我们 x一个C族， G中有长度的y（G）并且，每个边属于族中至少1个且至多“（G）”型。设顶点为G的边的辅助图LC（G），e和e0在LC（G）中重合当且仅当e和e0至少在1 y C2 C。注意degLC（G）（e）`（G）（`（G）1）;（4）对于所有的e2 E（G）.5.1设为任意约束，将变量fxej e2Eg任意赋给0，1，其中E是LC（G）中的独立集（即， 没有两个边缘出现在相同的类型中。则对于任何奇数权重，w（T（G;）`;）O（`（G）w（T（G;）j`;））.权利要求5.1的权利要求。首先注意T（G ~ i）=T（G~i），其中G~i=（V（G）;E（G）n E），~i是由所赋值自然定义的调整。由于定理2.7（以及开头的注释（G ~）的前式），它必须证明wb（G）O（`（G）wb（G~））. 让我们x20j割G（t）\E j`（G）noG ~的一个branh-位置（Ti），其宽度为wb（G~）。单G和0G~e具有相同的顶点集，（Ti）也被认为是一个branh，定义了G的一个位置，并称它的宽度为O（`（G）wb（G~））.实际上，对于T的一个nyndet，j CutG（t）j =j Cu tG~（t）j +j CutG（t）\E j。对任意的e2割G（t）\E，取一个任意的含有e. 注意，sin eE在LC（G）中是独立的，所有这些y是两两不同的。另一方面，Ce必须包含另一条不在E中的边fe2割G（t）。 每一条边f2E（G）nE至多可以在`（G） y les Ce，因此j割G~（t） j，然后 j割G（t） j（`（G）+1）j Cu tG~（t）j（`（G）+1）wb（G~）. 权利要求5.1被提出。设E（G）是强独立的，如果图LC（G）中任意两个距离e02E之间的距离至少为3.5.2每一个E E（G）包含一个强独立子集E0 E，其中jE0 j jE j =`4（G）.第5.2章证据使用顶点度界（4）通过贪婪算法构造E0现在我们准备讨论定理2.10的推导 Let`d=ef`（G），pd=ef1=（2`2），设E pE（G）是任意一个边子集，每一个边缘都有可能出现，而不是其他边缘。设Ed=efe2Epe在LC（G）jEp中是孤立的 . 注意，E始终是LC（G）中的指数集。 设e是一个随机约束，它随机分配变量fx ej e 2E g。则权利要求5.1意味着（概率为1）w（T（G;）`;）O（` w（T（G;）j`;））：（5）另一方面，设P是T（G;）的大小为S的归结反驳，C2 P是其中宽度为S的任意LauseK '6log S，K > 0是一个suf-非常大的常数。 应用权利要求5.2，nd D宽度为K`2log S因此，Ed=effe2E（G）jxe2Vars（D）g是强独立的.的e2Ep只依赖于图LC（G）中e的边的星SLC（G）（e）上的Ep的顶点，并且这些星对e2E0是不相交的（sin eE0是强独立的）. 因此，事件fe2 E j e 2 E 0g 是 独 立 的 ， 并且它们中的每 一个都具 有 概 率 P[e2Ej]=P[e2Ep j]。