1≥两两独立的近似抵抗预测Per Austrin第k皇家技术研究所Sto kholm，瑞典哈南·莫塞尔U.C. 伯克利美国2007年6月Abstra t本文研究了域[q]中k个变量的预测的可逼近性，给出了唯一对策猜想下预测抗逼近的一个新的充分条件.特别是此外，我们证明了一个预测P是近似抵抗的，如果存在一个在[q]k上的两两独立分布，其支持度为包含在对P的满足赋值的集合中。使用成对独立分布的构造，该结果意味着，• 对于一般k ≥ 3和q ≥ 2，Max k-CSPq问题在q<$log2k+1<$−k+1内是UG-难以近似的。• 对于k≥3和q次方，硬度比提高到kq（q − 1）/qk+ k。• 对于q= 2的特殊情况，即，对于布尔变量，我们可以将此绑定锐化为（k+O（k0. 525））/2k+，在最佳预处理基础上进行改进，2k/2k+k（Samorodnitsky和Trevisan，STOC'06）的明显界限基本上是因子2。• 最后，对于q= 2，假设著名的阿达玛定理为真，可以进一步改进，并且O（k0. 525）任期可以由4号代表回答。1产品介绍在Maxk-CSP问题中，我们给出了一组约束，约束是一个布尔函数，它最多作用在k个布尔变量上。目标是给变量赋值，使其满足尽可能多的约束。该问题对于任意k ~2都是NP-难的，因此，人们对该问题的逼近程度进行了大量的研究。我们说一个（随机化）算法电子邮件：austrin kth.se。研究由瑞典研究理事会资助，项目编号50394001。电子邮件：mossel stat.berkeley.edu.美国国家科学基金会资助职业奖DMS 0548249和DOD ONR授予N 0014 -07-1-05-06arXiv：0802.2300v1 [cs.CC] 2008年2月2··−⊕⊕近似比α，如果对于所有情况，算法保证找到一个分配，该分配（在实验中）至少满足α Opt的约束，其中Opt是在任何分配上同时满足的约束的最大数量。一个特别简单的近似算法是简单地对变量进行随机分配的算法。 该算法具有1/2k的比率。Trevisan[22]首次提出了一种求解Maxk-CSP的2 /2k比 算 法 。最近， Hast [8]给出了一个比率为k/ （logk 2k）的算法，Charikar等人对该算法进行了改进。[5]他给出了一个近似比为ck/2k 的 算法，其中c>0. 44是绝对的。PCP定理意味着Maxk-CSP问题是NP-难的，对于常数c >1，近似在1/ck以内。Samorodnitsky和Tre-visan[20]将该硬度提高到2.2μk/2k，Engebretsen和Holmerin[7]将其进一步提高到2.2 μ k /2k。最后，萨莫尔·奥·德尼茨基和T·雷维桑[21]假设，如果唯一博弈猜想[12]为真，则最大k-CSP问题很难在2k/2k范围内进行近似。结果表明，它们的硬度为2×10g2k+1μg/2k，当k=2r1时，硬度为（k+1）/2k，而当k = 2r1时，硬度为（k + 1）/ 2k对于一般k，Be大到2k/2k。 因此，硬度和近似可接受性之间的当前差距是2/0的小的初始因子。44个。对于预测P：{0，1}k→ {0，1}，最大CSP（P）问题是本 文 讨 论 了 一 类Maxk-CSP 的 特 殊 情 况 ， 其 中 所 有 约 束 都 是 P（l1，. . . ，lk），其中eahliteralli是变量或被求反的变量。 对于这个问题，随机分配算法具有m/2k的比率，其中m是P的满意分配的数量。令人惊讶的是，对于某些情况，这是最好的算法。结果，H？Stad[10]指出，对于P（x1，x2，x3）=x1，X2x3时，最大CSP（P）问题很难在1/2+λ内近似.预测P，这是很难近似的最大CSP（P）问题比随机分配更好，被称为近似抵抗。一个稍微强一点的概念是遗传近似抵抗，如果P所隐含的所有预测都是近似抵抗的，则预测P是遗传近似抵抗的一个自然而重要的问题是了解近似电阻的结构。对于k =2和k = 3，这个问题得到解决，2个变量的预测永远不会是近似抵抗的，并且3个变量的预测是近似抵抗的，当且仅当它是由三个变量的XOR暗示的[10，23]。 对于k = 4，Hast[9]成 功 地 将大多数预测值分类为近似阻力，但对于这种情况，似乎不像k = 3的情况那样存在不合理性。事实证明，假设唯一博弈，大多数预测是在fat遗传近似抵抗随着k的增加，表面的比例趋于1 [11]。 因此，与其试图理解看似复杂结构的近似抵抗预测，人们可能会尝试理解遗传近似抗性prediates的可能更容易的结构，因为这些prediates占所有prediates的绝大多数。对于Maxk-CSP问题，获得强不可逼近性的一个自然方法是寻找具有很少输入的近似抵抗预测这确实是所有提到的最大k-CSP的硬度结果的由来（除了PCP定理所暗示的那个）。将Maxk-CSP问题推广到3∈联系我们||·大小为q的域，而不仅仅是布尔变量。在不损失一般性的情况下，我们可以假设域是[q]。我们都知道这个问题. 对于Maxk-CSPq，随机分配给出1/qk-近似，f（ k）-近似算法的最大k-CSP问题给出了一个f（ klog2 q）-最 大 k-CSP q 问 题 的 近 似 算 法 。 因 此 ， Charikar et al. 的 算 法 给 出 0.44kl0g2q/qk-近似，其中q是二、 最大k -CSP q的最佳前不可逼近性 这个问题是由于Engebretsen [6]提出的，他证明了这个问题是NP难近似的在qO（k）/qk内。与q= 2类似，我们最大CSP（P）问题P：[ q]k→{0，1}。在这里，有几种自然的方式来概括文字的概念。一个可能的定义是说文字l是π（ xi）的形式，对于某个变量xi和置换π：[ q]→[ q]。一个更严格的定义是说一个字面量是xi+a的形式，其中，同样，xi是一个变量，a[ q]是一些等等。在本文中，我们使用了第二个严格的定义。 由于这是第一个定义的特例，我们的硬度结果也适用于第一个定义。1.1我们的贡献我们的主要成果如下：定理1.1. 设P：[q]k0，1是[q]上的k元预测，设μ是[q]k上的分布，满足PRx∈（[ q]k，μ）[P（x）]= 1对于所有1≤i/=j≤k和所有a，b∈[q]，PRx∈（[ q]k，μ）[xi=a，xj=b]=1/q2。然后，对于任何n>0，UGC意味着最大CSP（P）问题是NP-难以近似的。P−1（1）qk+k，也就是说， P是遗传近似抗性。利用两两独立分布的构造，我们得到下列推论：定理1.2. 对于任意k≥3，q≥2，且q>0，在内近似Maxk-CSPq问题是UG困难的。qlog2k +1qk+m< klog2q Qqk+1。在k= 2r−1的特殊情况下，对于某些r，硬度比提高到klog2qqk+1。4- -≥O−QKQK2K2K这已经对Engebretsen的qO （k）/qk-硬度有了显著的改进，并且在q是素数幂的情况下，我 们 可以进一步改进它.定理1.3. 对于任意k≥3，q=pe，p为素数，且p>0，在一定的条件下，k（q−1）q+k。QK在k=（qr1）/（q1）的特殊情况下，对于某个r，k（q−1）+ 1 +k≤kq+ k。对于q = 2的情形，这两个定理都不改进[21]的结果.然而，下面的定理是这样的。定理1.4. 对于任何k3和k>0，在k+（k0. （第525条）2k+1。如果阿达玛定理成立，则近似最大值k-CSP问题4<$（k+1）/4<$+<$≤k+4+<$因此， 我 们 将 [2 1]的 难 度 提 高 到 基 本 上为2，将最佳算法的差距从大约2/0减小到最佳算法。44到大约1/0。44个。1.2相关工作有趣的是，我们的结果与Samordnitsky和Tre-visan[2 1]的 结果 是一 致 的 . 利用Gowers范数，[21]证明了Maxk-CSP问题的硬度因子为2×log2k+1×log2k/2k，当k=2r时，硬度因子为（k+1）/2k1，但对于一般k，b e可达2k/2k。我们的证明使用了相同版本的UGC，但分析更直接，更一般。[21]的方法要求我们对长节点进行线性超图检验。对于这个检验，成功概率与长节点的Gowers内积密切相关。特别地，在可靠性分析中表明，如果该检验的值太大，则Gowers范数大于随机函数。由此可以看出，至少有两个函数有很大的意义，这反过来又使我们能够为UGC获得一个很好的解决方案。另一方面，我们的构造允许任何成对分布来定义长期检验。 使用[16]，我们表明，如果一组支持的长节点对于该长节点测试比随机的好，则其中至少两个具有较大的优势。我们的证明有许多优点：首先，它适用于任何两两独立分布。这应该是对要求我们工作的[21]要求的补充5O≤≤近似因子 如果（t，k）-UGC对于sm为真。et≥3时，≤≤特别是与超图线性测试。特别地，我们的结果使我们能够获得针对宽范围的P的最大CSP（P）的硬度结果。这些结果对于任何区域[ q ]都是一般的（如果[21]的结果推广到更大的区域就不清楚了），而且即使在q = 2的情况下，对于大多数k值，我们也能得到较好的硬度因子。同时，我们的证明使用了某些类型下相关性，将其置于与许多其他基于UGC的硬度结果相同的一般框架中，特别是2-CSP的硬度结果[13，14，2，3，18]。最后，我们的证明给出了以下意义上的参数化硬度。我们给出了一系列的硬度假设，称为（t，k）-UGC。所有这些假设都是从UGC得出的，特别是已知t= 2的假设等同于UGC。然而，对于较大的t值，（t，k）-UGC假设较弱。对于t的每个h值，我们的结果意味着不同的硬度，Maxk-CSP问题是NP-难的，在Okt/2−1/2k.因此，即使（4，k）-UGC的硬度为（k/2k），对于tk/logk，（t，k）-UGC给出的硬度比已知的最好的非线性结果更好[7]。2定义2.1独特的游戏我们使用以下公式的唯一标签覆盖问题：给定是一个k-一致超图，其中对于每个h边（v1，.. . ，vk）存在k个置换π1，.. . ，πk在[L]上。我们说一个边（v1，.. . ，vk），其中置换为π1，.. . ，πk满足标号V→[ L]，若有i1i2.. . < I t证明了πi1（ π（ vi1））= πi2（ π（ vi2））=. . . =πit（π（ vit））。我们说边缘是如果它是k-方向满意的，则被标记完全满意我们用Optt（X）∈[0，1]表示任意标号上t-满足边的最大分数。注意，Optt+1（X）Optt（X）。下面的onje真实是已知的遵循从独特的游戏Conje-真实（详见下文）。Conje ture 2.1. 对任意2tk，δ >0，存在L >0的suh区分具有标签集[ L ]的k元唯一标签覆盖实例X是NP困难的，其中Optk（X）≥1−δ，并且Opt tt（X）≤ δ。对于t和k的特殊值，我们将参考相应的特殊值。上述情况之一 onje ture作为（t，k）-唯一的游戏Conje ture（或（t，k）-UGC）。Khot对唯一对策Conjeture[1 2]的原始计算是（2，2）-UGC，并且Khot和Regev[1 5]提出，对于所有k，该唯一对策Conjeture等价于（2，k）-UGC，这是Samorodnitsky和Trevisan[2 1]用来获得Maxk-CSP的硬度的。在本文中，我们主要使用（3，k）-UGC来获得我们的硬度结果。显然，sin eOptt+1（ X）Optt（ X），（t，k）-UGC意味着（t+1，k）-UGC，因此我们的假设被唯一博弈猜想所暗示。但是，无论逆宇宙是否成立，或者是否有希望证明这一点（或者说，6我我我→⊆≤i ≤k−这是众所周知的（见例如。[13]th在每个函数f：[q]n→R上允许一个唯一的对于大k）的（k，k）-UGC没有证明唯一的博弈猜想，是不可能的，应该是未来研究的一个有趣的方向。2.2在uen esEfron-Stein de omposition：f=S[n]fS其中• 函数fS仅依赖于xS=（xi：i∈ S）。′• 对于每一个S′/εS，且每一个S′∈[q]S，对于m≤ n，我们写f≤m=E[fS（xS）]|xS′=yS′]=0.Σ史：|S|对于f的m次展开，≤ m f S。我们现在定义f上第 i坐标的单位，记为Infi（f），Infi（f）=E[Var[f（x）]]。（一）x xi定义了f上第i个坐标在uen e中的m次，记为Inf≤m（f）.i（f≤m）。所有这一切都是因为在uen e Infi（f）中度量了函数f对第i个变量的依赖程度，而在uen es Inf≤m（f）中的低次度量了f的展开式的低部分。后者的数量是losely有关的在轻微的噪声输入f 的 输 入 。uen es中低度的一个重要性质是，卢恩i=1Inf≤m（f）≤mVar[f]，这意味着在uen e中具有大的低次的坐标的数目一定是小的。特别地，如果f：[q]n[0，1]，则uen e中至少为τ的低次o坐标的个数至多为τ/m。2.3相关概率分析我们将对P−1（1）[ q]k中支持的概率分布感兴趣。遵循[16]的方法，把[q]k看作是k或与k坐标相对应的相关空间的一个集合。 我们讨论了两个或两个相关空间的正式定义定义2.2. 设（ε，μ）为a上的概率空间，夜间生产= 的1、2、3、4、5、6、7、8、9、10、11、 12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、2ρ（μ1，μ2;μ）=sup{Cov[f1（x1）f2（x2）]：fi：μi→R，Var[fi（xi）]=1}，其中（x1，x2）是从（μ，μ）中得出的。定义2.3. 设（ε，μ）为a上的概率空间，夜间生产QKi=1i，令S =（1）Qi∈Si。的相关性。. . ，k（与ρ（ρ1，. . . ，k; μ）=1 max1 ρ（{1，.，i}，n{i+1，.，k}; µ）7≥我J.∈.我们特别感兴趣的是这样一种情况，即相关的空间是由一个独立的度量来定义的。定义2.4. 设（μ，μ）为乘积空间上的概率空间，QKi=1i。 我们说μ是t-独立的，如果对于任何hoi e of i1 i2<. . . 0。（）ρ（ε 1，. . . <1.则对于所有的τ>0，存在τ >0和d >0，因此以下成立。 设f1，. . .，f k是函数fi：n→[0，1]，满足对所有的1≤j≤ n，|≤t。| ≤ t.然后... EΣ ΣYkYkfi（ w1，i，.. . ，wn，i）−..E[fi（w1，i，. . . ，wn，i）]。≤100，.w1，.. .，wni=1i=1 w1，.，wn.其中W1，. . . ，w n独立于（μ，μ）而画，wi，j∈ μj表示wi的第j个坐标。注意，（）在上述定理中成立的一个条件是，对所有的w∈，μ（ w）>0。粗略地说，该定理及其证明背后的基本思想是，低次函数并不能确定高阶函数的依赖性，如果基本度量是成对独立的，则不同坐标的所有函数基本上都是独立的。8联系我们- -≥−V≥− −w∈|P−1（1）|Kk′3主要定理在这一节中，我们证明了我们的主要定理。注意，它是定理1.1的推广。定理3.1. 设P：[q]k0，1是大小为q的整环上的k元预测，设μ是[q]k上的t-独立分布，满足Prx∈（[q]k，μ）[P（x）]> 0. 然后，对于任何k> 0，（t+1，k）-UGC意味着最大CSP（P）问题是NP-难近似的 ，公司简介qk·Prx∈（[q]k，μ）[ P（ x）]特别地，注意，如果Prx∈（[q]k，μ）[P（x）]=1，即， 如果μ的支持完全包含在P的满足赋值集合中，则P是抗逼近的. 它也是遗传近似抵抗的，因为当我们向P添加更令人满意的分配时， P−1（1）还原。 给定一个k元唯一标号覆盖实例X，证明器写出函数fv的表：[q]L→[q]，其中每个hv都被用作顶点v的标号的长码。此外，我们将假设fv 是 折 叠 的 ， 即 ， 对 于 每 个 x ∈ [q] 和 a ∈ [q] ， 我 们 有 f v （ x+（a，. . . ，a））=fv（x）+a（其中只要（[q]，+）是阿贝尔群，+在[ q ]中的定义是任意的）. 当 读取f v（x 1，. . . ，XL），验证者通过查询fv（x 1-x 1，x 2-x 1，. . . ，x L− x 1），并将x 1加到结果上。设η >0为参数，h的值将在后面确定，并通过下式定义[ q ] k上的概率分布μ ′：μ′（ w）=（1− η）· μ（ w）+ η· μU（ w），其中μU是[q]k上的均匀分布，即， µU（w）=1/qk。Givenaproof=f vv ∈ V的假设长赞美一个很好的标签的X，验证者他说：算法1：验证者VV（X，X ={fv}v∈V）(1)Pi k是随机边e=（ v1，. . .，vk）的置换π1，.. . ，πk.（二） 对于ea h i∈[ L]，从（[q]，μ）随机抽取wi。（3）F或eahj∈[k]，设xj=w1，j. . . wL，j，令bj=fvj πj（ xj）.(4)Aept如果P（b1，.. . ，bk）。引理3.2（完备性）。对于任何δ，如果Optk（X）1δ，则有一个证明，PR[ （X，X）a epts]（1δ）（1η） Pr（[q]k，µ）[P（w）]9→≥−- -||≥QK我|P−1（1）|证据对X取一个标号，使得边的一部分1δ是k-方向满足的，设fv：[q]L[q]e是顶点v的标号（v）的长边。设（v1，. . .，vk）是k-方向满足的边。 则fv1π1=fv2 π2=.. . =fvkπk，eahi是i的长模：=π1（ π（v1））.那么Va成立的概率就是P（ wi）为真的概率，而sin e wi从（[q]k，μ）中以概率1 η得出，至少（1 η）Prw∈（[q]k，μ）[P（w）]。验证者在第一步中选择的边e满足的概率最小为1−δ，所以我们最终得到了想要的不等式。引理3.3（合理性）。 对于任意的ε>0，η >0，存在一个常数δ：=δ（ n，η，t，k，q）>0，所以如果Optt+1（ X） δ，则对任意证明n，我们有证据假设Pr[V（X，X）aepts]≤Pr[V（X，X）aepts]>qk+mP−1（1）qk+1。（二）我们需要证明，这意味着存在δ：= δ（ θ，η，t，k，q）>0，使得Optt+1（X）δ。等式2意味着，对于边缘e的至少1/2的部分，−1当hosing e至少为时，V（X，λ）a成立的概率|P（1）|+0.02/2。设e=（ v1，.. . ，vk），其中置换为π1，.. . ，πk是一个很好的边。为v∈V，a∈[q]，设v，a：[q]L→{0，1}by.gv，a（ x）=1如果fv（x）=a0否则，请执行以下操作 。当h为e时，Va成立的概率是ΣkEgπ（wΣ，的。. . ，w），x∈ P−1（1）w1，.，WLi=1vi，xii月1L我其中h，通过e的hoi e，大于|P−1（1）|/qk+k/2。这意味着存在某个x∈ P−1（1） suh，ΣΣYkgv，x πi（ w1，i，.. .（i）>1/qk+1′w1，.，WL我我i=1Yk=i=1Ew1，.，WL[g vi，xiπi（w1，i，. . . ，wL，i）]+n′，其中，′=/2/|P−1（1）|最后一个等式y使用了这个等式，因为fv是折叠的而μ则为零，w e h eeEw1，. . ，wL[gvi，xi（w1，i，. . . ，wL，i）]=1/q.注意，由于μ和μU都是t方向独立的，所以μ′也是t方向独立的。10∈≥因德彭特另外，我们有一个，[q]k，μ′（w）η/qk>0，这意味着定理2.5的条件（b）和（）。然后，定理2.5的反正式表示意味着存在i∈[ L]且至少t+ 1114s||∈≤ ≥−≥− −≥−≤≥OO{}O≥−1π j（一J J我J J为了证明其完备性，我们在附录中给出了一个证明。 特别地，引理A.1设J∈[k]，使得对任意j∈J，Inf≤d（gv，x）= Inf≤d（gv，xπj）≥其中τ和d是τ，η，t，k和q的函数。从这一点开始构造X的良好标记的过程是标准的。给出了Optt+1（X）≥<$/2需要的话.τd·q最大值+1，其中h是n，η，t，k和q的函数，如现在我们可以直接证明定理3.1。第三个问题。1 .一、 设c=Prx（[q]k，μ）[P（x）]，s=P−1（1）/qk，η=min（1/4，μc）. 注意，在定理的状态中，要求c>0我们也有s >0和η >0。 假设（t + 1，k）-UGC为真，并且pik L足够大，使得区分具有Opt +1（X）δ和Optk（X）1 δ的k元唯一标签覆盖实例X是NP困难的，其中δ=min（η，δ（k/4，η，t，k，q）），其中δ（. . . ）是引理3的函数。3 .第三章。通过通过引理3.2和3.3，我们得到了区分最大CSP（P）实例（Opt（1δ）（1η）c（1 2η）c和Opt（1 δ）（1 η）c）是NP-困难的s+10c/4。 在其它情况下，最大CSP（P）的近似是NP-难的因素内问题s+1/4c /4（1−2η）c≤s（1 + 4η）c+（1+4η）η/4≤s/c+η4作为定理3.1的简单推论，我们有：推论4.1。 设t 2和μ是[ q ] k上的离散t-独立分布。 那么（t +1，k）-UGC意味着Maxk-CSPq问题是NP-难的，|补充（µ）|QK这样，我们就把求Maxk-CSPq的强不可逼近性问题简化为求小的t-独立分布的问题。由于我们主要对用这种方法得到的最强可能结果感兴趣，我们的主要关注点将是两两独立的e，即t= 2。然而，让我们首先提到t的一般值的两个简单的推论。当q= 2时，二进制BCH码给出了0，1k上的t-独立分布，其支持大小为（kt/2）[1。换句话说，（t+ 1，k）-UGC意味着Maxk-CSP问题是NP-难的，在（kt/2/2k）。特别注意，（4，k）-UGC可以得到硬度为（k/2k），其最大可达一个初始因子。对于q是一个素数幂，并且足够大，使得q k，有t-wise独立分布在[q]k上，支持大小为qt，基于评估Fq上的随机次数t多项式。因此，在这种情况下，（t + 1，k）-UGC意味着对于Max k-CSP q问题，硬度因子为q t −k。12- ∈∈∈⟨ ⟩ ⟨ ⟩ ∈| |QQQ−−卢恩对于任何Si= T，向量uS和uT满足引理4.2的条件，并且R在本节的剩余部分中，我们将着重讨论两两独立e的构造细节，给出在（3，k）- UGC下Maxk-CSPq的硬度。4.1定理1.2和1.3用于给出定理1.2和1.3的两两独立分布都基于下面的简单引理，这是众所周知的，但在这里以比通常稍微更一般的形式陈述引理4.2. 设R是有限交换环，u，vRn是R上的两个向量，且uivjujvi为一些i，j。1LetXRn是Rn上的一致随机向量，设μ是（u，X，v，X）R2在R2上的概率分布.其中，μ是一个独立的两两分布。证据不失一般性，假设i= 1且j= 2。证明了对所有的（a，b）∈R2和X3的任意值，.. . ，Xn，我们有Pr[（u，X，v，X）=（a，b）|X3，. . . ，Xn]=1/|R|二、要做到这一点，我们需要系统.u1 X1+u2 X2 = a′v1 X1+v2 X2 = b′有唯一解，其中a ′= a −i =3u i X i，b ′也是如此。这反过来，从u和v的条件中直接因此，给定Rn中的一组向量，若其中任意一对向量满足引理4.2的条件，我们构造了Rm上的一个两两独立的分布，其支持度为Rn.现在我们来证明定理1.2。定理1.2的证明 设r= log2k+1。 对非空S ∈ Z [r]，设u S ∈ Z r是S的原住民，即， u S，如果i ∈ S，则i= 1，否则为0。然后，因此，我们有，对于一致随机的X∈Zr，（<$uS，X<$）S<$[ r]导致Z2−1上的两两独立分布，支持度为qr。当k= 2r1时，我们得到的硬度为qlog2（k）−k，但对于一般值，k，特别是k= 2r−1，我们可能会损失一个因子q。我们注意到，当q= 2时，这个结构精确地给出了Samorodnitsky和Trevisan[21]所用的预测，对所有k给出了不适当的2k/2k，对所有形式为2l的k给出了（k+1）/2k1.一、直观地说，当我们在引理4.2中有更多的R上的结构时，我们应该能够找到更大的向量组，其中每对都满足独立条件。 这种直觉将我们引向定理1.3，它处理定理1.2的特殊情况，其中h q是一个素数幂。定理1.3的结构与文[17]基本相同。1R表示R的单位集。 在R是一个域的情况下，条件是等价的 u和v是线性无关的。13QQ∈QQ≥- -- − −||−−∈∼≥≡×≥≥×±≥×||⌈ ⌉ ≤× {−} →−设P（Fr）是Fr上的主空间，即， P（Fr）=（Fr|0）/π。在这里，×QQQQ第1项的P roof。3 .第三章。 设r=<$logq（k（q−1）+1）<$，n=（qr−1）/（q−1）≥k.是由（x1，. . .、x r）（y 1，. . .，y r）如果存在一个cFq∈ h，对于所有i，xi=cyi，即， 如果（x1 ，. . . ， xr ）和（y1，. . . ，yr）是线性相关的。则We具有P（Fr）=（qr1）/（q1）=n.选择n个向量u1，. . .，unFr作为P（Fr）的等价类的代表。则任意对ui，uj满足引理4.2的条件，如定理1.2所示，我们得到Fn上的一个两两独立分布，其支持度为qr。当k=（qr1）/（q1），这给出了硬度k（q1）+1，对于一般k，特别是k=（qr−11）/（q1）+1时，硬度比中损失了一个因子q。同样，对于q = 2，该构造给出了由Samorod-nitsky和Trevisan使用的相同的预测。在这种情况下，qk，我们得到的硬度为q2/qk，与我们从本节开始时提到的t方向独立的一般构造中得到的因子相同。4.2定理1.4现在让我们看看布尔变量的特殊情况，即，q= 2.到目前为止，我们只给出了Samorodnitsky和Trevisan结果的不同证明，但现在我们将展示如何改进这一结果。Hadamard矩阵是1上的n n矩阵，使得HHT=nI，即，每对行和每对列是正交的。设h（ n）表示存在n′n′ Hadamard矩阵的最小n′n众所周知，Hadamard矩阵给出了小的两两独立分布，从而给出了逼近Maxk-CSP的困难。具体来说，我们有以下主张：4.3号提案对于每一个k3，（3，k）-UGC意味着在h（k+1）/2k+1内应用肟酸的Maxk-CSP问题是UG-ha r d.证据设n = h（k + 1），A是一个n阶Hadamard矩阵，归一化后使一列只包含1.去掉n k列，包括全一列，设A′为结果n k矩阵。设μ：1，1 k[0，1]是将概率1/n分配给A ′的每一行的概率分布。则μ是一个两两独立分布，Supp（μ）= h（ k+ 1）。众所周知，Hadamard矩阵只存在于n= 1，n= 2和n0（mod 4）时.著名的Hadamard Conje ture断言，Hadamard矩阵存在于所有h可被4整除的n，换句话说，h（n）=4n/4n+3。也有可能得到关于h（n）的有用的无约束条件。我们现在给你一个简单的约束。定理4.4（[19]）. 或每一个奇素数p和整数e，0，则re存在nnHadamard矩阵Hn，其中ren=2e（p f+1），只要这个数ber能被4整除。定理4.5（[4]）. 存在一个整数n0，使得对于每一个n n0，在n和n+n0之间存在一个素数p。525.14√--−≡⌊⌋- -推论4.6。 我们有：h（n）≤n+ O（n0. 525）。P roof. 设p是大于n/2的最小素数，n′=2（p +1）≥n.然后，定理4.4断言存在n′× n′ Hadamard矩阵，因此h（ n）≤ n′. 如果n足够大（n≥2n0），则根据定理4.5，p≤n/2+（n/2）0。525和n′≤n+2n0. 525，如你所愿。定理1.4由命题4.3和推论4.6得出。利用比定理4.4更强的构造技巧，有可能得到比推论4.6更强的h（第五章我们给出了在唯一对策假设（的一个弱化版本）下预测是遗传抗逼近的一个强条件：满足的分配集包含一个离散的两两独立分布.通过构造小面分布，我们可以构造出具有抗逼近能力的预测，从而提高了Maxk-CSPq问题的难度.这里有几个方面，有进一步有趣的空间工作：如前所述，我们不知道（t，k）-UGC是否意味着标准UGC用于大的t值。 特别地，证明对于某些tk/logk的（t，k）-UGC<将使Maxk-CSP的硬度优于最佳CSP。当前NP-硬度结果。但即使理解（k，k）-UGC似乎也是一个有趣的问题。一个非常自然和有趣的问题是，我们的条件是否也是必要的-对于具有遗传近似抗性的预测是必要的，即，如果两两独立给出了遗传逼近剩余的完全证明.最后，很自然地要问，我们对Maxk-CSP q的结果是否可以推得更远一些，或者它们是否是紧的。 对于布尔变量的情况，Hast[9]证明了一个至多2k/2+1个输入的预测 不是近似抵抗的。对于k 2，3（mod 4），这与我们在UGC和Hadamard猜想下得到的结果完全吻合（其中k = 2r1和k= 2r2的硬度与[21]相同）。对于k0，1（mod 4），我们得到满足近似抵抗预测的分配数量之间的差距为2一个和一个没有。因此，迄今为止非常成功的方法是通过确定小的近似阻力预测值来获得Max k-CSP的硬度，不能进一步采用，但仍然存在大约1 / 0的小的初始差距。44到最佳当前算法。这将是有趣的，知道该算法是否可以改进，或者是否最大k-CSP的最困难的instan es不是最大CSP（P）instan es的一些近似阻力P。对于较大的q，这种情况变得更糟。当q = 2l和k =（qr1）/（q1），最佳算法与最佳不可逼近性之间存在着Θ（q /10 g2 q）的差距，对于一般的q和k值，差距甚至更大。15−雷费伦[1]诺加阿隆，L？szl？Babai和Alon Itai。最大独立集问题的一个快速简单的随机并行算法。Journal of Algorithms，7（4）：567 583，1986.[2] Per Austrin.平衡最大2-周六可能不是最难的。ACMSymposium onTheory of Computing（STOC），第189 - 197页，2007年。[3] Per Austrin.对任何2-CSP的尖锐不可逼近性。在IEEE Symposium onFoundations of Computer Sien e（FOCS），第307 - 317页，2007年。[4] C. Baker，G.Harman和J.平茨第二章因果素数之间的差异伦敦数学院学报，83（3）：532562，2001.[5] Moses Charikar ， Konstantin Makary hev ， and Yury Makary hev.Approximation Algorithm for the Max k-CSP Problem，2006.[6]Lars Engebretsen.的 的不可逼近性 非布尔预测。SIAM Journal on Disrete Mathematics，18（1）：114 129，2004.[7]Lars Engebretsen和Jonas Holmerin。NP问题的更有效的逼近和最大逼近难度的改进。 在Symposium on Theoreti al Aspe ts of ComputerSien e（STACS），第194 - 205页，2005年。[8] Gustav Hast.近似最大kCSP优于几乎线性因子的随机分配。见ICALP2005，第956 - 968页，2005年。[9]古斯塔夫·哈斯特。随机指派近似约束满足问题的求解。博士论文，KTH皇家技术研究所，2005年。[10约翰·H？斯塔德一些最优不可逼近性结果。Journal of the ACM，48（4）：798 859，2001.[11约翰·H？斯塔德关于随机预测的抗逼近性。出现在随机近似，2007年。[12苏巴什·霍特关于独特的2-prover 1轮游戏的力量。STOC2002，第767 - 775页，2002年。[13 Subhash Khot，Guy Kindler，El hanan Mossel，and Ryan O'Donnell.最大-ut和其他2变量sp的最优不逼近性结果？Siam Journal on Computing，37：319 357，2007。[14 Subhash Khot和Ryan O'Donnell。MaxCUTGAIN的SDP间隙和UGC硬度。见FOCS 2006，第217 - 226页，2006年。[15] Subhash Khot和Oded Regev。顶点覆盖可能很难近似到2μ m以内。在IEEE Conferen e on Computational Complexity，第379页，2003年。16→我→∈J−1π j（一|| ≤ ·J JC（vj），并且由此，πj（π（vj））=i的概率y为1/|C（vQj）|. 这意味[16我是哈南·莫塞尔。噪声与函数关系的高斯界。arXiv报告数学/0703683v3，2007年。[17我的天L.奥布莱恩两两独立随机变量Annals of Prob- ability，8（1）：170175，1980.[18 Ryan O'Donnell和Yi Wu。最大切割的最佳SDP算法，以及同样最佳的长码测试。 Manus ript，2007年。[19 Raymond E. A. C.佩利关于正交矩阵。数学与物理学报，12：311 -320，1933年。[20 Alex Samorodnitsky和Lu a Trevisan。 NP的PCP实现，具有最优的分摊查询复杂度。 在STOC，第191 - 199页，2000中。[21 Alex Samorodnitsky和Lu a Trevisan。Gowers均匀性，变量和PCP的使用。 在STOC 2006，第11 - 20页，2006年。[22把路交给特雷维桑。正线性规划的并行逼近算法。 1998年，第21卷，第72页，第88页[23 Jiangyu Zwi k.每个约束最多包含三个变量的在SODA 1998，1998中。A从基本变量中引理A.1. 设X是k元唯一的标签封面.此外，对于每个h顶点v，设f v：[q]k[q]，且.gv，a（ x）=1如果fvi=a0否则，请执行以下操作。然后，如果存在至少n个边的分数e=（v1，. . .，v k）的向量a ∈ [q]k，一个指数i
我的内容管理
展开
