不可能性定理与通用代数工具箱

2022-5-8 07:24:38

不可能性定理与泛代数工具Kitmario Szegedy和Yixin Xu罗格斯大学计算机科学系。罗格斯大学。教育部，2018年11月10日摘要我们阐明了判断聚合理论（更一般地说，评估聚合）与一个相对年轻但增长迅速的普适代数领域之间的密切联系，该领域主要用于研究约束满足问题。我们的联系产生了一个完整的非二元评估分类，分为可能性域和不可能性域，无论是在有效条件还是支持条件下。在当前结果之前，E.Dokow和R.Holzmanner通过组合方法对支持性案例中的非二元评估进行了分类。代数方法也为我们提供了对更简单的二元情况的新见解，这已经被上述作者完全分类。我们的代数观点让我们提出了一个关于加强非独裁标准的建议，这有助于我们避免像a ffine子空间这样的“异常值”。最后，我们给出了计算复杂度的上界，如果一个域不可能或不可能（据我们所知，之前没有给出确切的时间界限）。关键词：判断聚合、话语困境、康多塞悖论、阿罗不可能理论、社会选择理论、独裁、兼容操作、约束满足问题、二分法、，多态性1简介判断聚合的目标是研究“将多个逻辑连接命题上的单个判断集聚合为集体判断集”的函数的存在与否[LP02]。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:24:41

阿罗的不可能性定理可以在判断聚合框架中进行解释，这是一个有力的例子，表明即使在简单的情况下，我们也无法有意义地将个人观点聚合为社会观点。Elad Dokow和Ron Holzman[DH10a，DH10b]研究了判断聚合的一个优雅概括，我们在他们的评价聚合标题后称之为判断聚合。假设J是一组确定的问题，D是一组确定的可能立场/意见（如“是”、“否”等）。在不失去普遍性的情况下，我们假设j=[m]={1，…，m}。评估（v，…，vm）∈ DMD将D中的一个位置分配给每个j∈ [m] 。二元情况whenD={0，1}受到了特别关注[Wil75，RF86，DH10a]。我们的基本目标是领域X 在可行性评估中，这些评估（即意见组合）允许选民选择。例1。假设在谋杀案审判期间，陪审团成员必须就两个问题进行投票：1。嫌疑人有一把刀；2.嫌疑人是凶手；在每个问题上采取“是”或“否”的立场。每个成员都必须在这两个问题上采取立场，但陪审团同意，立场组合（1:否，2:是）不应有效：既不能作为个人投票，也不能作为集合投票。因此X={（不，不），（是，不），（是，是）}。聚合器。当一个社会的n个成员对所有m个问题采取立场时，每个成员的意见来自X，我们得到一个文件向量（X（1），x（n））∈ Xn。我们的目标是设计一个函数f:Xn→ 将文件向量转换为X的单个元素的函数。这种函数称为聚合器。我们将考虑的聚合器必须满足三个条件，这三个条件直接来自Arrow的著名条件，他在研究偏好列表聚合的特殊情况时确定了这三个条件。在我们描述它们之前，我们注意到x（i）=（x（i）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:24:46

，x（i）m）∈ 对于i=1，··，n，是向量本身：x（i）jis是jthissue上的位置。因此，文件是向量的向量。f的输出是一个以Dm为单位的向量，表示m个问题上的聚合位置。后一个向量也必须属于X。第一个也是关键的条件是，每个问题都应该独立于其他问题进行聚合（也称为逐点聚合或逐问题聚合）：逐问题聚合（IIA）：有函数fj:Dn→ D（1）≤ J≤ m）这样，外汇（x（1），x（n））∈ Xn:f（x（1），x（n））=Fx（1），x（n）, . . . , 调频x（1）米，x（n）m通过picturex（1）·x（1）m可以很好地可视化IIA属性∈ 十、x（n）··x（n）m∈ 十、↓f···↓fmx··xm∈ X上面我们汇总了列j（其中j∈ [m] 是功能fj的问题）。f takesXnto X的条件相当于，如果每一行都属于X，那么聚合行也属于X。组件聚合函数应该协同工作以实现这一点。我们采用了E.Dokow和R.Holzman[DH10a，DH10b]提出的术语“逐项汇总”，在这种广义背景下，它比常用的“无关替代品的独立性”表达更适合，其好处是首字母缩写保持不变。IIA分解的唯一性。f:Xn的表示→ X as（f，…，fm）显然不是唯一的，例如，当D包含任何元素时，这些元素在任何X中都不是构成元素∈ X.为了避免FJ的非唯一性，我们定义了j=prjX={uj|（u，…，um）∈ 十} 。如果我们定义fjon Dnjin而不是Dn，很容易看出fjbecomes是独一无二的。在本文中，我们将假设这一点。接下来，我们将描述Arrow对聚合器f:Xn施加的另外两个条件（除了IIA）→ 幂等性（或一致性）：f（X，…，X）=X每X∈ 引理1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:24:49

IIA聚合器f=（f，…，fm）是幂等的当且仅当在泛代数意义下每个FJI都是幂等的，即。 1.≤ J≤ M U∈ Dj:fj（u，…，u）=uNon独裁：聚合器f:Xn→ 如果有一个1，那么X就是独裁≤ K≤ n使得forevery（x（1），x（n））∈ 我们有f（x（1），x（n））=x（k）。否则，f引理2的非独裁条件成立。IIA聚合器f=（f，…，fm）是独裁当且仅当存在1≤ K≤ M使得每个FJI都是在普遍代数意义下的KTH坐标上的投影： 1.≤ J≤ M U联合国∈ Dj:fj（u，…，un）=UK定义1（不可能性/可能性域）。我们称之为X 关于IIA+幂等性+非独裁条件的Dma可能性域（箭头后），如果对于某些n≥ 2存在满足上述三个条件的算术数为n的X的聚合函数f。OtherwiseX是一个不可能的领域。在本文中，我们完全刻画了关于IIA+幂等+非独裁的不可能域，以及当幂等被支持性取代时的不可能域：f:Xn→ 如果每X（1），x（n）∈ Xnand每1≤ J≤ 我们有f（x（1），x（n））j∈ {x（1）j，…，x（n）j}。引理3。IIA聚合器f=（f，…，fm）是支持的当且仅当每个FJI在普遍代数意义上是保守的： 1.≤ J≤ M U联合国∈ Dj:fj（美国，…，联合国）∈ {u，…，un}支持性意味着幂等性，但反之亦然。在我们的结果之前，我们在[DH10a]中获得了IIA+幂等+非独裁下所有不可能二元域的完整特征。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:24:52

