通信与计算权衡的研究：布尔函数在不同计算模型中的表现

1沟通与计算PrahladhHarshaYuvalIshai <$JoeKilianKobbiNissim §S. Venkatesh¶2004年4月25摘要我们发起了一项研究，在著名的通信模型和其他相关模型的通信和计算之间的权衡。我们调查的基本问题是：是否有一个计算任务，表现出很强的权衡行为之间的通信量和本地计算所需的时间量在各种标准假设下，我们展示了布尔函数，在以下计算模型中表现出很强的权衡：（1）两方随机通信复杂度;(2)查询复杂度;（3）属性测试。对于确定性的通信复杂性模型，我们显示了一个类似的结果相对于一个随机预言。最后，我们研究了布尔函数算术化中出现的时间-度权衡问题，并将其与多方通信复杂性和密码学中的时间-通信权衡问题计算机科学和人工智能实验室，麻省理工学院，剑桥，MA 02139，美国，电子邮件：prahladh@mit.edu。作者在NEC美国实验室工作时所做的研究。†以色列理工学院计算机科学系，海法32000，以色列，电子邮件：yuvali@cs.technion.ac.il。NEC Laboratories America Inc，Princeton，NJ 08540，USA，电子邮件：joe@nec-labs.com。§Microsoft Research，SVC. 1065 La Avenida，Mountain View，CA 94043，USA，电子邮件：kobbi@microsoft.com。作者在NEC美国实验室工作时所做的研究计算机科学系，维多利亚大学，维多利亚，BC，加拿大V8 W 3 P6，电子邮件：venkat@cs.uvic.ca. 作者在MPI for Informatik（德国）时完成的研究。11介绍一个激励的谜语。考虑下面的多方通信游戏。固定有限域F，设M是F上的n×k矩阵. F的列被分配给k个参与者，每个参与人j都知道M的所有列除了第j列(This被称为玩家YnZurkPS（M）=Mi，j，i=1j =1通过同时向外部裁判发送消息这可以通过将整个矩阵M发送给裁判（例如，让P1发送第二列，P2发送其余列）。 目标是最小化通信复杂性，以发送的最长消息的长度来衡量。在[BGKL 03]中研究了一个密切相关的问题 当k> n（比如k = n +1）时，我们的问题有下面的简单解，隐含在[BGKL 03]中。把PS（M）写为k n项的和，其中每项是涉及M的每一行的单个条目的乘积。由于参与者比行多，因此对于每个这样的项，都有一个参与者持有其所有值。因此，我们可以将每一项分配给某个知道其值的参与者，并让每个参与者发送分配给它的所有项的总和然后，裁判可以通过简单地将其接收到的k个字段元素相加来恢复PS（M）。虽然该协议在通信中非常有效，参与者的组合计算是n的指数。请注意，如果使用自然贪婪策略将每个项分配给第一个可以分配它的参与人，那么参与人n+ 1将需要计算M的n×n子矩阵的持久式，这是一个#P-困难问题。[1]因此，一个自然的问题是：函数PS（M）是否允许这样的协议：（1）每个参与者只发送F的单个元素;（2）每个参与者的局部计算是n中的多项式？鉴于自然术语分配策略的失败，否定的答案似乎是可能的。这也似乎是合理的，对于任何有效的方式分配的kn项的球员，一些球员将被迫计算一个硬函数。因此，这个问题看起来像是一个很好的候选人的时间通信权衡：它需要很少的时间来计算时，没有限制的通信复杂性，需要很少的通信时，没有限制的时间复杂性，但似乎藐视解决方案，同时有效的两个复杂性措施。令人惊讶的是，上述问题的答案是“是”。(The不耐烦的读者可以跳到5.2节来解答这个谜。）因此，这个特殊的问题并没有表现出最初怀疑的时间-通信权衡。然而，这个问题是这项工作的原始动机，它探讨了在相关背景下存在的类似权衡。1.1问题描述设f：X×Y→Z是两个输入的任意函数。在Yao [Yao79]的双方通信模型中，有两个参与者A和B。A被给定x∈X，B被给定y∈Y，它们[1]即使F具有特征2，在这种情况下，永久物可以被有效地计算，但不清楚（比如）中间参与者的计算是否可以被有效地实现。2需要通过相互通信来计算z=f（x，y）。在为f设计的任何通信协议中，有三种有用的复杂性度量：• 通信复杂度：A和B之间交换的比特总数;• 时间复杂度：A和B进行本地计算所需的时间• 轮复杂度：A和B交换的消息数。给定这三个复杂性度量中的任何两个，很自然地会问是否有任务在它们之间表现出权衡。在两方模型中不会出现回合与计算的问题，因为A将其整个输入发送给B的简单协议对于两种度量都是最优2回合复杂度和通信复杂度之间的权衡已经得到了很好的研究（见下文）。在本文中，我们开始研究剩下的问题：证明通信和本地计算之间的权衡具体地说，我们的主要目标是找到函数f，使得：（1）f可以在给定其两个输入的情况下有效地计算，即，在通信上没有限制的情况下;（2）在计算上没有限制的情况下，F具有低通信复杂度的协议;以及（3）不存在用于F的同时具有低通信和有效计算的协议为了在特定的通信模型中给出一个简单的例子，假设A被给予CNF公式g作为输入，B被赋予其变量的赋值x他们需要通过让A向B发送一条消息来决定x是否满足g。此外，假设A是确定性的。在这种情况下，很容易争辩说，除非P=NP，否则不存在同时使用高效计算和最佳通信的协议。实际上，这样的协议将允许通过简单地比较A在这两个输入上发送的消息来有效地判定两个给定公式g1、g2之间的请注意，这种折衷结果非常弱，因为它不排除通信是最佳通信的两倍的时间有效我们的目标是在各种模型中获得更强的权衡结果。1.2相关工作Papadimitriou和Sipser [PS84]首先讨论了在通信轮次和通信复杂性之间进行权衡的问题对于任何固定的k，他们提出了一个布尔函数pk，称为指针追逐问题，它有一个k轮协议，具有O（logn）位的通信。他们指出，如果只允许k-1轮，其通信复杂度至少是线性的换句话说，pk在轮数和通信复杂度之间表现出很强的权衡行为这个猜想在一系列的论文中得到了证明（[PS84，DGS87，NW93]）。在这项工作中没有考虑的其他复杂性措施是空间复杂性和随机性复杂性。Beame等人[BTY94]考虑了空间和通信之间的权衡Canetti和Goldreich [CG 93]研究了随机性和通信之间的权衡。1.3我们的结果我们的第一个结果是一个强大的时间通信权衡的布尔函数在两方随机通信模型。[2]然而，这个问题在密码学环境中确实有意义，因为玩家需要计算他们输入的函数在第5.3节中讨论了这种权衡问题。3CT（n）随机通信模型。假设存在一个UP关系R，使得R所对应的搜索问题不在BPTIME[2 O（T（n））]中。(This（2）在一个O（T（n））有界的攻击者面前，存在一个安全的单向置换。然后，存在具有以下性质的有效可计算布尔函数f R。 如果Alice和Bob在计算上是无界的，那么存在一个O（log n）比特的1轮随机化协议，该协议计算f R。 但是如果Alice和Bob在计算上是有界的，那么任何针对fR的随机化协议，即使是多轮的，也将需要N（T（n））比特的通信。作为推论，我们得到以下强分离结果。设Fc表示函数类f（x，y）∈PTIME，使得f的随机通信复杂度有界于C. 类似地，令Fpoly是函数f（x，y）∈PTIME，使得f（x，y）可计算为具有通信的多项式时间方c.然后有一个显式的布尔函数f在Flogn\F poly对于T（n）如上。确定性通信模型。 对于确定性的两方模型，获得类似的权衡结果似乎要困难得多。我们展示了一个强有力的权衡结果相对于一个随机预言。具体来说，让L是一个随机稀疏语言。然后，在选择L的概率为1的情况下，存在布尔函数fL（相对于L可有效计算），具有以下性质。如果Alice和Bob都是计算无界的，并且Oracle可以访问L，那么对于fL来说，存在一个确定性通信协议，比如说，O（log2n）比特的通信。然而，任何Alice和Bob在计算上受限的协议都需要<$（n）比特的通信，即使使用Oracle访问L。查询复杂度和属性测试。我们的下一个结果证明了相关模型（如查询复杂性模型和属性测试模型）的权衡。在这些模型中，信息以表的形式存储，查询通过对该表的位探测来回答 我们认为探测器作为存储表和查询方案（或测试器）之间的通信，而查询方案（或测试器）的计算作为本地计算。我们证明：(a)在密码学假设下，存在一种语言L，使得在长度为n的输入上，具有无限计算的查询方案进行O（logn）次查询，而具有有效局部计算的查询方案需要对某个固定的ε<1进行<$（nε）次查询;（b）假设NP/NPBPP，给定任何ε>0，存在一个性质P，使得在长度为n的输入上，计算上无界的测试器只需要nε位来检查输入是否满足该性质。另一方面，计算上有界的测试器需要n1-ε位。在更强的假设下，该结果可以被加强到任何次指数权衡，即所有NP语言没有随机次指数时间算法。自然的权衡问题。除了证明在各种情况下权衡的存在，我们还提出了几个具体的自然权衡问题，并将它们相互联系起来。我们提出了三个不同的权衡问题，在不同的情况下产生的：布尔函数的算术化，多方通信和密码学。我们通过表明第一个问题的“正”解决将意味着第二个问题的解决，而第二个问题又意味着第三个问题的解决来将它们因此，密码学应用可以作为研究其他两个的额外442预赛在本节中，我们描述了通信复杂性模型，我们考虑的问题的正式定义和UP关系的概念。2.1通信复杂性模型[Yao86]设X，Y，Z为任意有限集，f：X×Y→Z为任意函数. 有两个参与者，Alice和Bob，他们希望对f（x，y）进行求值，其中x∈X，y∈Y。Alice只知道x，Bob只知道y。为了评估该函数，它们根据某个固定的协议P相互通信，在该协议中它们相互发送消息协议P在输入（x，y）上的成本是当Alice被给定x而Bob被给定y时，Alice和Bob交换的比特数。 协议P的成本是P在所有输入（x，y）上的最坏情况成本。f的（确定性）通信复杂度是计算f的协议的最小成本。如果允许Alice和Bob进行随机抛硬币，并且他们的消息除了他们的输入和通信之外还取决于抛硬币的结果，我们说协议P是随机的。函数f的随机化通信复杂度是最小成本一个随机协议，计算f的误差最多为1任何输入（x，y）。 误差在协议的内部掷硬币2.2权衡我们现在正式描述我们的权衡问题的两方通信复杂性模型。对于我们考虑的其他模型，也可以给出类似的定义我们的目标是找到一个布尔函数f：X×Y→ {0， 1}，具有以下性质：• f（x，y）可以有效地计算，即在多项式时间内，如果输入x∈X和y∈Y是给定的。• F具有非常有效的通信协议，即对于某些C，具有通信复杂度（logN）C的协议。• 对于f来说，没有一种协议可以同时实现通信和计算的高效性。换句话说，在最坏的情况下，任何Alice和Bob只使用多项式时间进行本地计算的协议都需要几乎线性数量的通信比特。2.3UP关系定义2.1一个关系R×被称为UP关系（见证大小为nk），如果1. 存在一个确定性图灵机，它决定语言{（x，w）|（x，w）∈ R}。2. 对于每个x，至多存在一个w使得（x，w）∈R，并且这个w满足|为|X|K .|k. 我们把这个w，如果它存在的话，记为w（x）。对应于R的搜索问题是找到w使得R（x，w）成立的问题，给定X.5我们将假设存在UP关系，相应的搜索问题是非常困难的。这种假设在密码学中是标准的，因为强单向置换的存在意味着这种硬UP关系的存在。更正式地说，定义2.2我们说一个UP关系R是T（n）-困难的，如果没有一个在时间2 O（T（n））内运行的概率算法能解决对应于R的搜索问题。3两方通信复杂性模型中的权衡3.1随机模型我们从我们考虑的布尔函数的定义开始定义3.1设R <${0，1}<$× {0，1}<$是一个UP关系，其见证大小为nk。 考虑2-player（Alice and Bob）booleanfunctionfR：{0，1}n+ nk × {0，1}nk → {0，1}。AliceBob.如果R（x，w）成立fR（（x，z），w）=0否则其中，a，b表示a，b模2的内积。定理3.2设R是T（n）-hard UP反应. 那么，谓词f R具有以下性质。1. f R可以在多项式时间内计算。2. 存在一个随机化协议，计算f R与O（log n）位通信。3. 如果Alice和Bob在计算上是有界的，那么对于fR的任何随机化协议，即使是多轮的，也将需要N（T（n））比特的通信。证明：观察到fR可以在给定其两个输入的情况下有效地计算。我们只需要检查R（x，w）是否成立，如果成立，输出z，w。引理3.3如果Alice在计算上是无界的，那么存在一个随机化协议，它用O（log n）比特通信来计算f R。证明：Alice计算唯一的w，使得R（x，w）成立。然后，Alice和Bob参与一个如果是，她计算并将答案发送给鲍勃。下面的引理表明，当Alice和Bob在计算上有界时，这种通信有效的协议是不可能的。事实上，这足以证明，只有爱丽丝是计算界的。Bob被允许在计算上是无界的。2.随机通信的复杂度是O（logn）。6算法Ann2引理3.4假设存在一个b（n）比特通信随机化多轮协议栈，它计算f R，其中Alice的运行时间至多为TA（n），那么存在一个随机化算法，它在时间上解决R对应的搜索问题poly（n，2 b（n））·TA（n）。校样：对于论证的其余部分，我们假设对于任何x，w是唯一的w，使得R（x，w）成立，记为w（x）。因此，为了我们的目的，f R（（x，z），w）=<$z，w<$。我们的目标是将给定x计算w的搜索问题与计算低通信协议的网络我们的方法是将一个低通信协议转换成一个高效的预言机，它可以计算出比随机猜测更有优势的z，w给定这样一个预言，我们可以使用Goldreich-Levin重建算法来计算w的少量候选。更准确地说，我们创建了一个我们通过穷举搜索来尝试每个神谕，并利用我们可以识别正确的w的事实。将协议转换为Oracle设T是一个成绩单。为了简单起见，我们假设Alice输出fR（（x，z），w）作为其最后一位;这惯例将转录本的大小增加最多2位。 因此，T包括关于以下的你好我们定义概率预言机AT（x，z）用于计算Δz，wΔ z，如下所示。KT（Input：（x，z）∈ {0，1} × {0，1}）。从爱丽丝那边模拟协议每当需要来自Bob的消息时，请使用转录本T以获得相应的消息。如果在任何时候，Alice根据协议生成的消息与转录本T的内容不一致，则放弃协议并输出随机位b。否则，按照协议进行到底，输出协议栈产生的b首先，我们定义我们的符号的优势，和AT猜测z，w。定义3.5设x ∈ {0，1}n，w = w（x），z均匀分布. 我们定义ADV（x，x）为：ADV（adv，x）= Pr [Alice outputsadvz，wadv]-Pr [Alice其中，Alice和Bob分别使用输入（x，z）和w运行概率，并且概率是针对Alice和Bob对z的选择和对硬币的投掷。 我们类似地定义ADV（AT，x）。 固定x和转录本T，我们定义ADV（x，x，T）为 ：ADV（x，x，T）= Pr [T发生且Alice输出x，z，w，z]。-Pr [T发生并且Alice注意，对AT的优势的唯一贡献从这些定义可以看出，ΣADV（x，x）=ADV（x，x，T）.（一）不由于协议adv正确地计算了fR，因此ADV（x，x）≥1对于每个x。 由于最多有22b（n）个可能的转录本T，从公式（1）可以得出，对于每个x∈ {0， 1}n，存在一个转录本T∈，ADV（X，X，T）≥ 122b（n）+1一个简单但关键的观察是，我们经常可以通过ADV（A，x，T）绑定adv（A，T，x）（二）7WWW222b（n）+1ε命题3.6如果ADV（A，x，T）> 0，则ADV（A，T，x）≥ ADV（A，x，T）。证明：设ρ（x，z）（T）为Alice和Bob的硬币在各自输入（x，z）和w下运行时与T一致的概率同样地，设ρ（x，z）（T）是爱丽丝的硬币与T一致的概率因此，ρ（x，z）（T）是运行AT（x，z）时T最后，设ρw（T）为鲍勃的硬币与T一致的概率注意ρw（T）与z无关。从这些定义可以得出，ρ（x，z）（T）= ρ（x，z）（T）ρ w（T）。（三）固定x（且w=w（x）），设G表示z的集合，使得T给出了n z的正确值，w表示了n z的集合，B表示z的集合，使得给出了不正确的值。然后我们可以用下式表示ADV（A，x，T）和ADV（A，T，x）：ADV（x，x，T）=1.ΣΣ Σρ（x，z）（T）−ρ（x，z）（T）以及（4）2NKWz∈G.Wz∈BΣADV（AT1，x）=2nkΣ Σρ（x，z）（T）−ρ（x，z）（T）.（五）z∈G z ∈B根据等式（3）、（4）和（5），以及ρ（x，z）（T）=ρ（x，z）（T）ρw（T），因此，ADV（λ，x，T）= ADV（AT，x）ρ w（T）.（六）由于0≤ρw（T）≤1，命题成立（注意当ρw（T）= 0时，ADV（x，x，T）= 0）。Q Q固定任意x∈ {0， 1}n。考虑由等式（2）保证存在的转录本T对于这份成绩单，我们从命题3.6得出结论，1ADV（AT_（10），x）≥ 22 b（n）+1.（七）设ε=1.现在我们运行Goldreich-Levin算法GL（见定理3.7），n，ε，Oracle访问AT（x，. ）和谓词R（x，. ）.定理3.7（Goldreich-Levin [GL89]）存在一个随机化算法GL，它具有对一个函数的预言访问和一个谓词，满足：Fix u ∈ {0，1}n. 设h：{0，1}n→{0，1}是一个随机化算法，使得h（v）= u，v以至少1+ ε的概率，其中概率是v的选择，均匀随机选择，以及h的内部硬币投掷。 设P：{0，1}n→ {0，1}是多项式时间可计算谓词，使得P（v）= 1当且仅当u = v. 然后，具有对h和P的预言访问的随机化算法GL满足Pr[GLh，P（n，ε）=u]≥34此外，GL的运行时间至多为poly（n，1）。8定理3.7保证算法GL以恒定概率在时间poly（n，1/ε）中计算w。然而，我们没有成绩单T。（回想一下，我们只知道存在一个满足方程（7）的抄本T，我们不知道如何获得它。）为此，我们跑9Goldreich-Levin算法GL对于每个可能的具有参数n和ε的转录本T。其中一个必须成功。此外，我们可以通过验证R（x，w）成立来检查哪一个成功该算法的总时间最多为22b· poly（n，22b +1）·TA（n）= poly（n，2b）·TA（n）.这证明了引理3.4。为 了 结 束 折 衷结果的证明，我们现在使用以下假设：对应于UP关系R的搜索问题不具有在长度为n的输入上在时间上运行的随机算法。因此，poly（n，2b）·TA（n）≥2<$ （ T （ n ） ），因此b（n）=<$（T（n）），因为TA（n）在n中多项式有界。QQ备注：1. 如果我们假设在UP中有一个搜索问题没有亚指数时间随机算法，我们会得到一个非常强的折衷。这种假设被用于密码学。2. 我们可以在一个较弱的假设下证明相同的结果，即FewP类有一个关系，其搜索问题是困难的。在这种情况下，我们可以使用集合隶属函数而不是等式。3. 如果对应于关系R的搜索问题在x从分布D中选择时的平均情况复杂度至少为2π（T（n））（而不是最坏情况复杂度），则与上述相同的证明表明，对于多项式有界的Alice和Bob，当x从分布D中选择时，fR的平均情况通信复杂度至少为π（T（n）），z一致且w=w（x）。3.2确定性模型奇怪的是，对于确定性模型，似乎更难获得强权衡结果这部分是由于该模型的弱点（例如，不能实现有效的相等性检查协议）。对于这个模型，我们展示了相对于随机预言机的权衡结果。我们强调，我们不使用随机预言“随机化”的协议。特别是，我们要求我们的协议不产生错误。我们首先给出我们考虑的布尔函数的定义定义3.8设L是任何语言。考虑2人（Alice和Bob）布尔函数f L：{0，1}n× {0，1}n→ {0，1}。AliceBob.fL（x，y）=如果x和y都在L中，0否则其中，x，y表示x，y模2的内积。定理3.9设L是一个随机稀疏语言，它包含2k（n）个长度为n的字符串。这里，k（n）可以是使得k（n）= ω（log n）的任何函数。然后，在选择L的概率为1的情况下，谓词f L具有以下性质，给定对L的oracle访问：1. 可以在多项式时间内计算。102. f L具有k（n）+1位通信的通信协议。3. 任何通信协议（确定的或随机的），其中Alice和Bob在计算上是有界的，都需要N（n）比特的通信（即使使用对L的oracle访问）。 注意，协议的选择可以取决于L的选择。性质1很容易验证：要计算fL（x，y），只需使用oracle访问来检查x和y是否属于L，然后在必要时计算它们的内积。接下来，我们证明性质2。引理3.10如果Alice和Bob在计算上是无界的并且具有对L的oracle访问，则f L具有k（n）+1位通信的通信协议。证明：Alice使用Oracle访问L，确定x是否属于L。如果是这样，她还找出了x在L中字符串的字典顺序中的位置。她将此信息发送给Bob，Bob如果x和y都属于L，则输出x，y，否则输出0在本节的剩余部分，我们建立属性3。引理3.11在选择L的概率为1的情况下，对于fL的任何通信协议，其中Alice和Bob在时间2 o（k（n））上运行，将需要N（n）比特的通信，即使使用对L的oracle访问，即使协议被允许随机化并且以小概率出错。引理3.11的证明过程如下。我们从一个协议，这是有效的通信和计算。我们首先表明，甲骨文调用没有太多的使用这样的协议。换句话说，我们可以得到另一个具有类似效率的协议，它不需要对L进行oracle调用。这一步的直觉是，时间有界协议不太可能在任何不同于其输入（x，y）的输入z∈L上查询L。接下来，我们使用内积函数对于低通信协议平均来说很难因此，我们获得的协议定义了一个过程，该过程将来自L的一对随机元素与不访问L的一对真正的随机字符串区分开来。由于L是一种随机稀疏语言，这导致了一个矛盾。证明的细节可在附录A中找到。4相关模型4.1查询复杂性模型我们考虑查询复杂度模型，其中决策过程D探测其输入x，选择查看某些位，而不是其他位。谓词P在n位输入上的查询复杂度由下式给出：最小值最大值（D在x上的探测次数）。Dx这里，D在P的所有决策过程中变化，x在长度为n的所有输入中变化。我们可以考虑这个度量的计算上有界的模拟，其中D被限制为在概率多项式时间内运行。在这样的定义中出现了一些微妙之处。例如，D必须在n之前量化，因为多项式时间是一个渐近概念，但在此量化下，可能没有此外，我们可能希望扩大我们的定义，以允许错误概率。幸运的是，定理4.2建立了一个折衷方案，它显然能够适应这些技术问题。11p定义4.1我们定义lsb（x）为x的最低有效位。 我们说单向置换p是n（n）-lsb困难的，如果在输入x上没有概率多项式时间过程可以以不可忽略地大于2 − n（n）的概率计算lsbl（n）（p−1（x）），其中x是从以下中均匀选择的{0，1}n。我们注意到，这样的排列存在的基础上计算离散的复合整数[SS90，HSS93]的难度定理4.2设p是<$（n）-lsb硬的. 那么就存在一个谓词C：（{0， 1}n）2<$（n）+1−→ {0， 1}具有以下特性：1. C p可以在多项式时间内计算。2. C p的查询复杂度最多为2n。3. 没有多项式时间有界判决过程Q可以仅查询2 α 1（n）比特来计算Cp，其中α <1是任意常数。特别地，输入上存在一个分布，使得如果Q以优势ε计算Cp，则可以以概率<$（ε 2−α <$（n））从p（x）计算lsb <$（n）（x）。证明：（草图）为了符号的简单性，我们写而不是（n）。 我们定义Cp（y，x1，. . . ，x2n），使得p（x i）= y和b（xi）=i（t是一个n比特串）。谓词Cp在多项式时间内是可计算的，因为我们可以遍历i的所有（多项式-许多）可能值。要看到Cp的查询复杂度最多为2n，请考虑以下（计算无界决策过程）：1. 查询y（长度为n位）2. 计算x=p−1（y）和i=lsb（x）。3. 查询xi（长度为n位），并接受当且仅当xi=x。我们证明不存在多项式时间有界决策过程是矛盾的。给定Q，如上所述，我们构造一个多项式时间算法G，用于从p（x）猜测lsb（x），如下所示：1. 给定p（x），计算y = p（x）并选择x1，. . . ，x2从{0，1}n均匀随机地2. 在输入（y，x1，. . . ，x2π）。定义II ={i：Q查询x i的至少一位}。3. 从I中选择一个随机索引i，并输出i（作为一个10位量）。我们将G的成功概率与Q的优势ε在计算Cp（y，x1，. . . ，x2π），其输入分布如下：1. 从{0， 1}n中均匀地选择x，并令y=p（x）和i=lsb（x）。122. 对于j=i，从{0， 1}n中均匀地选择xj。3. 在概率为1/ 2时，选择xi=x（谓词为真）。否则，从下式中均匀地选择xi{0， 1}n−x（谓词为false）。显然，如果在一个特定的运行中，Q从不查询xi中的任何位，那么它在猜测谓词的值方面没有优势 因此，对于概率<$（ε），i ∈ I，其中I如上所定义。在这种情况下，从I中均匀选择将以概率1/|我|.由于I≤2 α（n），定理如下。我们的构造只假设p（）对多项式对手是强的，导致任何多项式折衷。通过对p（）中比特的同时硬度的更强假设，我们可以证明任何次指数的折衷。4.2性能测试属性测试模型与上面定义的查询复杂度模型非常相似。给定一个输入x，测试人员探测x的某些位，我们计算这样的查询的数量。设P是n位输入上的谓词. P的ε-测试器是一个随机化过程，它应该在满足P的输入x上以至少3/4的概率输出1，并且应该在与任何满足P的输入x′相距ε-远的输入x上以3/4的概率输出0。测试器在其他长度为n的实例上的输出是任意的。谓词P在长度为n的输入上的ε-测试复杂度由下式给出：min max（T在x上的探测次数）。Tx这里，T在所有可能的P测试器上变化，x在所有长度为n的输入上变化。定理4.3设L是任意语言，使得L ∈ NP，L/∈ BPP。 固定任何ε> 0。修复任何c> 1且m = n c. 然后，存在一个谓词PL：（{0， 1}n）2m−→{0， 1}具有以下特性：1. P L可以在多项式时间内计算。2. 算法的时间复杂度为O（n）。3. 没有多项式时间有界特性ε-测试器T可以计算小于m比特的PL查询证明：为了定义谓词PL，我们需要引入一些符号。我们从NP中的语言L开始，它不在BPP中，并让RL（x，w）它的对应关系。 不失一般性，让我们假设，|X|为|W|记为n。设C：{0，1}n→ { 0，1}mn是距离大于2εmn的纠错码。 对于y ∈ {0，1}mn和w1，. . . ，wm∈ {0，1}n，定义了我们的性质 PL（y， w1，. . . ， wm）为1，如果y = C（x），对某个x ∈ L，且 RL（x，w1<$··<$wm）成立（即如果w1，. . .，w m构成证明x∈ L）。谓词P L在多项式时间内是可计算的，因为我们可以解码y得到x，然后检查w1，. . . ，w m做证明x在L中的成员资格的证明。为了检查PL的ε-测试复杂度至多为n，考虑以下（计算上无界的）测试器：131. 时间复杂度为O（n2. 检查对于某个x，y是否与C（x）一致。 如果不是，拒绝。3. 否则，检查x是否在L中，如果是，则接受。很容易检查测试器在所有PL成立的情况下都以高概率输出1为了证明测试器的输出在ε-远不满足PL的输入上是正确的，我们进行以下简单的观察。如果y对x∈L进行编码，则可以仅改变w1（即，n=mn比特）以得到满足PL的实例。因此，与满足PL的实例相距ε-远的实例必须包含与任何y=C（x）相距ε-远的y，其中x∈L。因此，我们的计算无界测试器在不查看w1的情况下决定属性。. . ，w m. 测试器探测y的n位，如果它们不符合x∈L的任何码字y=C（x），则拒绝。给出错误答案的概率是两个码字在O（n）随机位置上达成一致的概率。假设存在一个多项式时间有界测试器T，它查询少于m位。我们将使用T来设计一个概率多项式时间算法D，用于L中的成员资格。1. 给定一个输入x，计算y=C（x）。2. 选择m个随机字符串w1，. . . ，w m在{0，1}n中。3. 输出T（y，w1，. . . ，w m）。由于T读取的输入少于m位，我们注意到它甚至没有关于可能的证据w=w1···wm的单个位的信息。因此，算法D与T具有相同的成功概率。 这意味着L在BPP中，这是一个矛盾。 QQ我们的构造只使用了NP/ BPP的事实。一个更强有力的假设，在NP中不具有次指数时间随机化算法使我们能够获得任何次指数折衷。5自然权衡问题与前几节着重于证明权衡的存在性不同，在这一节中，我们提出了几个具体的自然权衡问题，并将它们相互联系起来。我们提出了三个不同的权衡问题，在不同的情况下产生的：布尔函数的算术化，多方通信和密码学。我们通过证明第一个问题的（正）解意味着第二个问题的解，而第二个问题的解又意味着第三个问题的解来将它们5.1算术化中的时间与程度布尔函数的算术化已被证明是复杂性理论[LFKN 92，BF 91]中一个非常有力的工具 多元多项式p（X1，. . . ，Xn）在域4F上被称为扩展布尔函数f：{0，1}n→ {0，1}，如果p和f在{0，1}n上一致;也就是说，如果对于任何x∈ {0，1}n，我们有p（x）= f（x）。 任何函数f允许唯一的多线性扩展，即，延长[4]在下面的内容中，域可以用环来代替，域上的多项式可以用整数上的多项式来代替我们更喜欢在（有限）域上使用多项式，因为它们在应用中很有用。14其中每个变量的度最多为1。如果放松度界限，则扩展的数量变得很大。我们考虑的计算复杂性评估多项式扩展在一个给定的点在Fn。具体地说，给定一个函数f和每个变量的度的约束d，计算上最简单的扩展满足度约束有多容易？在d = 1的情况下，很容易在EXPTIMEf中忽略一个模糊函数的（多个）扩展。但是，如果f是“容易的”（比如在AC 0中），那么关于其多线性扩展的时间复杂度，还有此外，如果我们将度限制放宽到d>1，这是否允许更节省时间的扩展？正如我们将看到的，回答这些问题并不难，时间和程度之间的弱权衡为了更具体地研究时间-度权衡问题，我们用公式表示了以下问题的非一致代数版本。定义5.1给定一个布尔函数f：{0，1}n→{0，1}和（每个变量的）次数上的界d，定义TD（f，d）为最小整数s，使得对于任何域F，F上存在一个大小为-s的代数回路，该代数回路求值f的某个-d次扩张。 我们还允许TD的第一个参数是函数f：{0，1}n→ {0，1}，在这种情况下，度界将是输入长度n的函数，输出也将是n的函数。我们首先证明，如果度界d与f的公式大小一样大，则扩展的时间复杂度受公式大小的限制。5.2假设f：{0，1}n→{0，1}可以用一个大小为n的布尔公式计算。然后TD（f，n）= O（n）.证明：通过直接算术化大小为的公式计算f，可以得到所需的度-的扩展。例如，如果n=1−1−2，则多项式pn可以递归地定义为pn=1−（1−pn1）（1−pn2）。事实上，即使是这个扩张的总次数也是以k为界的。QQ注意，如果用一个公式代替一个电路，那么上面的度就直截了当了算术化可以在电路大小上变成指数我们现在认为，如果坚持最小程度的扩张，那么即使对于一些非常简单的函数f，评估它们的扩张也可能变得#P-困难。这给出了一个可证明的，尽管非常弱的，在标准复杂性假设下时间和度之间的权衡5.3存在一个AC0函数f使得如果TD（f，1）= n O（1）则P =#P.证明草图：设f是3CNF公式的泛函数。 也就是说，f（G;x）=G（x），其中G个变量表示n个输入上的3CNF公式。函数f可以在AC0中计算。 设F是一个特征不同于2，5的域，且β= 2−1（因此β=1−β）。 让 p是域F上f的（唯一）多线性扩张。使用对p的预言，可以容易地计算给定公式g模F的特征的满足赋值的数目。这通过评估p（g; β，β，. . .，β），并将结果除以β n。注意，多重线性扩张中的每个非零项对应于g的某个满意的赋值。因为β= 1−β，所以每一项的值都是βn。Q[5]这个限制不是必要的，但它使证明简单了一点。15αm关于时间-程度的权衡，人们可以提出各种问题。特别地，人们可以尝试分别改进权利要求5.2、5.3中的度界限，理想地缩小两者之间的差距。为了具体起见，我们想强调一般问题的以下特殊情况。问题5.4是否每个多时间可计算f都有多项式次数界d（n），使得TD（f，d）= n O（1）？ d（n）可以独立于f吗？5.2时间与多方同时消息通信协议我们首先从引言中提出一个谜语的答案。然后，我们将谜语扩展到一个更一般的问题，这可能会表现出一个时间通信的权衡，并将其与上述的时间度问题。解决这个问题。 让我们来确定Q的所有部分都在M的下面。我们好k=n+1个玩家可以传送PS（M）=ni=1 每个人都要向裁判发出一个信号，F的有效可计算元素（相同的解决方案适用于任何更多的玩家。高级思想是首先将s i的“加法”表示转换方案1. M的每个条目被提升到F的扩展字段F′，使得|F′|≥k + 1。(This这只是一个概念性的步骤，不需要采取行动，因为F是F′的一个子领域。） 设α1，. . . ，α k是F ′中不同的非零元素。2. 参与者在本地处理他们的M条目，每个参与者为每行输出一个F′元素。令Pi，j表示参与者j对应于第i行的输出。Pi，j的值应满足以下条件：对于每个i，k个点（α j，Pi，j）位于F ′上的一个自由系数为si的一次多项式上。这一阶段的实现将在下面描述。3. 每个参与者j将其来自先前状态的n个本地输出Pi，j相乘，得到单个elementqj∈F′。不存在一个Qthkpoints（αj，qj）nonon iienono n自由系数恰好ni=1 s i= PS（M）。由于k>n，该多项式可以是唯一的。克通过简单的编程来定义，并定义一个简单的自由度函数，即j=1λjqjf ixedcoefficientsλj∈F′. Eachplayrjprojecsλjqjdowntoheor iginalf ield dusaf ieldhomomorphismh：F′→F，并将结果发送给裁判。4. 裁判输出它收到的k个字段元素Itremainstedescr ibeimentionstep2. Defineak×kmarixLoverF′suchtatL，m= 1 −α。 对于每个i，我们令P i，j=km=1L j，m M i，m. 注意，由于L j，j= 0，参与者j可以根据他的本地输入计算这个和这仍然是争论，上述本地计算实际上产生所需的si的1次表示。由此可知，对于L的任何列m，值（α， L，m）位于自由系数为1的1次多项式上。通过克线性，值（α，P）位于自由系数为1·M=s的一次多项式上。J因此，我们已经表明：i、jj=1i，j i16i=1定理5.5函数PS（M）=Qn克j=1 Mij，其中k>n，在计算上允许有效的同时消息协议，其中每个参与者持有除一列之外的所有M，将单个字段元素发送给仲裁者。权衡候选人。鉴于和积问题的简单性，并受5.3节应用的启发，我们想考虑下面的推广。 代替计算行和s i的乘积，我们现在允许任意多项式时间可计算函数f（s1，. . . ，s n）。（为了简单起见，假设f是一个布尔函数，并且我们保证s i∈ {0，1}。注意，在没有对时间复杂度的任何限制的情况下，可以通过将先前的协议与f的多线性扩展相结合来获得通信有效的协议。然而，该协议