列表H-同态问题的查询复杂度与图H的性质有关

0→∈∈→ ∈∈⊆∈检验列表H-同态吉田雄一京都大学信息学部、PreferredInfrastructure公司yyoshida@kuis.kyoto-u.ac.jp2018年11月13日，摘要设H是一个无向图。在列表H-同态问题中，给定一个具有列表约束L（v）的无向图G，V（H）对于每个变量vV（G），目标是求一个列表H-同态f：V（G）V（H），即f（v）L（v）对于每个vV（G）和（f（u），f（v））E（H）当（u，v）E（G）.我们考虑如下问题：给定一个映射f：V（G）V（H）作为一个预言通路，目标是以高概率判定f是列表H-同态还是远离任何列表H-同态.算法的效率是通过访问f的次数来衡量的。本文根据查询复杂度对图H进行了分类，证明了如下的可测性定理：（i）列表H-同态可用常数次查询可测当且仅当H是自反完全图或非自反完全二部图.(ii)列表H-同态是可测试的次线性查询数当且仅当H是双弧图。（iii）测试列表H-同态需要线性数量的查询，如果H不是双弧图。由2010年MSRA奖学金支持arXiv：1106.3126v1 [cs.DS] 2011年6月11介绍对于两个图G=（V（G），E（G））和H=（V（H），E（H）），称映射f：V（G）→V（H）是从G到H的同胚映射，如果（f（u），f（v））∈E（H），只要（u，v）∈E（G）.在H-同态问题（简称HOM（H））中，给定一个无向图G，目标是判定是否存在从G到H的同态。众所周知，HOM（H）是在P中，如果H是一个二部图，并在NP-完全，如果H不是一个二部图[3，8，21]。列表H-同态问题（List H -Homomorphism Problem，简称LHOM（H））是H-同态问题的一个变种，在这个问题中，我们也给G中的每个顶点v一个列表L（v）<$V（H）。一个映射f：V（G）→V（H）称为G到H的列表同态，如果f是G到H的同态，且对任意v∈V（G），f（v）∈L（v）.目的是判定是否存在从G到H的列表同态f。关于图H与计算的LHOM（H）的复杂性[11，12，13，14]。特别地，LHOM（H）在P中当且仅当H是双弧图[14]。在本文中，我们考虑测试列表同态。[17]见《易经》，见《易经》，见《易经》。在我们的设置中，映射f被给定为oracle访问，即，如果我们指定一个顶点v∈V（G），则预言机返回f（v）。一个映射f称为f-远离列表同态，如果我们必须修改f的至少一个f-分数使f成为列表同态。一种算法被称为LHOM（H）的测试器，如果它能从G到H的2/ 3的随机变量中提取，并且如果它能从G到H的2 /3的随机变量中提取，那么它就具有2/3的随机变量。一个算法的效率是通过对oraclef的访问次数来衡量的。当我们说查询复杂度是常数/次线性/线性时，它总是意味着常数/次线性/线性，|V（G）|，即，f的畴大小。我们可以假设存在从G到H的列表同态。如果否则，我们可以毫不犹豫地立即拒绝在本文中，我们完全分类图H方面的查询复杂度进行测试LHOM（H）. 我们的结果由以下两个定理组成。定理1.1. LHOM（H）是常数查询可测的当且仅当H是非自反完全二部图或自反完全图。定理1.2. LHOM（H）是次线性可测的当且仅当H是双弧图.属性测试领域的核心问题是将属性分为以下三类：可通过常数/次线性/线性数量的查询进行测试的属性我们的结果首先建立了这样一个自然的和一般的组合问题的分类。由定理1.2和文献[14]的结果可知，LHOM（H）是次线性可检验当且仅当LHOM（H）在P中。然而，目前还不清楚是否有一个计算类对应的属性测试与一个常数数量的查询。为了获得我们的结果，我们利用泛代数，它现在是研究约束满足问题的计算复杂性的常用工具（参见，例如，[24]）。本文的另一个贡献是，通用代数方法是非常有用的设置属性测试。相关作品：我们很少成功地获得可测试的属性的特征与一个常数/次线性数量的查询。我们所知道的唯一这样的表征是在所述设计的模型中的用于grappperties的特征[18]。在此模型中，Szemer′di的正则性粗略地说，正则引理给出了一个图的恒定大小的草图。事实证明，一个属性在稠密模型中是可测试的，2˜Σ|A→|A→∈ →⊆→∼一B常数数量的查询当且仅当该属性通过常数数量的草图的并集很好地近似[1]。然而，没有表征是已知的属性可测试的次线性数量的查询。类似地，对于布尔函数的性质，已知几种关于常数时间可测性的部分分类[5，25]。设B是一个关系结构（定义见第2节）。在B上的约束满足问题（简称CSP（B））中，给定另一个关系结构A，目标是求A到B的同态。关于CSP（B）的计算复杂度对B进行分类已经有很多研究（参见例如，[10、22]）。我们可以看到HOM（H）和LHOM（H）是CSP的特殊情况，也有许多关于H的分类结果。HOM（H）和LHOM（H）的计算复杂度（参见，例如，[20、22]）。在k-SAT上测试同态已经被研究[4，16]。在k-SAT中，给定一个CNF公式，每个子句由k个文字组成，目标是找到一个变量的赋值，以满足所有子句。对于某种适当的关系结构B，问题k-SAT与CSP（B）一致.测试k-SAT的同态可以重述如下：给定一个赋值，测试这个赋值是否是一个令人满意的赋值或远离任何令人满意的赋值。是已知2SAT可通过O（n）个查询来测试[16]，而测试3SAT需要n（n）个查询[4]，其中n是输入CNF公式中的变量数。我们可以看到，我们的结果将这些结果推广到一个大的CSP家族。给定一个关系结构B，也很自然地要问一个关系结构A是否与B有同态或远没有同态。 在这里，A作为一个oracle访问。在这种情况下有两种主要模式，即，稠密模型和有界度模型。 在稠密模型中，已知任何CSP在恒定时间内都是可测试的[2]。在有界度模型中，已知Horn-SAT在恒定时间内是可测试的[30，29]，并且查询测试2SAT所需的是Θ（n）[19]，其中n是输入结构A中的变量数。组织：在第2节中，我们介绍了本文中使用的定义。 第3节和第4节分别给出了类似地，第5节和第6节分别给出了2预赛令w：AR是权重函数，使得a∈Vw（a）= 1. 然后，由A我们的意思是我们选择一个元素a概率为w（a）。对于函数f：AB和A'A、我们定义 f′：A′A作为定义域限制在A ′的函数。我们还将w′：A′R定义为W|A′（a）=w（a）/a′∈A′w（a′）. 不，不，不，|A′satisf iesa′∈A′w|A′（a′）=1。关系结构，多态性和代数：词汇表τ是关系符号的有限集合;每个符号都有一个相关的元。一个（有限的）关系结构A，它有一个有限的集合A，它的论域，对于每个n元的关系符号R∈τ， A上的n元关系RA，A对R的解释。 结构A到具有相同词汇τ的结构B的同态是从A的论域到B的论域的映射A：A→B，使得对于每个（n元）关系符号R∈τ和任何元组（a1，. . .，an）∈R，元组（n（a1），. . .，n（an））∈R.对于关系结构B，我们定义HOM（B）为这样的问题，其中给定另一个关系结构A，目标是找到从A到B的同态。 我们表示为|一|A的宇宙的大小，用A表示它的元组的数量，3AA一阿格夫wRwH一名妇女LL关系为了简洁起见，我们使用大写字母来表示相应关系结构的范围A表示A的宇宙）。设R是集合A上的一个关系，若对任意元组a1，. . . ，an∈ R，元组f（a1，. . . ，an）也属于R. 关系R称为f的不变量。如果操作f是关系结构A的每个关系的多态，则操作f是关系结构A的多态。A的所有多态性的集合记为Pol（A）。从操作集合C中Inv（C）表示来自C的所有操作的不变量的集合。一个代数是一个对A=（A;F），由一个集合A，A的论域，和一个运算集合F，A的基本运算组成 从A的基本运算和A上的投影运算得到的运算，即f（x1，. . .，xn）= xi，借助于复合称为A的项运算。项（A）表示的所有项运算的集合A.任何关系结构A都可以与代数Alg（A）=（A;Pol（A））相关联。相反，任何代数=（A;F）对应于一类关系结构Str（），它包括所有具有论域A和Term（A）的结构A一个运算f称为幂等的，如果f（x1，. . . ，x k）∈ {x1，. . . ，xk}，对于任意x1，. . . ，其中k是f的arity。 一个代数称为幂等，如果任何基本运算（因此，术语运算）是幂等的图同态：我们经常将图H=（V（H），E（H））与由论域V（H）和二元关系E（H）组成的关系结构H标识。特别是，|H|为|V（H）|和=|E（H）|.注意，用图术语定义的问题HOM（H）和用关系结构定义的问题HOM（H）类似地，LHOM（H）可以用关系结构来重述。设H是与H相关联的关系结构，并定义HL是通过将所有一元关系SV（H）相加而从H获得的关系结构。然后，LHOM（H）与HOM（HL）重合。 设G是具有列表约束的图{L（v）}v∈V（G）. 设G是对应于G的关系结构. 然后，我们可以定义另一个关系结构G，通过添加一元关系SG<$V（G）从G获得。这里，对于每个（一元）元组（v）∈ SG，存在对应的约束L（v）=SH。最后，我们定义了图H的HL= Alg（HL）。注意代数HL是幂等的，因为H对每个v∈V（H）包含一元关系Sv={（v）}，并且以{Sv}v∈V（H）为不变量的运算一定是幂等的。测试同态：设A和B是关系结构，w：A → R是a∈A（a）= 1的权函数。两个函数f，f：A→ B之间的距离定义为dist（f，f′）=Pr[f（a）/=f′（a）]。对于f：A→B，我们定义findistB（f）=minf′dist（f，f′）其中f′是从A到B的同态。 如果distB（f）≥λ，我们称映射f为λ-far. 针对子集A′→A，我们发现B（f|A′）的最小化使用是在W|A′。我们考虑测试到关系结构B的同态。 输入是（A，w，f），其中A是关系结构，：A→是一个权重函数，a∈A（a）= 1，f：A→B是一个映射。 映射f作为Oracle访问给出。因此，通过指定a ∈ A，oracle返回f（a）的值。定义2.1.一个算法被称为HOM（B）的测试器，如果给定一个输入（A，w，f），它接受2 / 3的witprob bityat，其中f是A到B的homomomo4vwvwvw一个测试器被称为单侧误差测试器，如果它总是接受一个输入（A，w，f），如果f是一个同态。一个算法被称为具有查询复杂度q（n，m，f），如果给定一个输入（A，w，f），它查询至多q（|一|，，）times.我们总是假设q（n，m，n）是n，m上的增函数和n上的减函数。我们可以类似地为图H的HOM（H）和LHOM（H）定义测试者和可测试性，因为它们具有使用关系结构的等价形式化为了方便起见，我们将HOM（H）和LHOM（H）的输入分别写为（G，w，f）和（G，L，w，f），其中G是一个图，{L（v）}v∈V（G）是列表约束的集合，w是权函数，f是作为Oracle访问给定的映射最后给出了双弧图的定义，虽然在证明中没有用到这个定义。设C是具有两个指定点p和q的圆。双弧是一对弧（N，S），使得N包含p但不包含q，S包含q但不包含p。一个图H=（V，E）是一个双弧图，如果存在一族双弧{（Nx，SX）|x ∈ V}，使得对于每个x，y ∈ V，以下成立：（i）如果x和y相邻，则Nx与Sy不相交，Ny与Sx也不相交，以及（ii）如果x不相邻于y，则N x与S y相交，并且N y与S x相交。一个无向图称为自反图，如果每个顶点都有一个回路，如果没有顶点有回路，则称为非自反图已知自反图是双弧当且仅当它是区间图，非自反图是双弧当且仅当它是二部图且它的补图是圆弧图[14]。3可测试图的常数个数在这一节中，我们展示下面的引理，它是引理3.1. 当H是非自反完全二部图或自反完全图时，则这两个指数是LHOM（H）的一个非自反可分解的指数，其最小可分解指数为O（1/2）.设（G，L，w，f）为LHOM（H）的输入。对于顶点v∈V（G），设C（v）是包含v的连通分支.提案3.2. 设（G，L，w，f）为LHOM（H）的输入。 设dist H（f）≥ ∞. 然后，E[distH（f|C（v））]≥100。Proof. Letfbalist-homorphismc losttofanddistv=dist（f|C（v），f|C（v））。Itisclearthatf=distH（f|C（v））。 SicdistH（f）≥0，则有E[distH（f）|C（v））]=E[v]≥。推论3.3。假设当输入图被限制为连通图时，对于查询复杂度为q（n）的LHOM（H），存在单侧误差测试器A. 然后，对于LHOM（H），存在一个单侧误差检验A′，它具有q（q）/q（q）的最小值。Proof. Let（G，L，w，f）是一个整数。我们的一个图A′是这样的：LetS是根据w从G中选出的Θ（1/θ）个顶点的集合。对于每个顶点v∈S，我们在其域限制为C（v）的输入上运行带有误差参数的A如果A对某个v∈S拒绝，则我们拒绝。我们接受其他方式。很容易看出，当f是列表同态时，上面的算法总是接受的，并且querycomplexity是mostq（q）/q。5≥.′∪vw≥ΣΣSincef是S-farfomf1，wehavev∈V，f（v）=bw（v）≥∞/2orrv∈V，f（v）=aw（v）≥∞/2. 我很好，v∈V1，f（v）=aw（v）≥∞/2orv∈V2，f（v）=bw（v）≥∞/2. 在一个新的情况下，这一问题可能会在两周内出现。设distH（f）≠. 根据命题3.2，我们有Evw[distH（f|C（v））]≥100。我们，Pr[distH（f|C（v））≥n]≥nh或ds。 对于具有H（f）的xv|C（v））≥0时，A的平均值与在2/3的位置上， 因此，A′是一个双线性方程，满足1−（1−2/3·λ）Θ（1/λ）≥2/3。引理3.4. 假设对于查询复杂度为q（n）的LHOM（H），如果输入映射被限制为满足列表约束，则存在单侧误差测试器A. 然后，对于任意put，也存在一个单边的有限性系数A′，对于LHOM（H），它的有限性系数为O（1/n）+q（n/2）。证据 设（G，L，w，f）为输入。 我们定义f ′：G → H为f′（v）= f（v）如果f（v）∈L（v），则L（v）中的任何元素，否则注意，我们可以通过查询f一次来计算f′（v），即，f（v）.我们的几何结构A′如下：LetS是Θ（1/θ）的向量，它由G ac cccdongodown构成。我们拒绝如果f（v）/∈L（v），对于某些v∈S。如果不是，我们简单地返回输出，通过A在 fithanerrrrparametern/2上运行。很容易看出，当f是列表同态时，上面的测试总是可以接受的，并且q的复杂度为O（1/n）+q（n/2）。当H（f）≥ 0时，则H（f）≥0.如果dist（f，f′）≥θ/2，则当f（v）∈ L（v）或v ∈S时，A′的解满足1−（1−θ/2）Θ（1/θ）≥2/3的条件.如果f_（i）（f，f′）<≠/2，则对于任意的约束条件，H（f′）≥≠/2. 因此，A′rejectswithprobilitat2/3。引理3.5. 设H是自反完全图。然后，存在单侧误差测试器，LHOM（H）具有二次多项式O（1/n）.证据 设（G，L，w，f）是一个输入，并假设f满足列表约束。然后，我们总是可以接受，因为任何映射都是H的列表同态。引理由引理3.4推导而来。引理3.6. 设K2是两点非自反完全图. 对于LHOM（K2）存在一个单侧误差A，其最小误差为O（1/K2）.证据 设（G，L，w，f）是一个输入，并假设G是连通的，f满足列表约束。注意G必须是二分的才能与H同态，设V1V2是G的二分划。 设a，b是K2中的两个顶点. 然后，我们有两个同态，即， f1和f2，其中f1为|V1a，f1|V2b和df2|V1b，f2|V2型。我们的目标A如下：LetS1（resp. ，S2）是由V1构成的Θ（1/θ）向量空间的集合（分别地， （2）根据W|V1（分别为， W|V2）。 然后，我们检查f（u）=f（v）对于每个u，v∈S1，f（u）=f（v），对任意u，v∈S2，且f（u）不要等。我们接受其他方式。f（v）对任意u ∈ S1，v ∈ S2. 如果他们中的任何人很容易看出，当f是列表同态时，上面的测试总是接受的，并且quurycomplexity是O（1/n）。设dist H（f）≠. 注意，f 1或f 2必须满足列表约束。下面我们假设f1和f2都满足列表约束。当它们中的任何一个都不满足列表约束时，分析是类似的Σ Σ1 2re j ect是at1−2（1−λ/2）Θ（1/λ）≥2/3。我们有6′˜˜˜f= V（G）→V（H），并给出了两个方程.˜f（v）=lea s t2/3.从C orrollary3开始。3和Lemma3。4、LHOM（K2）与hO（1/λ2）问题等价.现在，我们证明了任何完全二部图都是可测试的，具有常数数量的查询。对于两个图G和H，如果（u，v）∈E（G）当且仅当（f（u），f（v））∈E（H），则称映射f：V（G）→V（H）是全同态与同态的区别在于，当（u，v）/∈E（G）时，我们必须有（f（u），f（v））/∈ E（3.7号提案 设h是从H到H′的全同态。 对图G和从G到H′的同态f ′，设f：V（G）→ V（H）是一个映射，使得f（v）是h−1（f ′（v））中的任意元素.则f也是G到H的同态。证据假设f不是同态。 则存在u，v ∈ V（G）使得（u，v）∈E（G）而（f（u），f（v））/∈E（H）. 然 后 ，我们有（f ′（u），f ′（v））=（h（f（u）），h（f（v）/∈E（H′），因为h是全同态，这与f是同态的事实相矛盾。引理3.8。设H是一个图，并假设存在一个从H到H′的全同态h. 如果存在查询复杂度为q（n）的LHOM（H′）的单侧错误测试器，则存在查询复杂度为O（1/n）+q（n/2）的LHOM（H）的单侧错误测试器.证据 设（G，L，w，f）是一个输入，并假设f满足列表约束。我们定义L′=h<$L和f′=h<$f。然后，我们在输入（G，L′，w，f′）上运行LHOM（H′）的测试器，误差参数为。如果f是一个列表同态，那么f′也是一个列表同态，并且测试者总是接受。设dist H（f）≥n，f′是最接近f ′的列表同态.我们定义- 是的f（v）如果f′（v）=f′（v），L（v）中的任何元素<$h−1（f ′（v）），否则。注意，在后一种情况下，L（v）<$h−1（f′（v））不是空的，因为f′（v）∈L′（v）=h（L（v））。因此，在本发明中，f是明确的。我们可以很容易地看到，f满足列表约束的建设。当f ′（v）= f ′（v）时，我们有f（v）∈ h−1（f ′（v））。因 此 ，f是命题3.7的列表同态。这意味着dist（f ′，f ′）≥ dist（f，f）≥ dist H（f）≥ ∞。因此，测试人员拒绝的概率为我们已经证明了当输入被限制为满足列表约束时，LHOM（H）是可测试的引理由引理3.4推导而来。引理3.9 设H是一个非自反完全二部图。然后，存在LHOM（H）的单侧误差检验，其具有最大的互补性O（1/2）。Proof. 由于该索引是从H到K2的一个完全随机的映射，所以LHOM（H）可与引理3.6和3.8中的两个O（1/K2）查询等价。引理3.1的证明 这个主张直接由引理3.5和3.9得出。7log logn----log lognlog lognlog lognlog lognlog logn4具有常数个数的不可测图在这一节中，我们证明下面的引理，它是引理4.1. 如果H既不是非自反完全二部图也不是自反完全图，则测试LHOM（H）需要n次（logn）查询。下面是直接的，因为我们可以通过列表约束自由地限制映射的范围4.2号提案 设H是一个图，H′是H的导出子图. 如果测试LHOM（H′）需要q个查询，那么测试LHOM（H）也需要q个查询。下面的引理在[16]中隐式地陈述，当显示测试2SAT的下限时。引理4.3（[16]）. 设H是一个图，G是一个具有列表约束的图{L（v）}v∈V（G）. 对于顶点u，v∈ V（G），其中u/= v，设R ={（f（u），f（v））|f是从G到H的列表同态}。如果R={（a，c），（b，c），（b，d）}，对于顶点a，b，c，d∈H，a/=b，c/=d，则检验LHOM（H）需要lognlog logn ）查询。我们也使用下面的引理，它是引理6.1的一个特例（见第6节）。引理4.4. 设K3是一个三点非自反完全图. 然后，对LHOM（K3）进行了检验需要n（n）个 查询。注意K3不是一个双弧图。以下两个引理分别处理自反图和非自反图引理4.5。 设H是自反图。 如果H不是完全图，则测试LHOM（H）需要查询次数（logn）。证据设P=（{a，b，c};{（a，a），（b，b），（c，c），（a，b），（b，c）}）是长度为2的自反路，G=（{u，v};{（u，v）}）是具有列表约束L（u）={a，b}和L（v）={b，c}的非自反边. 很容易看出，引理4.3中的关系R变成R=（a，b），（b，b），（b，c）。它遵循测试LHOM（P）需要n次（logn）查询。 根据命题4.2，如果LHOM（H）是可测试的，有一个常数数量的查询，H必须有一个直径为1，这意味着H是一个自反完全图。引理4.6. 设H是一个非自反图。如果H不是完全二部图，则测试LHOM（H）需要n次（logn）查询。证据 设P =（{a，b，c，d};{（a，b），（b，c），（c，d）}）是长度为3的非自反路，G =（{u，v};{（u，v）}）是具有列表约束L（u）={a，c}和L（v）={b，d}的非自反边.很容易看出引理4.3中的关系R变为R=（a，b），（c，b），（c，d）。因此，测试LHOM（P）需要n（logn）个查询。此外，对于非自反三角形T，测试LHOM（T）需要从引理4.4中进行n（n）次查询。因此，如果LHOM（H）是可测试的与一个常数数量的查询，H必须没有一个路径的长度为3或一个三角形的诱导子图从命题4.2。因此，H必须是完全二部图。引理4.1设P=（{a，b};{（a，b），（b，b）}）是一条带环的边，G=（{u，v};{（u，v）}）是一条带列表约束L（u）=L（v）={a，b}的非自反边.然后，引理4.3中的关系R变为{（a，b），（b，b），（b，a）}，并且由此得出测试LHOM（P）需要n次（logn）查询。因此，如果LHOM（H）是用常数查询数可测试的，则H必须是自反的或非自反的提案4.2然后，引理由引理4.5和4.6得出。1998年，8√√′′−15具有次线性数的可测图在这一节中，我们展示下面的引理，它是引理5.1. 设H是一个双弧图。然后，存在LHOM（H）的单侧误差检验器。2.Apixel（n/10）。我们首先描述了一个传播算法来解决CSP。设A和B是两个关系结构。为了检查是否存在从A到B的同态f，我们可以使用以下算法。设k，n是整数，k≤n.对于每个子集U∈A，|U| ≤n，我们跟踪对应于来自A的映射的元组的集合SU|U到B。首先，我们将SU初始化为部分实例A的解的集合|联合然后，对于每个子集U，U∈A，|UU| ≤k，我们在SU中消除元组a，如果a|U′不包含在SU′中|联合我们将继续此过程，直到没有更新发生。这种传播算法被称为（k，n）-Minimality[9]。如果对于某个U<$A，SU变为空，则我们可以得出结论：A与B没有同态。即使当传播停止时没有SU是空的，A也可能不具有到B的同态。如果在这种情况下A与B有同态，则称B有宽度（k，n）。一个三元运算f：B3→B称为多数运算，如果f（x，x，y）=f（x，y，x）=f（y，x，x）=x，其中x，y∈B.已知关联代数Alg（B）允许多数运算的关系结构B具有宽度（2，3）[24]。我们称映射f：A→B<${n}可扩张为同态，如果存在同态f′：A→B使得f′（v）=f（v），只要f（v）∈B. 我们称一个顶点v为违反顶点，如果f（v）/∈ S{v};称一对顶点（v，u）为违反对，如果（f（v），f（u））/∈ S{v，u}。 已知多数运算蕴含以下性质。引理5.2（2-Helly性质，[15]）。设B是一个关系结构，使得Alg（B）允许多数运算。 对于关系结构A和U A，|U |≤ 3，设SU是由A上的（2，3）-极小所得到的元组的集合.若映射f：A→B<${n}不可扩张为同态，则对某个u，v∈f（B），存在一个违反点v或违反对（v，u）.引理5.3（[11]）. 设H是一个双弧图。然后，H L允许多数运算。引理5.1设（G，L，w，f）为LHOM（H）的输入。根据引理5.2和5.3，我们可以假设2-Helly性质。我们的算法描述如下。算法1双弧图H的LHOM（H1：运行（2，3）-极小性，并让SU是为UV（G）获得的元组的集合，|U| ≤ 3。2：LetX是Θ（1/λ）的向量，表示一个连续或连续的向量3：如果n ∈v∈X使得f（v）/∈S{v}，则4：调整输入。5：使Y1、Y2成为Θ（n/θ）的向量的集合，或者将其降到最低。6：如果nv∈Y1，u∈Y2，使得（f（v），f（u））/∈S{v，u}，则7：输入。8：接受输入。Ntethat（2，3）-MimalimatimL. 复杂度为O（列表同态n/10）。很明显，当文件910CN3设distH（f）≥∞.设U是V（G）的一个具有最大权的子集，使得部分同态f |U是可扩展到列表同态的。显然，我们有w（U）+n≤1。LetveavertexinV（G）\U. 从U的最大值中，我们可以选择|U{v}都是t-同态。因此，根据2-Helly性质，v是一个违反顶点或（v，u）是一个违反对，对于某些u∈U。设A是V（G）\U中的违反顶点集，B=V（G）\（U<$A）.注意，对于任意v∈B，对（v，u）对于某个u∈U是违反对。由于A<$B=V（G）\U，我们有w（A）+w（B）≥1−w（U）≥<$。当w（A）≥λ/2时，我们在方程4中选择L，其中p为1-（1-λ/2）Θ（1/λ）≥2/3。当w（B）≥λ/2时，对于B′∈B，我们定义N（B′）={u∈U|v∈B′，（v，u）是违反对}。注意f|U′可扩为列表同态，其中U ′=（U\N（B′））<$B′。因此，从U的极大性出发，我们必须有w（B′）≤w（N（B′））。Letq=|Y1|为|Y2|且dc>0时，将成为一个参数。LetB′=Y1BandF1beventttthatw（B′）≤<$q. 通过计算，我们发现，在给定的条件下，Pr[F1]≤1。不，不，中国日报10证明了w（N（B））≥w（B）≥cn。 设F2为未检测到违反边缘的事件。 然后，Pr[F2]≤Pr[F1]+Pr[F2|F1]≤1+（1−q）q≤1bychosing hidenconstinq=Θ（n/）注意，我们只使用HL允许多数运算的事实。因此，我们的算法也可以用来测试同态到其他CSP承认多数操作，例如，2SAT。6具有次线性数的不可测图在本节中，我们证明了下面的定理，这是引理6.1. 如果图H不是双弧图，则测试LHOM（H）需要进行n（n）次查询。为了证明引理6.1，我们使用了一系列归约。首先，我们定义本节中使用的约简定义6.2. 假设A和B是关系结构。 如果存在函数t1（n，m），t2（n，m）和常数c1，c2满足下列条件，则我们称存在从B到A的（随机）保隙局部约化：存在一个（随机）构造使得给定H O M（B）的输入（J，wJ，fJ），HOM（A）的n个输入ut（I，wI，fI）满足：1 .一、 |我|01- 02 - 03 - 2001（|J|，J.J.），二、02-02|J|，J.J.），3. 如果fJ是同态，则fI也是同态，4. 如果distB（fJ）≥0，则nPr[di stA（fI）≥c1λ]≥9/10，且d5. 对于任意v ∈ I，我们可以通过查询fJ至多c2次来计算fI（v）。引理6.3. 设A是一个关系结构，使得存在一个HOM（A）的测试器，其查询复杂度为q（n，m，n）.如果存在从关系结构B到A的保持间隙的局部约简，则存在HOM（B）的测试器，其查询复杂度为O（q（t1（n，m），t2（n，m），O（n）.Proof. Let（J，wJ，fJ）是HOM（B）的一个整数. Let（I，wI，fI）是由约化给出的HOM（A）的输入（random）。足够大10一˜˜ ˜˜ππ˜ ˜˜我们运行Awithit hhanerrorparameterc1. 如果J是一个比较好的选择，那么A的平均成本是2/3。如果J是非对称的，则A的概率为9/10·2/3=3/ 5。在这两种情况下，我们都可以通过运行A的恒定次数来增加概率，并获得大多数输出。由于我们可以通过查询fJ最多c2次来计算fI（v）的值，因此对fJ的查询次数为tmostO（c2q（t1（n，m），t2（n，m），c1q））。对于一个代数A，我们说HOM（A）是q（n，m，n）个查询可测试的，如果对任何关系结构A∈Str（A），HOM（A）是q（n，m，n）个查询可测试的。引理6.4. 设A是一个关系结构，使得HOM（A）是用q（n，m，n）个查询可测试的. 其中HOM（）也可分解为O（1/n+q（O（n+m），O（m），O（n）q.证据 设B是Str（A）中的关系结构。然后，通过使用以下构造[6，7]，在许多步骤中从A的关系获得B的每个关系1. 删除关系，2. 添加通过置换关系的变量而获得的关系3. 添加相同元数的两个关系的交集4. 将两个关系的乘积5. 添加等式关系，以及6. 添加通过将n元关系投影到其前n-1个变量而获得的关系。因此，足以证明B是可测试的，如果B是由任何这些结构从A.为此，我们给出了从B到A的保间隙局部约简，其中t1（n，m）≤n +m，t2（n，m）≤2m，c1=c2=O（1）. （对于Case5，我们需要执行的操作成本为O（1/N）。）Let（J，wJ，fJ）是HOM（B）的一个输出。我们构造了HOM（A）的整数put（I，wI，fI），使其满足保间隙局部约简的条件自从检查条件（1）、（2）、（3）和（5）是直接的，我们将只检查条件（4）。 对于下面的任何情况，我们定义f I：I → A为最接近f I的同态。然后，我们将构建一个利用f I证明了dist（f I，f I）一定是大 ，并利用dist（f J，f <$J）≥ <$的事实证明了dist（fI，fI）一定是大的。因此，该表格将由一个第6页中的一个页显示。3 .第三章。例1：我们首先假设B是从A通过去掉A的一个关系而得到的。设I是从J得到的关系结构，它是通过用一个空关系补充J的关系而得到的，该空关系对应于从A中去掉的关系。我们设w I=w J和f I=f J。然后，我们定义fJ=fI。 很明显，f J是J到B的同态。因 此 ，dist（f I，f I）= dist（f J，f J）≥ 0成立。情形2：假设B是由A加上由关系式S得到的关系式S而得到的R通过根据置换π置换变量。让我成为关系结构通过删除SJ和通过RI=RJ SJ从J中删除，而S J通过将 S J a cc 或 d i n g 的 v a r i a b l e s permutingtevariables p erdingtoπ−1 。 我们有wI=wJ和fI=fJ。 因此，我们定义了f J= f I。 很明显，f J是J到B的同态。因此，dist（f I，f I）=dist（f J，f J）≥ 0成立。11˜˜1212˜˜Σ^→一Maj^ ^您的位置：JJJJw（u）JJΣb∈BJ因此，我们假设dist（fJ，f^J）=u：θ-块v∈u：fI（u）fJ（v）例3：设R和S是A的相同元的两个关系。 设T表示R和S的交集。假设B是由A加上关系T而得。设I是由TJ和RJ通过RI=R J T J和S J通过SI=SJTJ来表示的R J的关系式。 我们有wI=wJ和fI=fJ。 因此，我们定义了fJ=fI。 证明了如果J是J到B的同态. 因 此 ，dist（f I，f I）=dist（f J，f<$J）≥ 0成立。例4：设R和S是A的两个关系。设T表示R和S的乘积，设B由A加上关系T得到。设I是从J得到的关系结构，通过RI=RJT J和SI=SJTJ来定义TJ和重新定义R J，其中TJ（重新定义）。，TJ）是TJ在R部分变量上的投影（分别为，S-部分）。我们设wI= wJ和f I=f J。然后，我们定义fJ= fI。 很明显，f J是J到B的同态。因此，dist（fI，fI）=dist（fJ，f<$J）≥dholds。例5：假设B是由A加上等式关系得到的。 设θ是θ′的自反、对称、传递闭包，其中θ′是J对应于B中等式的关系。显然，θ是J上的一个等价关系。对于变量v∈J，我们定义v/θ作为相应的θ块。 对于θ-块u，我们定义wJ（u，b）=wJ（v）， wJ（u）=v∈u：fJ（v）=bf_w_J（u，b），w_maj（u）= max_w_J（u，b），f_maj（u）= argmax_w_J（u，b）。b∈Bb∈B在我们将问题简化为HOM（）之前，我们首先运行以下算法：Θ（1/θ）可以变化或减小，以使其保持不变，其中，所述值可以由θ来变化。LetfJ：J Bbethe映射使得fJ（v）=fJ（v/θ）。注意，fJ是最接近fJ的映射，它服从θ。很容易看出，当fJ是从J到B的同态并且查询时间复杂度为O（1/n）。当t（f J，f ^J）≥ 0/ 2 0 时，则p ∈ H（fJ，f^J）≥0/20. 这是一个很好的选择，u：θ-区组（wJ（u）−wmaj（u））≥n/20. Itisnot必须说明的是，在这种情况下，所有受影响的部分都将占到2/3。u：θ-区组（wJ（u）-wmaj（u））

下载后可阅读完整内容，剩余1页未读，立即下载