他们将工作扩展到了非二元情况，但只获得了部分特征，并且仅在IIA+支持+非独裁条件下。在我们的描述中，我们利用了D.Geiger[Gei68]发现的Galois联系。盖革的性质定理允许我们用小工具的存在来描述聚合器的不存在性——存在的逻辑表达式是由X和一些非常基本的关系创建的，比如赋值或一元关系。（在文献中，小工具有时也称为连接查询。）定理8和定理17给出了我们的主要结果。我们的主要贡献不是任何新技术，而是指出了迄今为止尚未探索的非常广泛的联系。简单只对新连接有利。基于代数观点，我们还可以加强非独裁条件，以排除专家认为的异常值（如线性子空间）的可能性。我们在这里使用的理论越来越为计算机科学家所熟悉，因为它提供了一个强大的机制来解决著名的费德和瓦迪[FV98]关于约束满意度问题（CSP）的二分法猜想。希望这种联系能让研究人员利用CSP研究所创造的大量材料来证明不可能性定理。2背景E.Dokow和R.Holzman在[DH10a，DH10b]中提出了引言中描述的优雅的一般组合框架，作为本论文的基础。我们将其命名为“综合评估”，以其标题命名。在他们的两个突破性成果中，他们在对不可能域进行分类方面取得了决定性的进展，即那些我们无法从中总结观点的X。特别是，他们彻底解决了二元问题。为了解释他们的结果，我们需要一些定义。定义2。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

大多数88

2022-5-8 07:24:56

如果| prjX |对每1大于1，我们称X为非退化的≤ J≤ m、由于退化发生的问题可以简单地聚合起来，在不丧失普遍性的情况下，我们可以假设X是非退化的。定义3（块度图和MIPE）。域X的块性图 {0，1}在顶点集V=[m]×{0，1}上有一个有向图：有一条来自（k，σ）的有向边∈ Vto（`，ρ）∈ 其中k6=`当且仅当存在：（i.）子集S [m] 这样k，`∈ S和（ii）a（部分）评估美国→ {0，1}uk=σ，u`=¨ρ，因此在x中没有任何完整赋值x的扩展，但如果我们定义u的任何位，则得到的部分赋值将扩展到x的某个元素。上述部分赋值u称为MIPE（最小不可行部分赋值）。定义4（完全堵塞）。域X {0，1}mH是完全阻塞条件，当且仅当阻塞图是强连通的。Nehring和Puppe[NP02]的结果导致[DH10a]。当单调性条件被添加到通常的条件中时，他们已经获得了二进制不可能域的完整分类。如果在任何情况下，对于每个问题j，如果投票人决定将他/她在该问题上的立场转换为当前的聚合立场，那么聚合器被称为单调的。定理4（Nehring和Puppe[NP02]）。非退化X 关于IIA+幂等性+单调性+非独裁性，{0，1}是一个不可能域，当且仅当X是完全锁定的。E.Dokow和R.Holzman：定理5（E.Dokow，R.Holzman[DH10a]）最终证明了没有单调性条件的二元计算的完整特征。让X {0，1}m，非退化。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:24:59

那么X是关于IIA+幂等性+非独裁的一个可能性域，当且仅当X是全锁的且不是一个有效子空间。Dokow和Holzman在通用D[DH10b]方面也取得了重大进展。在近特征化中，他们对非二进制谓词使用了总阻塞性的推广，这与二进制概念相似但更复杂，我们将定义推迟到第10.1节（定义17）。我们还需要定义关系X的一个条件，这在宇宙代数文献中被称为2-可分解性。对于[DH10b]中的同一概念，我们采用了这个术语，而不是“非多重约束”表达式。定义5。对于D上的m元关系X和1≤ k<`≤ m、让prk，`X={（uk，u`）|（u，…，嗯）∈ 十} 。如果对于任何元组X=（X，…，xm），关系X称为2-可分解的∈ DMWEX∈ X当且仅当（xk，X`）∈ prk，`X代表所有1≤ k<`≤ m、备注1。巧合的是，在[DH10b]中也出现了“2-可分解”的表达，但含义截然不同。定理6（E.Dokow，R.Holzman[DH10b]）。让X Dm，非退化和非二进制（有一个1≤ J≤ 我认为| prjX |>2）。如果X完全被阻止且不可2-分解（见定义5），那么X是关于IIA+支持性+非独裁的不可能域。定理7（E.Dokow，R.Holzman[DH10b]）。让X 马克。如果X是非退化的，并且不是完全封闭的，那么X是关于IIA+支持性+非独裁的可能性域。3.我们的研究结果尽管多科和霍尔茨曼取得了令人印象深刻的进步，但仍有一些重要问题有待解决：1。当| D |>3时，完成支持性案例的描述。（在[DH10b]中，|D |=3的情况得到解决。）2.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-5-8 07:25:02

用幂等条件解决| D |>2的情况。我们从代数理论中得到启发，并将其与[DH10b]的思想结合起来，得到了非二元情形的完整特征，以及支持性和幂等性条件。定理8。让X Dm，非退化和非二元。如果X完全被阻止，那么X是关于IIA+支持性（幂等）+非独裁的可能性域，当且仅当不存在支持性（幂等）非独裁IIA聚合器，且最多有三个（| D |）投票者。描述（据我们所知，这是第一次）允许算法确定ifX是关于支持（幂等）条件的不可能域。小工具。事实证明，我们可以用一组小工具的双重方式来描述不可能域。我们的新描述为不可能提供了证据，但在投票理论的背景下还没有被更早地了解。Gadget（或连接查询）是在本地翻译实例（逐项）时用于减少约束满足问题的表达式。它们是存在量化的从句组合，其中每个从句都是一种关系。这种解释中的关系被视为不一定是布尔变量上的布尔值函数。gadget的语法是：R（~x）=~y:S（~x，~y）∧ . . . ∧ Sk（~x，~y）（每个Siin效应只取决于~x，~y的子集）它们的目的是表达给定关系集合中的新关系。D.Geiger[Gei68]的一个定理建立了一组关系的聚合器的不存在与Γ-gadget（即所有关系都来自Γ或“=”关系）的存在之间的联系。这个定理是P.Jeavons，A.A.Bulatov，A.A.Krokhin，D.A.Cohen，M.提出的约束满足问题代数理论的支柱。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:05

库珀、M.吉森[JCG97、Jea98、JCC98、BJK05]和其他几位研究人员。图1:multi-sorted Not All Equal（NAE）小工具，用于表示x（类型1）和x（类型3）之间的多重排序不等式关系。变量Yan和Yar是存在界的（它们也被设置为常数）。这个小玩意是我们证明阿罗定理的核心。这也是我们的出发点。在通用代数（IIA）中，聚合器被称为多态性。它们与我们介绍的聚合器不同，因为它们是单排序的：f=f=…=调频。阿尔及利亚文献[BJ03，Bul11]也研究了多分类多态性，即FJ可能不同的情况。在处理多排序多态性时，所有关系和小工具也必须是多排序的。在多排序世界中，我们首先必须为每个变量声明一个类型。变量的类型与编程语言中的用途相同：调用函数时，被调用变量的类型必须与函数声明中的类型匹配。本着同样的精神，我们构造（或提供给我们）的每一个多排序的l元关系R都必须有一系列的l（不一定是不同的）类型。我们可以称之为类型声明。类型必须一致：小工具中任何关系出现时涉及的变量类型必须与类型声明匹配。在本文中，我们证明了盖革定理的多排序版本（见第4节）。这使我们能够通过生产一系列的小配件来验证不可能的结果。如果我们想证明XQmjDjis是一个不可能的领域，我们需要为某个“完整”的（多排序）关系集构造X+小工具。在这里，上一个索引中的“+”指的是使用赋值关系的权限（即“x=a”，其中a∈ 除了X之外，我们的小工具中还有Dj（用于类型j变量）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:09

在所有情况下，X都必须被视为一个多排序关系，所有组件（参数）都有不同的类型。demponence约束用X+的“+”编码。或者，小工具重新格式化中的支持性条件转换为允许在小工具中使用任意一元关系。当我们允许后者时，这个小工具就是Xf小工具。定理9。对于每个D和m，都有一个多排序关系的固定集P=P（D，m），X Dmis是一个关于IIA+幂等性（支持性）+非独裁的不可能域，当且仅当我们可以用一个gadget来表示P的每个成员，该gadget的联合体只有（适当的多排序）X+-（Xf）-子句。此外，辅助变量的个数由某个显式函数φ（m，|D |）上界（m中的单指数）。更详细的定理在定理17中重述，并在第6节中得到证明。我们的描述允许我们以两种不同的方式在有限时间内计算X是否是不可能域（无论是在弱域还是在支持域中）：要么通过检查聚合器（最多一定数量的参数）（定理8），要么通过检查小工具（最多一定大小）（定理9）。我们的小工具特征化的一个主要应用是，我们可以通过仅仅展示几个小工具（而不是试图排除一大组聚合器）来证明域X的不可能性。在某些情况下，我们可以利用对称性，根据特定问题定制小工具。我们可以通过小工具排除大多数聚合器，而直接处理其他聚合器。使用小工具，我们可以显示由{（u，…，um）定义的成对区分关系∈ Dm | uk6=u`（1≤ k<`≤ m）当| D |>m时，}是不可能域≥ 2当| D |=m时≥ 3关于IIA+幂等性+非独裁条件。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:12

在[DH10b]中，这仅在IIA+支持性+非独裁条件下得到证明，而[FF11]仅在| D |=m>2时证明上述情况。一些作者认为我们讨论的可能性概念过于宽宏大量。研究了几个进一步的限制，例如[Kal02]。例如，Dokow和Holzman质疑定理5中出现的{0，1}m的线性子空间是否真的应该被视为可能性域[DH10a]。第12节我们提出了一个新的聚合器类，它加强了非独裁的概念。我们的新定义直接来自代数理论，并具有许多可取的性质。虽然Dokow和Holzman完全解决了二元计算的问题，但宇宙代数给出了他们定理的一种更明确的形式：定理10。让X {0，1}mnon退化。那么X是一个关于IIA+幂等+非独裁的不可能域，当且仅当X被完全阻塞并且它不是一个有效子空间。如果X没有完全被阻止，那么对于所有1≤ J≤ m以下情况之一：1。存在一个f，使得fjis是半格运算u∨ v还是u∧ v、二,。有一个f，使得FJI是多数操作（u∨ v）∧ （五）∨ w）∧ （w）∨ u），3。有一个f，使得fjis是Mal’tsev操作u- v+w模式2,4。代数理论一个关键的观察结果是，如果我们转向多排序关系、小工具、多态性等，而不是更常见的单排序关系，代数理论可以在赋值聚合上下文中工作。多重排序关系不同于通常的关系，因为我们考虑的关系的每个组成部分都有一种类型。每种类型b都有一个指定的范围集Db。在不丧失一般性的情况下，我们可以假设允许类型的集合是[t]={1，…，t}，其中t是一个固定的正整数。对应的是D，Dt。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:16

让XQmj=1Dτj，其中τj∈ [t] 一个人≤ J≤ m、我们用（X，τ）来表示X，其中τ=（τ，…，τm），以表明它是多重排序的，以及其成分的类型。（在我们的赋值聚合设置中，t=m，Dj=prjX，X的类型将是（X，（1，…，m））。）定义6（小工具，多分类）。我们定义了一个类型集[t]，{Db}b∈[t] 。如果存在多排序的小工具表达式R（x，…，xk）= Yyk:R（z1,1，…，z1，k）∧ . . . ∧ Rp（zp，1，…，zp，kp），其中每个Ri要么来自Γ，要么来自多排序等式关系（x=y，（b，b））（因此对于某些b，类型（x）=类型（y）=b）∈ [t] 。变量z1,1，zp，集合{x，…，xk}中的kpare∪ {y，…，yk}。在CSP的代数理论中，投票函数被称为多态性。根据它们的代数性质，对它们进行了广泛的研究和分类。在更常见的单排序情况下，我们被迫用相同的函数汇总每个问题。在多排序的情况下，不同的类型被独立地聚合：我们有和类型一样多的聚合器函数。（即使对于两种类型的SA 6=b，我们有Da=Db，聚合器Fa和FB可能会有所不同。）这些正是我们在评估聚合设置中需要的多态性。定义7（多排序多态性）。固定t，{Db}b∈[t] 。设（X，τ）为多排序关系，其中τ=（τ，…，τm）∈ [t] 修理≥ 1.A系列fb:Dnb→ Db（1）≤ B≤ t）如果元组（fτ，…，fτm）是关系X的IIA聚合器，即它需要Xninto X，则函数的集合称为（X，τ）的多排序多态性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-5-8 07:25:19

更一般地说，集合fb:Dnb→ Db（1）≤ B≤ t）如果{fb}b，则函数集合是关于一组多排序关系（每个关系都在同一固定类型集合上）的多排序多态性∈[t] 是Γ中每个关系的多排序多态性。笔记上面概括了单排序多态性的概念，当t=1和D=D时，也可以选择t=m，Dj=Prj（X），并键入Xas（X，（1，…，m））。定义8（MPol）。Fix[t]和{Db}b∈[t] 。多排序关系集合Γ的所有多排序多态性集合用MPol（Γ）表示。定义9（MInv）。Fix[t]和{Db}b∈[t] 。由多排序聚合器函数的集合F保持的所有多排序关系的集合用MInv（F）表示。定义10（h·i）。Fix[t]和{Db}b∈[t] 。对于一组多排序关系，我们定义：hΓi={（R，τ）|（R，τ）多排序gadget-简化为}现在我们可以陈述我们的多排序盖革定理：定理11。Fix[t]和{Db}b∈[t] ，并设Γ，Γ为（可能为有限）多排序关系集，设F，Fbe为（可能为有限）多排序聚合器集。然后1。MInv（MPol（Γ））=hΓi2。Γ Γ==> MPol（Γ） MPol（Γ）3。F F==> MInv（F） MInv（F）证明。让我们首先回顾一下单排序盖革定理：定理12（D.盖革[Geiger[68]）。固定D，并让Γ，Γ成为函数集上的关系集，让F，Fbe（可能是有限的）函数集，这样每个函数都来自于一些D次方toD（即D的聚合函数）。然后1。Inv（Pol（Γ））=hΓi2。Pol（Inv（F））=[F]3。Γ Γ==> 波尔（Γ） Pol（Γ）4。F F==> 投资部（F） Inv（F）为了将我们的多排序版本翻译成上述单排序版本，我们首先定义=D˙∪D˙∪ · · ·˙∪Dt，其中Db是类型b的范围。如果最初的Db不是不相交的，我们会使它们不相交，而不会失去通用性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:24

非空的多排序关系X Dτ×···×Dτmca现在可以解释为单排序关系XD 马克。我们注意到，将它们视为集合，X和XD是完全相同的。XD中的索引D只是提醒我们，我们将XD视为D中的单个排序关系，而将X视为（X，τ）。由于Dbs是不相交的，因此从任何此类XD6= 我们可以恢复每个坐标的类型（XD的单个元素的组件已经提供了这个信息）。如果Γ是固定类型集[t]上的一组多排序关系，那么让ΓDbe是X∈ Γ.为了b∈ [t] 我们介绍了一元关系tbd（在单排序世界中）：Tb（u）←→ U∈ 换句话说，Tb（u）表示“在多排序的世界中，u有b型。”对于关系集合{T，…，Tt}，我们引入符号Θ。定义11。允许 D上的任何一组关系，使得Θ . 那么对于任何多态性f:Dn→ D of 还有b∈ [t] 我们可以定义fb:Dnb→ Dbas fb（x）=Dnb上的f（x）。笔记我们知道DNB上的f从DBS中获取值，因为它是Tb的聚合器∈ .我们现在有：引理13。设Γ是固定类型集[t]上的任意多排序关系集，其符号如前所述。那么以下是等价的：1。（f，…，ft）是Γ的多排序多态性；2.序列f，如定义11所述，FTA是由以下因素的某些多态性引起的： = ΓD∪ Θ.我们不能证明这个简单的引理。回到定理11的证明，唯一的挑战是证明1。从2号开始。三,。这是显而易见的。根据已知的复合引理（多态复合，gadgets）可知，minv（MPol（Γ））我必须向另一个方向展示安全壳。定理12给出了inv（Pol（ΓD∪ Θ））=hΓD∪ Θid在这里，h·id中的下标表示该小工具一代是在单一排序的世界中获取的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:28

我们的证明方案是将hΓi与hΓD联系起来∪ ΘiDand MInv（MPol（Γ））至Inv（Pol（ΓD）∪ Θ)).我们可以从ΓD生成哪些非空关系∪ Θ，即hΓD的元素是什么∪ Θi？这组发电机的Agadget的形式为（x，…，xk）= Yyk:R（z1,1，…，z1，k）∧ . . . ∧ Rp（zp，1，…，zp，kp）（1），其中每个Ri要么来自Γ，要么来自Θ或=关系。定义12。我们说（1）中的（x-或y-）变量z的类型为b，如果当赋值的共轭项（不含存在量词）保持时，z的值为Db。换句话说，在连词中加上tb（z）并不能消除连词中任何令人满意的赋值。从aΓD开始∪ Θgadget（回忆一下，这是一个单独排序的gadget）只有D个变量，任何变量都没有先验类型限制（除了整个D）。然而，如果变量z与关系SD有关，其中S是来自Γ的关系，则S为该变量提供了类型b：如果z为6，则SDnever不成立∈ Db，所以我们不妨将z限制为Db。现在假设有一个变量zsuch，它在（1）的右边包含一个关系z=zz和一个已经受限的z。那么zmust也来自Db。当然，这样的方程链也会对链末端的变量强制执行类型。最后，任何关系Tb（z）都会在z上强制执行类型b。总之，我们可以将类型b分配给变量z if1。Tb（z）出现在小工具中；2.z出现在类型为b的ΓD约束中；3.有一系列等式关系，从任何限制为b型的变量开始（1.或2.）这导致了z。我们注意到，一个变量不能有两种不同（即相互矛盾）的类型。类型中的任何矛盾都会使R不可维护（即空关系）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:31

因此，R相当于一个“类型化部分”和一个“非类型化部分”的直接乘积：R=Rtyped×（w1,1=·s=w1，s）×·wl，1=·wl，sl）|{z}非类型化部分wi，js是变量，非类型化（或类型化）部分可能不存在。第一点-3.也给thatRtypedis一个语法上可识别的R部分，它是通过从右边删除一些变量和术语而产生的。尽管Rtypedis是一个ΓD-gadget（回想一下，Γ是一个由类型化关系集Γ构造的非类型化关系集），但由于其语法，我们也可以将其解读为（类型化的）Γgadget，此外还有完全相同的语义（这意味着Rtypedas a set与我们将公式解读为Γ-gadget时完全相同）。因此，Rtyped[被视为一种多排序关系]∈ hΓi.接下来我们宣称∈ MInv（MPol（Γ））-→ 研发部∈ 投资部（波兰）∪ Θ)).左侧显示R由所有多排序多态性（f，…，ft）保持∈ MPol（Γ））。我们有f∈ 波尔（ΓD）∪ Θ）当且仅当其成分序列（如定义11所示）（f，…，ft）∈ MPol（Γ）。所以RDI由所有f∈ 波尔（ΓD）∪ Θ），证明我们的主张。通过单排序盖革定理（应用于ΓD∪Θ）我们从第三次世界大战开始∈ 投资部（波兰）∪Θ）），我们也有那条路∈ 赫德∪ Θi.在前面的两段中，我们已经看到，那么Rd的形式必须是Rtyped×（α1,1=···=α1，s）×·····×（αl，1=··=αl，sl）。但由于RDA的所有组件都是类型化的，所以只有类型化的部分（RD=Rtyped=R作为集合）。所以R∈ hΓi.5小工具描述不可能盖革的Galois连接（及其多排序版本）发出这样一个信息：我们可以从一组关系（或从单个关系）创建的小工具越多，这组关系的聚合器就越小。不可能域X没有任何非平凡的聚合器，因此X被期望生成所有关系。对于科塞来说，更让我们兴奋的是相反的情况。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:34

如果我们可以把所有关系写成由X和一些简单关系组成的小工具，那么X一定是一个不可能域。然而，还有一些工作要做：1。我们需要理解幂等性（支持性）条件的作用。2.我们想找到一个最小的（出于算法原因，但也为了方便）小工具集，它已经暗示了X的不可能性。5.1幂等性和支持性条件幂等性和支持性条件对应于向我们的关系基集中添加额外的关系，我们从中构建证明X不可能性的小工具。我们的基集是原始的{X}。对于幂等条件，我们添加所有赋值关系；对于支持条件，我们添加所有一元关系（定义如下）。定义13（一元关系，Xf）。多重排序的一元关系是（x）∈ A、（A）），其中∈ [t] isa类型和A 爸爸。对于多排序关系X，我们将X定义为包含X的关系集，以及类型集[t]、{Db}b的所有一元关系∈[t] 定义了X。定义14（分配关系，X+）。多排序赋值关系是（x=v，（a））形式的一元关系，其中v∈ Da（即| A |=1）。X+是一组关系，包括X和类型集[t]，{Db}b的所有赋值关系∈[t] 定义了X。引理14。一个多排序函数g=（g，…，gt），其中ga:Dna→ Da是幂等的（意思是每个GAI都是幂等的）当且仅当它聚合了所有类型的所有赋值关系。它是支持的，当且仅当它聚合了所有类型的所有一元关系时。我们省略了这个已知陈述的简单证明。5.2原始问题的翻译在用小工具描述它之前，我们用一小段时间来讨论代数语言中“不可能”的确切概念。引理15。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-5-8 07:25:37

以下投票理论和代数条件是等价的：代数投票理论 Dmis是一个关系X Dmis a Domainf=（f，…，fm），其中fj:Dnj→ 流行音乐播音员Herdj=定义的prjX（将D限定为DJ很重要）。IIA聚合器函数f:Xn→ 十、 1.≤ K≤ n：所有的fjare投影在他们的坐标上。下面的投票理论和代数问题是等价的：代数投票理论判定X是否具有决定X是否具有幂等（支持）幂等（支持）非独裁非独裁多排序多态性。IIA聚合器。如果上述问题的答案是“否”，那么X是一个不可能域。5.3根据引理14、15和我们的多排序盖革定理（定理11），不难证明：引理16。域X 就IIA+幂等性（支持性）+非独裁而言，当且仅当所有多排序关系都可以生成为多排序X+（Xf）-小工具时，Dmis是不可能的。这里t=m，Dj=prjX表示1≤ J≤ 而X的类型是（X，（1，…，m））。然而，所有（多排序）关系的集合非常大！幸运的是，我们可以选择一个生成所有关系的有限子集（实际上，以许多不同的方式），只考虑这些就足够了。定义15（非二进制或关系）。我们定义了多重排序关系Ru，vk，`只有当x=u和y=v同时保持时，它才是不成立的（x有k型，v有`）。信息公式：Ru，vk，`（x，y）=（x=u）∧ y=v，（k，`）。定义16（多重排序并非所有相等的关系）。只有当Da=Db=Dc={0,1}时，才能定义A、b、c型上的多排序NAE关系。在这种情况下，a，b，c（x，y，z）=（|{x，y，z}|>1，（a，b，c））。我们现在准备陈述我们的小工具对不可能域X的描述：定理17。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:40

让X 不退化。设t=m，τ=（1，…，m），j型beDj=prjX的范围。那么X是关于IIA+幂等性+非独裁性的不可能域，当且仅当每1有（X，τ）+-表示Ru，vk的gadget≤ k、 `≤ MU∈ prkX，v∈ pr`X.此外，对于某些1，如果| Dj |=2≤ J≤ m、我们还需要添加多排序的NAE gadgeton类型（j，j，j）。类似的陈述，当我们用“支持性”替换“幂等性”时，需要用（X，τ）f.6替换（X，τ）+。首先，我们给出定理17的证明。我们展示了非平凡的方向，也就是说，如果我们能创造出定理17所要求的所有小工具，剩下的唯一多态性就是独裁。备注2。即使是hΓi中的一个小玩意也可能产生严重后果。例如，如果我们可以在两种不同类型的a和b（使用通用字母表）之间构造相等小工具（x=y，（a，b）），任何多排序多态性（f，…，ft）∈ MPol（Γ）必须具有相同的a和B成分。我们将在本节末尾证明这一点。我们证明定理17的方法是开始创建小工具，并将它们用作“子程序”，以创建更多的小工具。下面的引理表示，对于任何固定的1≤ k、 “<t来自Ru，vk`∈ hΓi引理18中，hΓi one可以构造类型为（k，`）的所有多排序二元关系。让我≤ k、 `≤ t和（S，（k，`）是包含在prkX×pr`X中的任何多排序关系∧（u，v）6∈SRu，vk，`。我们省略了直接的证据。注意，没有什么能阻止我们在引理中设置k=`的，在这种情况下，我们得到了所有的二元关系（R） Dk）。hΓi中这些关系的存在说明了Γ的（多排序）多态性是什么？他们说了很多。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-5-8 07:25:44

事实上，如果dk的大小至少为3，那么这个不相等的关系（x6=y，（k，k））就排除了所有的幂等（以及所有支持的）多态性，而不是该类型的独裁：引理19（不等于gadget引理）。假设（（x6=y），（k，k））∈ hΓi.那么对于每一个f=（f，·ft）∈ MPol（Γ）它必须认为FKX是prkX上的独裁政权。上面的引理和引理18同素膜20。假设| prkX |≥ 定理17的条件成立，所以我们可以创建所有的Ru，vk，`from（X，τ）+（分别来自X，τ）f）。那么X的任何幂等（支持）聚合器f=（f，···，ft）的kthcomponent必须是独裁。如果| prkX |=2怎么办？然后NAE小工具可以用来处理同样的事情。引理21（并非所有引理都相等）。假设多重排序的关系并非都相等（|x，y，z |>1）∧ x、 y，z∈ prkX，（k，k，k））gadget简化为一组多排序关系。那么对于everyf=（f，··，ft）∈ MPol（Γ）它必须认为FKX是prkX上的独裁政权。在定理17的条件中，有一个明确指出，当| prkX |=2时（|x，y，z |>1）∧ x、 y，z∈ prkX，（k，k，k））gadget可以从（X，τ）+（分别从X，τ）f）构造，以使引理21适用。把引理20和引理21放在一起，我们得出结论，如果定理17承诺的小工具都存在，那么每个多排序多态性（f，…，fm）的所有组件都是各自PRJX上的独裁。为了完成定理17的“如果”部分，我们需要证明的是，这些独裁政权由相同的指数K（独裁者）控制。假设情况并非如此，让k和`是由Kthvoter指定的fkis和f`由投票者l6=k指定的组件。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:49

因为X是非退化的（所以prkX和pr`X的大小至少有两个），并且因为K¨onig定理（或者简单地说是基本组合定理），所以应该有u，v∈ prkX和u，v∈ 例如：1。u6=v和u6=v；2.X中有一个元素U表示k和uon`；3.X中有一个元素V取k和von`。现在让我们汇总一组投票，全部来自{U，V}，但Kthvote是U，Lthvote是V。然后（f，…，fm）将这个输入聚合到Z，使得kthissue聚合到u，thissue聚合到v。现在请注意，Ru，vk，`代表u和v，但不代表Z，这是一个矛盾，因为每个聚合器都必须保持所有小工具都可以从X+（Xf）构造，尤其是Ru，vk，`。定理17证明的“如果”（非平凡）部分到此结束。在本节的其余部分中，我们假设对于两种类型a，b∈ [t] 我们有Da=Db（相当于Da，Db之间的1-1对应关系“=”。我们证明，从一组（多排序）关系中构造a型和b型之间的“=”小工具的能力意味着对于Γ的每一个多态性（f，…，ft），我们都有fa=fb。这可能很有用，因为代数理论主要是针对单排序多态性开发的。引理22（等式小工具引理）。设Γ是一组类型为set[t]的多排序关系。假设对于类型a和b，我们有Da=Db，并且多排序等式关系（x=y，（a，b））gadget减少为Γ。然后对于每一个f=（f，·ft）∈ MPol（Γ）它必须认为fa与fb相同。证据我们需要证明，对于每个u=（u，…，un）∈ 它认为fa（u）=fb（u）。以一个武断的u∈ 脱氧核糖核酸f是（x=y，（a，b））的多排序多态性。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:52

这源于以下事实：f=（f，··，ft）是Γ的多态性，（x=y，（a，b））gadget减少为Γ。因此，由于表格的每一行都是a型bu=uu=u。。。un=UNF（u）=fb（u）在实心水平线上方满足（x=y，（a，b））关系，我们可以对表格的两列应用多态性F。现在，正如所讨论的，f必须保持关系（x=y，（a，b）），sofa（u）=fb（u）。7示例：Arrow的TheoremLet a={a，…，Ak}表示一组k项，并让sk成为对应于k集合的域！A上的不同线性顺序，我们在下面描述。每个投票者都必须按照某种线性顺序投票，而这些选票必须聚合成一个单一的线性顺序，即“社会的选择”我们不是按原样（比如a<a<a<a）来考虑线性顺序，而是将其表示为一个序列K对应于形式<A？的问题的二进制位置，A<A，一-1<An？（另见第2节）。当“<”是a上的线性顺序时，这些问题的答案（0=否；1=是）以有效评估的形式唯一地（甚至冗余地）编码“<”。所有有效计算的集合（这些是长度的二进制向量）N) 正是这种关系 {0，1}（n）。Arrow著名地展示了：定理23（Arrow[Arr50]）。当k≥ 3.没有聚合器f:Snk→ SKN≥ 2满足IIA+幂等+非独裁。很容易看出，不可能简化了SKK的不可能性≥ 3.下面我们将用小工具的方法证明定理23，当k=3时。在A<A？A<A？A<A？basis（将“A<A？”替换为“A<A？”不会改变问题）我们有：S={001、010、011、100、101、110}=NAE（并非全部相等），因为箭头允许用不同的聚合器聚合不同的坐标，所以我们查看Sas与类型集[3]的多排序关系。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:55

我们需要证明，多排序关系集S+的唯一多态性是投影（独裁）。在第3节中，我们为关系（x=y）、（1,3））创建了一个小工具。让我们用R来表示它。通过对称性，S+小工具也存在于R=（，（x=y），（1，2））和R=（，（x=y），（2，3））。然后是小玩意x:R（x，x）∧ R（x，x）表示（x=x，（1，3））（见图2）。我们可以类似地表示任意（xa=xb，（a，b））为1≤ a<b≤ 3.一旦我们产生了这些关系，通过引理22，我们得出结论，S+的每一个多排序多态性都必须是一个单排序多态性，即形式（f，f，f），众所周知，NAE的所有单排序幂等多态性都是独裁。图2：表示x=x的小工具。8示例：成对差异我们继续说明如何使用手工制作的小工具来证明特定领域的不可能性定理：定理24。设D和m为| D |>m=2或| D |=m≥ 3.定义={（x，…，xm）∈ Dm | x，xmare pairwise distinct}那么X是关于IIA+幂等+非独裁条件的不可能域。在[DH10b]中，这个定理是在IIA+支持性+非独裁条件下证明的。这个定理的一个特例，即| D |=m≥ 3，可以从[FF11]中的结果得出。当m=2和| D |=3时，我们给出了一个小工具证明，这在某种意义上是参数中最难设置的。在这种情况下，关系X [3] 是（1，2）型的二元关系，我们必须证明MPol（X+）只包含投影（独裁）。我们注意到，这种情况下的问题本质上相当于表明，只要允许赋值约束，三部图的三个着色是NP难的，即允许我们声明“顶点v有颜色c”。如果我们放弃二部条件，那么这个问题就是众所周知的NP难问题。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:25:59

二部条件来自问题的多排序性质：关系X只能连接类型1变量和类型2变量。首先，我们为关系（x=x=2），（1，1））创建一个小工具。显然，根据对称性，任何（，（x=y=a），（b，b））都存在小工具，其中1≤ A.≤ 3和1≤ B≤ 2.图3：实现这一点的小工具（见图3）对应于以下公式：R（x，x）=Yy:X（X，y）∧ X（X，y）∧ X（y，y）∧ X（y，y）∧ X（y，y）∧∧X（y，y）∧ X（y，y）∧ （y=3）∧ （y=1）∧ （y=2）不难检查R是否实现了（x=x=2），（1，1））关系。现在让我们用Rba来表示关系（x=y=a），（b，b））。然后Rb（x，y）∧ Rb（x，y）∧ Rb（x，y）表示（x 6=y，（b，b））关系。最后，gadgetT（x，x）=y、 y:（x6=y）∧ （x6=y）∧ （y6=y）∧ X（y，X）∧ X（y，X）表示（X=X，（1，2））（见图4）。一旦我们产生了这个关系，通过引理22，我们得出结论，X+的每一个多排序多态性必须是一个单排序多态性，即形式（f，f）。众所周知，x 6=y（单排序）关系的唯一幂等多态性是独裁。图4:equality Gadget 9 Binary evaluation在本节中，我们首先将完全封锁条件转化为代数语言，然后使用它重新审视二进制评估的情况，给出E.Dokow，R.Holzman分类定理的另一种证明，并指出定理10.9.1完全封锁及其后果定理25的证明。让X {0,1}mbe完全阻塞（见定义4）且不退化。设（X，τ）为类型集[t]中X的变量的任意类型，Da={0，1}≤ A.≤ t、我们还假设使用了所有类型。那么对于所有人来说≤ a、 b≤ t:（x=y，（a，b））（多排序）小工具减少到x+。证据

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-5-8 07:26:02

回想一下，总阻塞条件意味着在顶点集V=[m]×0，1}上，我们有一个强连通图定义如下：有一条来自（k，) ∈ V到（`，) ∈ 其中k6=`当且仅当存在：（i.）子集S [m] 这样k，`∈ S和（ii）a（部分）评估美国→ {0,1}英国= u`=1- 这样就不会把u扩展到x中的任何完整求值x，但是如果我们对u的任何一位求值，那么得到的部分求值就会扩展到x的某个元素。让我们关注有向边（（k，), (`, )) 如上所述，S={k，`，S，…，sq}（我们将这S乘以k，`，, ), 创建gadgetEk，`，,（xk，x`）=是的，ysq，~y:X（xk，X`，ys，…，ysq，~y）∧ （ys=us）∧ . . . ∧ （ysq=usq）在这里，我们试图通过索引来表示变量在x中的位置，但符号有一些滥用。特别是，~y收集m- 2.- 不在S={k，`，S，…，sq}中的X的q变量。Weremark表示变量的类型是由它在X中的位置唯一决定的。然后我们有，`，,(, ) = 1，Ek，`，,(, 1.- ) = 0，Ek，`，,(1 - , 1.- ) = 所有这三个方程都来自于u:S→ {0,1}英国= u`=1- 是一个基本上不满意的部分赋值，因此，如果我们只改变其中一个uk的值，u`，赋值就变得令人满意。现在考虑一个链（（k，), （k），)), （（k，), （k），)), . . . , （（kt）-1.T-1），（kt，t））图中的边，我们已经为其生成了关系Ek，k，,, . . . , Ekt-1千吨，T-1.上面是助教。创建小工具（xk，xkt）=yk，ykt-1:Ek，k，,（xk，yk）∧ . . . ∧ Ekt-1千吨，T-1.t（ykt-1、xkt）很容易看出输入是一致的。如果我们设置xk=然后所有的YKIV变量都被强制接受i、最终迫使xkt=t、另一方面，R（1- , 1.- t） =1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-8 07:26:05

要显示这一点，将所有YKIVARIABLE设置为1是足够的- 在上面公式的右边。由于块度图是强连通的，对于任何a，b∈ [t] 类型（xk）=a，类型（x`）=b≤ k、 `≤ 不管怎样K`∈ {0，1}我们现在可以构建小工具Ra，b，,这迫使x`=`只要xk=kand还允许xk=1- k、 x`=1- `作业和一个小工具Ra，b，1-,1.-这迫使x`=1- `只要xk=1- kand还允许xk=k、 x`=`分配西娜，b，,∧ 拉，b，1-,1.-实现xk+k=x`+`mod 2。特别是通过选择k=` = 我们已经实现了（x=y，（a，b））关系。例2。设X={000011101110}={xyz∈ {0，1}|x+y+z=0模2}。我们还假设[t]=3，且坐标具有i型。那么最小不可行部分求值（MIPE）都是xyz∈ {0，1}其中x+y+z=1 mod 2。然后，阻塞图是有向完全图（即，每个边的有向边都是双向绘制的）。对于k=1，`=2，k=0，`= 1我们可以创建gadget（基于S={1,2,3}，u=001）：E1,2,0,1（x，x）=y:X（X，X，y）∧ （y=1）这与从S={1,2,3}，u=111（意外地，两个小工具结果相同，所以连接仍然是E1,2,0,1（x，x））创建的E1,2,1,0给出了（x6=y，（1,2））关系，因为人们可以直接检查它。引理26。让X {0,1}m，完全阻塞。然后每一个聚合器f=（f，…，fm）都满足所有fj都是相同的，这是IIA+幂等的。证据设t=m，并将X视为多排序关系（X，（1，2，…，m））。然后（x=y，（k，`））（1≤ k、 `≤ m） gadget通过引理25减少到X+。因为f是X的幂等IIA聚合器，所以我们得到了f∈ MPol（X+）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-5-8 07:26:08

结合以上两件事，接下来的陈述来自引理22。我们注意到（尽管在续集中没有使用它），完全阻塞也会产生所有非等式关系：引理27。让X {0,1}m，完全阻塞。X有类型（X，（1，…，m））。然后X（作为一个多排序关系）生成所有形式的关系（x6=y，（a，b）），其中a，b∈ [t] .9.2定理5的新证明我们给出了定理5有趣部分的新证明（E.Dokow，R.Holzman，[DH10a]），即当X完全阻塞时，它是一个可能性域（关于IIA+幂等性+节点数），当且仅当它是一个有效子空间。新的证明使用了约束满足问题代数理论的结果。引理26给出了当X完全阻塞时，X的所有幂等多排序多态性都是单排序的，我们可以使用Schaefer定理，或者更精确地使用它的代数版本（Hubie Chen[Che09]），来确定Pol（X）中的函数类型：定理28（Schaefer，代数版本）。设D={0，1}和Γ是一组（单排序）关系onD。那么Γ+作为多态性有以下四种操作之一：1。二进制与运算∧;2.二进制或运算∨;3.三元多数运算Maj（x，y，z）=（x∧ y）∨ （十）∧ z）∨ （y）∧ z） )；4.马勒采夫行动- v+w模式2。否则Pol（Γ+）只包含投影（独裁）。定理28给出了当X完全阻塞且X不是不可能域时，情况1之一-4.必须坚持。但是[DH10a]证明了更多，它表明当X被完全阻断时，只有情况4。默认情况下（即没有非平凡多态性）可能会发生。我们提供了一个简短的证明。我们排除案例1-3.如下所示：不包括1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 07:26:11

2：我们证明如果∨ ∈ Pol（X），那么在块性图中，形式（k，1）的节点没有指向形式（`，0）的任何节点的有向边，因此块性图不能强（或无论如何）连接。为此，有必要证明每个MIPE最多有一个变量设置为1。假设xk=x`=1是k6=`的MIPE的一部分，其余的MIPE计算为α。根据定义，我们有任务：xkx ` MIPE rest的rest（1 1αany）从不∈ X（因为它是MIPE）（01α部分）∈ X（因为它是MIPE）（10α部分）∈ X（因为它是MIPE）（0∨ 1 1 ∨ 0α（部分）∈ X（assgnm 2∨ 假设3）那么表格的第一行和第四行相互矛盾。类似的证据表明∧ ∈ Pol（X）阻塞图不是强连通的。排除3：假设X完全被阻塞且主要∈ 波尔（X）。首先我们展示：引理29。如果少校∈ Pol（X）那么X的每个MIPE的长度最多为2。证据考虑一个MIPE S，与我们的假设相反，它至少有三个元素，x，x，x≤ 我≤ 3，而MIPE的其余部分计算为α。然后下表的第一行和第五行一起给出了一个矛盾：xxxrest的MIPE rest（uuuαany）never∈ X（因为它是MIPE）（1）- uuuα（部分）∈ X（因为它是MIPE）（u1- uuα（部分）∈ X（因为它是MIPE）（uu1- uα（有些）∈ X（因为它是MIPE）（uuuαsome）∈ X Maj（assgnms 2,3,4）假设我们有（k）的边，) 到（`，) 在块度图中。由于由引理29产生的这条边的长度为2（不能为1），我们得出结论xk=力x`=. 考虑任何x∈ 十、根据我们的假设，总阻塞图是强连通的，因此有一条从（1，X）到（1，1）的路径- x），根据上述论点，这意味着（1，x）力（1，1- x）通过一系列的边缘，这是一个明显的矛盾。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