2 ⊆2Σ简洁零和博弈的复杂性Lance Fortnow计算机科学芝加哥大学美国fortnow@cs.uchicago.edu瓦伦丁卡巴涅茨计算机科学Simon FraserUniversity温哥华，BC加拿大kabanets@cs.sfu.ca计算机科学加州大学圣地亚哥分校美国russell@cs.ucsd.edu加州理工美国加利福尼亚州帕萨迪纳umans@cs.caltech.edu摘要我们研究解决简洁的零和游戏的复杂性，即， 博弈的支付矩阵M由布尔回路C直接给出，使得M（i，j）= C（i，j）。我们补充了已知的EXP-硬度计算精确值的一个简洁的零和游戏的几个结果近似值。（1）证明了对于类promise -Sp，将简洁零和对策的值逼近到一个可加因子内是完全的，加性因子近似。1. 介绍1.1. 零和游戏一个两人零和博弈由一个矩阵指定M. 行玩家选择行i，同时，“promise” version of2列玩家选择列j。然后，S2.据我们所知，这是这门课上第一个完整的自然问题。(2)我们描述了一个ZPPNP算法，用于构造近似的最优策略，因此近似值，一个给定的简洁的零和游戏。作为推论，我们得到，在一个统一的方式，几个复杂性理论的结果，例如，一个学习SAT电路的ZPPNP算法[7]和蔡[9]的最近结果，S pZPP NP.（3）我们观察到，在一个乘法因子内逼近一个无限零和博弈的值是在PSPACE中，并且它不可能在promise-Sp中，除非多项式时间层次崩溃。因此，在一个原因下-向列玩家支付金额M（i，j）行玩家的目标是最小化其损失，而列玩家的目标是最大化其收益。给定概率分布（混合策略）P和Q分别在M的行和列上， 期望收益定义为M（P，Q）=i，jP（i）M（i，j）Q（j）.冯·诺依曼[22]的最小最大定理指出，即使两个参与者按顺序进行博弈，最后一个行动的参与者也会没有任何优势超过谁先行动的球员，即，min maxM（P，Q）= max minM（P，Q）=v，可行的复杂性理论假设，乘法因子P Q Q P简洁的零和游戏的近似严格来说更难这项研究是作者在NEC美国实验室完成的。†由NSF Award CCR-0098197和USA-Israel BSF Grant 97-00188这项研究的大部分是作者在加州大学圣地亚哥分校完成的，由NSERC博士后奖学金支持研究部分由NSF资助CCF-0346991。其中v被称为博弈M的价值。 这意味着存在策略P和Q使得maxQM（P，Q）≤v和minPM（P，Q）>v。这样的策略P和Q被称为最优策略。众所周知，最优策略，因此，游戏可以通过线性规划在多项式时间内找到（参见，例如，[24])此外，寻找最佳策略−∈∃ ∀∃ ∀/∈22⊕2| || ∈ |||| |||||⊕2222∈2/∈∈⊆⊆2等价于求解线性规划，因此是P-困难的。有时，将给定的零和博弈M的值v近似到一个小的加性因子λ内，并找到近似最优的策略Pλ，使得maxQM（P，Q）≤v+v，且minPM（P，Q）>v- 是的与完全最优策略不同，近似最优策略可以并行有效地完成[15，16，21，26]，以及通过随机算法在次线性时间中顺序完成[16]。零和博弈在计算复杂性和计算学习中也扮演着重要的角色在复杂性理论中，Yao [30，32]展示了如何应用零和游戏来证明随机算法运行时间的下限;Goldmann，HaRazstad和Razboro v[14]prove语言L具有多项式时间谓词R（x，y，z），使得如果x在L中则yz R（x，y，z）= 1，如果x不在L中则z y R（x，y，z）= 0。对于每个x，定义收益矩阵Mx（z，y）=R（x，y，z）。如果x L，则有一列全是11.3. 我们的结果我们有三个主要结果的复杂性计算给定的简洁零和游戏的价值。(1) 我们证明，近似的值的简洁零和游戏内的一个附加因素是完整的类承诺-SP，到2 2关于加权阈值电路功率的一个结果old gates; Lipton和Young [20]使用Yao在学习理论中，Freund和Schapire [12，13]展示了如何将重复零和游戏的算法用于在线预测和提升。1.2.简洁的零和博弈一个简洁的两人零和博弈由一个隐式给定的支付矩阵M定义。也就是说，给定一个布尔电路C，使得可以通过在输入i，j上评估电路C来获得值M（i，j）。注意，电路C可以比矩阵M小得多（例如，在M的大小上的多对数）。计算简洁的零和博弈的精确值是EXP-完全的，如图所示，例如，在[11，定理4.6]中。为了完整起见，我们在附录A中给出了另一种证明。几个复杂类的语言判定问题可以有效地归结为计算（或近似）一个适当的非线性零和博弈的值例如，考虑具有多项式时间可计算预测R（x，y，z）的语言L MA [2，4]，使得如果x在L中，则存在y使得Prz[R（x，y ，z）=1]>2/3，并且如果x不在L中，则对于所有y，Prz[R（x，y，z）=1]<1/3，其中y=zpoly（x）。 对于每一个x，我们定义支付矩阵MX（w;y，z）=R（x，y，z w），其行由w很容易看出，如果x，则游戏Mx的值大于2/3。L，且小于1/3，如果xL.[28]《易经》中的“君子之道，焉可诬也？据我们所知，这是第一个自然问题，这类完全的;存在一个自然的完全问题应该使类Sp更有趣的研究。(2) 我们描述了一个ZPPNP算法，用于构造近似最优策略，从而近似给定简洁零和博弈的值。作为推论，我 们 以 统 一 的 方 式 获 得 了 几 个 已 知 的 结 果 ：MASp[28]，SpZPPNP[9]，用于学习SAT的多项式大小的布尔电路的ZPPNP算法，假设这样的电路存在[7]，以及用于确定计算某个布尔函数f的给定布尔电路是否对f近似最优的ZPPNP算法（即，如果没有明显更小的布尔电路计算f）[7]。(3) 我们还观察到，一个简洁的零和游戏的近似值内的乘法因子是在PSPACE，它不是在承诺-SP，除非多项式时间层次崩溃到第二个层次。因此，在合理的复杂性理论假设下，简洁的零和博弈的乘因子近似严格比加因子近似更难。其余的文件第2节包含必要的定义和一些已知的结果需要在稍后的文件。在第3节中，我们证明了一个简洁的零和博弈的近似值是完全的类承诺-SP，第4节给出了一个近似求解给定的简洁零和对策的ZPPNP算法，以及寻找适当的最优策略，并通过统一证明一些新老结果，给出了我们结果的几个在第5节中，我们考虑了将简洁的零和博弈的值近似到乘法因子内的问题。第6节包含结论性评论。在附录中，我们给出了另一种证明，即计算一个简洁的零和博弈的精确值是EXP-困难的，并给出了另一个promise-Sp-完全问题的例子，一个版本的简洁集覆盖。−-∈−--.∈22222∀ ∈ ∃ ∀∀ ∈ ∃ ∀∈∈{|/}2∈∈22∈∈−n∪n| |nnnS2由那些Promise问题nMX--2. 预赛设M为给定的01个值为v的收益矩阵。当v>0时，我们说行混合策略P和列混合策略Q是n-最优的，如果maxQM（P，Q）≤v+v且minPM（P，Q）>v- 是的 对于kN，我们说，混合策略是k-一致的，如果它从一个k纯策略的多重集Newman[23]、Althofer[1]、Lipton和Young [20]的结果表明，对于小的k，每个零和对策都有k-一致最优策略.定理1（[23，1，20]）. 设M是n行m列上的0.1收益矩阵.对于任意的ε >0，令k>max lnn，lnm /（2×2）.然后，对于博弈M的行和列参与人，都存在k-一致的最优混合策略我们对复杂性类P、NP、ZPP、BPP、PH、EXP和P/poly使用标准表示法[25]。我们使用BPPNP来表示一类（不一定是布尔）函数，这些函数可以通过概率多项 式 时 间 图 灵 机 以 高 概 率 计 算 ， 并 可 以 访 问 NP-oracle。无错误类ZPPNP表示可以由具有NP-oracle的概率图灵机计算的（不一定是布尔）函数的类，使得图灵机总是在多项式时间内停止，并且输出函数的正确值，或者以小概率输出FAIL。设R（x，y）是任意多项式时间关系，|y|∈聚乙烯（|X|），令R x={y|R（x，y）= 1}是Wit的集合，其中存在多项式时间可计算谓词R（x，y，z），对于|y|为|z| 10- 12 - 13（|X|），满足以下条件：对每个x ∈+−，x ∈+ ⇒<$0y<$zR（x，y，z）=1且x∈<$− <$$>z<$yR（x，y，z）=设C是一个任意的布尔回路，定义了一个具有支付矩阵MC的连续零和博弈，0≤u≤1且kN是任意的。 我们定义承诺问题简洁的零和博弈值（SGV）P的有效性：（C，u，1k）如果博弈的价值MC至少为u+ 1/k。负的代价：（C，u，1k）如果博弈MC至多为u−1/k。本节的主要结果如下。定理3. Promise问题SGV是Promise-Sp-完全的.首先，我们认为promise-Sp中的每个问题都是多项式时间可约化为promise问题SGV，即，问题SGV对于类promise-Sp来说是困难的。引理4. 问题SGV是promise-S p-hard。证据设P是promise -Sp中的任意promise问题.设R（x，y，z）是多项式时间可计算谓词，使得x≠+ yzR（x，y，z）= 1和x−z y R（x，y，z）= 0。对于任何x，考虑简洁的零和博弈，def支付矩阵M（z，y）= R（x，y，z）。注意，对于每个与x相关联的nesses，且令L R=XR x= 0是由R定义的NP语言。 Bellare，Goldreich，Petrank [5]证明了x LR的见证人可以使用NP-预言机随机 一 致 地 生 成 ; 下 面 的 定 理 是 对 Jerrum ， Valiant 和Vazirani [19]的早期结果的改进。定理2（[5]）. 对于如上所述的R、R x和L R，存在ZPPNP算法，其将x作为输入LR和输出 集合R x的均匀分布元素，或输出FAIL;输出F AIL的概率由严格小于1的常数限制。3. Promise-Sp-完备性一个promise问题是一个对的集合，n>0（n+，n−），其中n+，n−n{0，1}n是不相交的子-x+，列参与人有一个纯策略y能达到收益1。另一方面，对于每一个x≠−，有一个纯策略z使行参与人获得收益0。也就是说，对于x+，博弈Mx的值为1，对于x− ， 博 弈M x的值为0。通过设置C （z，y ）=R（x，y，z），u=1/2，k= 3来定义（C，u，1 k）上的SGV问题完成了证明。接下来，我们证明问题SGV是在类中，promise-Sp .引理5. SGV∈ promise-Sp.证据设（C，u，k）是SGV的一个实例，使得由C定义的博弈M的值至少为u +1/k，或者至多为u1/k。设收益矩阵M有n行m列，其中n，m≤ 2|C|.利用定理1，我们可以选择参数s∈对于每一个n >0。在n+=n>0n+中的字符串称为n的正实例，而在n-= n中的字符串称为n的正实例。n>0如果+−={0，1}，poly（C，k），使得博弈M对于行和列参与人都有s-一致的1/（2k）-最优策略. 现在我们定义一个新的支付矩阵M_n，其秩为：那么，语言定义了一种语言。类S p的标记为nn=nssize-s从1，. . . ，n，并且其列由m=mssize-s多集标记promise-p2塞福尔从{1}。 对于1≤≤1，1≤≤，令，的。.. ，m我JSIΣ−2|Tj|P不我 不不t=1恩岛例如，maxQM（P<$，Q）≤v+v，.Σ=Σ和T j表示从{1，. . . ，n}和{1，. . . ，m}。我们定义混合策略Pt+1用于下一轮博弈。行玩家的目标是使其总损失最小化.1如果1ΣM（ a，b）> u不t=1 M（Pt，Qt），其中T是总轮M（i，j）=|TJ||Tj|0否则a∈Si，b∈Tj在重复的游戏中。Freund和Schapire提出并分析了下面的学习算法，称为MW，意思是考虑博弈M的值v至少为u+1/k的情况。 那么对于列局中人，存在一个s-一致的1/（2k）-最优策略.设Tj是对应于此策略y的大小为s的多集. 根据1/（2k）的定义─重量”。算法MW从行上的均匀分布开始在每轮t之后，行参与者的新混合策略通过以下规则计算：βM（i，Qt）最优性，我们对每一个1≤a≤n，Pt+1（i）=Pt（i）Zt、（1）1<$M（a，b）>v−1/（2k）>u+1/k−1/（2k）>u。其中Z=P（i）βM（i，Qt）是归一化因子，并且∈b∈Tj因此，对每一个1≤i ≤n≠，M ∈（i，j）= 1.一 个对 称 的论证表明，如果博弈M 的值至 多为u1/k，则有一个r o w1≤i ≤ nn≠，使得M（i，j）=0，对于所有1≤j≤m。定义谓词R（（C，u，1k），j，i）=M（i，j）将问题SGV放入类promise-Sp中。现在我们可以证明定理3。β[0，1）是算法的参数。用文字来说，新的混合策略的行播放器重新权衡行，在给定列玩家的当前策略Qt的情况下，与i遭受的损失成比例地降低行i的概率：损失越高，新的概率越低。定理6（[13]）. 对于任意n行n元的矩阵M，以及任意混合策略序列Q1，. . . ，QT，混合策略序列P1，. . . ，PT由算法MW产生定理3的证明 证明由引理4和引理5得出。其中β=不.1个以上2lnnTΣ−1满足以下条件：不4. 近似一个连续零的值<$M（P t，Q t）≤ min <$M（P，Q t）+3<$T ln n.和博弈t=1t=1在这里，我们将展示如何近似值，以及如何在ZPPNP中学习给定简洁零和博弈的稀疏近似最优策略。4.1. 学习玩重复的游戏我们的学习算法将基于Freund的换句话说，算法MW只比完全知道所有混合策略Q1，. . .，Q T将由列播放器播放。现在，假设列参与人以最具对抗性的方式选择混合策略，即，在每轮测试中，Qt= arg max M（ Pt，Q）.Q则概率分布P<$=1<$TPt，求和游戏;一个类似的算法是由Grigoriadis和Khachiyan [16]，受Brown和Robinson [6，27]提出的解决零和博弈的经典确定性迭代方法的启发。我们首先描述[13]的重复游戏设置。假设M是一个收益矩阵。在重复博弈的每一轮t中，行参与人在行上有一个混合策略Pt.在充分了解Pt的情况下，列参与人选择（纯）策略Qt;原则上，Qt可以是任意的，但在ad中，算法产生的混合策略的年龄定理6中的，当T足够大时，将是博弈M的近似最优策略定理7（[13]）. 设M是一个n行的收益矩阵，其元素在[0，1]中。设v为博弈M的价值。设混合策略P1，. . .，PT的列策略可以由定理6的算法MW选择，而列策略Q1，. . .，Q T被选择为使得Q t=argmaxQM（Pt，Q），对于每个1 ≤ t≤ T. 然后将混合在零和博弈的对抗性设置中，列参与者可能会选择Qt来最大化其预期收益，当前策略Pt的球员。在第一轮之后，strategiesP？=1TT.t=1不Pt和Q1TTt=1Qt是[13]学习如何玩重复的零-最佳条件为：¯ ¯行玩家遭受损失M（Pt，Qt）。《The Row Player》观察每行i的损失M（i，Qt），并选择min PM（P，Q<$）>v−1。因此，我们有v − ∞ ≤ M（P，Q）≤ v + ∞。不不k=1β=βP−| || |不−不和1 ≤ r ≤ b t，定义关系R（j，. . . ，j; i，r）= 1不2不哪里Zni=1≤ΣM（i，j，k）是一个归一化因子。证据下面的不等式序列证明了该定理：v= min maxM（P，Q）的极小极大定理Q1，. . . ，Q t，输出根据如由算法MW的规则（1）定义的混合策略Pt+1分布的行索引i。PQ证明我们假设算法的参数β≤maxM（P<$，Q）Q定理6的MW是有理数β=b1/b2，对于某些整数b1，b2（通过取一个充分好的有理数=max1<$M（P，Q）根据P<$的定义Q如果有必要，可以使用β近似值对于整数1≤i≤n21不k=1Kt=1当且仅当r ≤ βPtM（i，j）bt. （一）看（一）1maxM（P，Q）TQt=1不关系R的性质，并应用定理2，我们得到一个对（i0，r0）均匀分布在证人之间，R. 注意，对于每个1≤i≤n，=1<$M（P，Q）根据Q的定义对第一个元素为i的对进行采样，TT Tt=1不不Pt+1（i）=βPtM（i，jk）/Z，≤min1<$M（P，Q）+∞ 由定理6=minM（P，Q<$）+由Q<$的定义P≤max minM（P，Q）因此，对R的见证进行均匀采样并输出采样对的第一个元素i0，得到了所需的ZP PNP算法，采样时间为Pt+1。Q P=v + v的最小最大定理。因此，我们可以使用算法MW，通过设置T∈O（lnn/δ2），将给定零和博弈的值近似到可加因子δ内。4.2. 计算近似最优策略ZPPNP现在我们将展示如何调整[13]的算法MW以获得用于计算简洁零和游戏的稀疏、近似最优策略的ZPPNP算法。设M是由某个布尔电路C隐式给出的n行m列的支付矩阵，使得C（i，j）=M（i，j），对于所有的1≤i≤n和1≤j≤m。注意n，m≤2|C|. 我们需要构造一个算法为了使用定理7计算近似最优策略P<$，我们需要在游 戏 的 每 一 轮 t 中选择最 佳 可 能 列 策 略 Q t= argmaxQM（P t，Q），给定行参与者的当前混合策略P t。目前尚不清楚这是否可以在BPPNP中实现。然而，定理7的证明可以很容易地修改为，如果每个Qt被选择为如果M（Pt，Qt）>maxQM（Pt，Q）σ，对于某些σ >0，则所得的混合策略P<$和Q<$将是（σ+σ）-最优（optimal）。换句话说，在每一轮t中选择一个几乎最佳的列策略Q t就足以获得近似最优的策略P′和Q′。我们现在解释如何在BPPNP中选择这样的几乎最佳可能列策略Qt。读者不应该对我们正在考虑BPPNP算法而不是ZPPNP算法的事实感到震惊。这个BPPNPal-在C中运行时间多项式。显然，我们没有足够的时间来写下行参与者的混合策略，因为它们是由算法MW根据规则（1）计算的。幸运的是，每个这样的策略Pt+1都有一个简洁的描述：它只依赖于t个纯策略Q1，. . . ，列参与人在前t轮博弈中使用的Q t，以及每个纯策略是矩阵M的列的索引1≤j≤m。因此，Pt+1完全由电路C加上至多tlogm位的信息来定义。 利用定理2，我们能够根据分布Pt+1进行采样。引理8. 设M是由布尔回路C指定的支付矩阵。存在ZPP NP算法，给定t个列索引j1，. . . ，j t对应于纯策略在我们最终的无错误的ZPPNP算法中，出租m只会被用作子程序固定舍入t，1≤t≤T。 我们假设我们已经选择了策略Q1，. . . ，Q t−1，因此混合策略P t是完全指定的;基本情况是t= 1，其中，P1简单地是矩阵M的行上的均匀分布。引理9. 存在BPP NP算法，给定列索引j1，. . .，j t-1，其中t>1且σ > 0，输出列索引j t，使得在算法的随机选择上具有高概率，M（P t，j t）>maxjM（Pt，j）σ。该算法的运行时间是t，1/σ，C的多项式，其中C是布尔电路它定义了矩阵MP不t=1tk=1≤≤|Σ≤∈Σ| |−| |∈∈| |∈−−−1jm，1|S|i∈SM（i，j）−J K1i∈S1我们有这个|1i∈SM（i，j）− M（P t，j）|≤σ′，对于每个K色谱柱1≤Ji∈S两种混合策略的描述所以Q不¯不t=1我们现在可以在P中选取jji∈SM i，j，ΣΣ2Pr of. 设σ′=σ/2。F或整数k被指定为后r，通过根据分布Pt独立随机采样k次来形成多集S;这可以是在ZPPNP中通过引理8实现对于任何固定列Σ并且多集S1和S2产生稀疏近似最优策略，即，max1<$M（i，j）≤v+δ，M（P，j）|>σ′至多为2e−2kσ′2 关于The Hoeffding不[17]第十七因此，概率至少为1 − 2me−2kσ'，|S|JM. 让我们称这样的多集好.S和min1M（i，j）> v − δ。选择kpoly（logm，1/σ），我们可以使构造好的多重集S的概率足够高。假设我们已经构造了一个好的多重集S，= arg max（）NP如下首先，我们通过下式计算w= maxM（i，j）：遍历所有可能的整数该算法的运行时间在C语言中是多项式的，1/δ。Pr of. 设σ=δ/12。正如在定理前面的讨论中所解释的，我们可以在BPPNP中构造等w= 0，. . . ，k，问NP-查询：是否存在列1≤j≤m使得证明了v 2σ≤M（P<$，Q<$）≤v+2σ，其中NP<$i∈SM（i，j）> w？所需的w将是最后一个值BPP算法的时间是poly（|C|，1/σ）。 也就是说，我们的问题得到了肯定的回答。(To为了加快速度，我们也可以在0和k之间的整数区间上进行二分查找。一旦我们计算了w，我们就可以在col上进行二分搜索umn索引1≤j≤m，询问NP-查询：当前间隔的上半部分中的列j，两种策略都有很大的概率在加性因子2 σ内近似最优。设 S2是由纯策略序 列 Q1 ，. . . ，QT用于定义Q<$，其中T=k2pol y（C，1/σ）. 为了构造S1，我们从P′inde-K1次。显然，这两个多集都可以是一致的。thatiSM（i，j）=w？在最多logm步之后，我们将得到所需的j= arg maxji∈SM（i，j）。菲-在ZPPNP中构造。通过从S1均匀采样，我们可以近似M（P<$，Q<$）在一个加法因子σ内的概率分布最后，由于S是一个好集，我们有M（Pt，j）>1|S|<$i∈SM（i，j<$）−σ′>maxjM（Pt，j）−2σ′=Poly（C，1/σ）时间具有高概率，通过Hoeffd- ing边界[17]。也就是说，很有可能，结果-maxjM（Pt，j）−σ，如所承诺的。运行引理9的BPP NP算法，T = O（lnn/σ2）步，我们构造了一个纯策略序列Q，. . .，Q，使得，在估计u将使得v3σ≤u≤v+ 3σ，S1和S2给出的稀疏混合策略在加性因子3σ内近似最优。最后，我们展示了如何消除我们的问题的错误1T建筑。给定估计u和稀疏随机选择的算法，混合策略P=战略和S，我们可以在PNP中测试，1吨不P（由规则（1）确定）和Q<$=1<$TQS12是 2σ-最优。 也就是说，maxQM（P，Q）≤v+2σ，并且¯max1J<$M（i，j）≤u+6σ，（2）minPM（P，Q）>v2σ，其中v是博弈的值M. 因此，我们有很高的概率，v2σ≤M（P<$，Q<$）≤v+2σ。和|i ∈S1|i∈S1¯ ¯由于混合策略P和Q都有小的偏差，min1<$M（i，j）>u− 6σ。（三）因此，它们都可以通过ZPPNP算法进行采样Q′的情况是非常复杂的，因为它是在我|S2|j∈S2大多数T列。从P<$a中取1≤t≤T均匀随机，使用算法从Pt中，并输出结果行索引。最后，我们可以证明本节的主要定理定理10.有一个ZPPNP算法，给定一个如果测试（2）和（3）都成功，则输出u，S1和S2;否则，我们输出FAIL。为了分析正确性，我们观察到，具有高概率，u，S1和S2使得v−3σ≤u≤v+ 3σ，max1<$M（i，j）≤v+ 3σ≤u+ 6σ，Jδ>0和布尔电路C定义支付矩阵M的未知值v，输出一个数u和多集S1和S2的行和列索引，使得|= k 1，|S2| 2）2）2）3）3）3）4）4）4）5）|C|，1 / δ），|,1/δ),v−δ≤u≤v+δ，我2j∈S2t=1不Σ|i ∈S1|i∈S1同样的min1|j ∈S2|j∈S2M（i，j）> v −3σ> u − 6σ。我2∈∈Σ222∈/∈| |∈∈2| |p∈因此，我们的检验（2）和（3）很有可能通过。当它们成功时，输出u将使博弈M的值v近似在加性因子6σ δ内，而由 S1和 S2给出的稀疏策略将近似在加性因子12σ=δ内是最优的。4.3. 应用在本节中，我们将展示如何用定理3和定理10以非常统一的方式导出几个新旧结果。定理11（[28]）. MAP.S.P证据 让L MA是任何语言。正如我们在引言的第1.2节中所讨论的，对于每一个x，都有一个简洁的零和博弈Mx，它由一个布尔电路Cx定义，（φ，x）其中φ是大小为n的布尔公式，x是对φ的变量的赋值。我们定义M（C，（φ，x））=1如果φ（x）为真，则C（φ）输出FALSE0否则。换句话说，矩阵M被定义为惩罚行玩家使用不正确的SAT电路。根据我们的假设，存在一个大小为s（n）的电路C，它正确地决定SAT。因此，矩阵M的行C将完全由0将定理10应用于简洁的零和对策M（δ=1/4），我们得到了学习大小为k的多路集S的ZPPNP算法，对于k个poly（s（n）），使得对于M的每一列jMx的值1/3如果x/∈L。如果x∈L，至少为2/3，且至多为1M（i，j）≤1/4。|i ∈ S|i∈S让我们以SGV实例的格式将每个x与三元组（Cx，1/2，18）相关联由定理3可知，SGV的结果问题是由多项式时间谓词R定义的promise-Sp。定义新谓词这意味着，对于每个大小为n的可满足布尔公式φ，多重集S中至少有3/4的条件将为φ产生一个令人满意的赋值。因此，以下多项式大小的布尔电路将正确地决定SAT：R（x，y，z）d=efR（（C必需的.，1/2，18），y，z）表明L∈Sp，在输入φ，输出1上当且仅当S中至少有一个回路对φ产生满意的赋值。定理12（[9]）. SpZPPNP证据设L S p为任何语言。正如我们在引言的第1.2节中所论证的，S2的定义意味着，对于每个x，存在一个简洁的零和博弈，如果x L，则该博弈的值为1，如果x L，则该博弈的值为0。由于通过定理10将一个简洁的零和博弈的值近似到1/4以内是在ZPP NP中，因此结果如下。利用类似的思想，我们还对文[20]中的一些结果作了如下改进，这些结果隐含在文[7]中。定理14（[7]）. 设C是n位输入上的布尔电路，s是与C等价的最小可能布尔电路的大小 有一个ZPP NP算法，给定一个布尔电路C，输出一个大小为O（ns +n log n）的等效电路。以下结果的证明利用了Yao [30，32]提出的算法和输入之间的零和博弈的概念定理13（[7]）. 如果SAT在P/poly中，则存在证据 对于每一个1 ≤ i ≤ C，考虑简洁的零和博弈，其支付矩阵Mi的行用大小为i的布尔电路A标记，列用n位字符串x标记.我们定义Mi（A，x）=0，如果A（x）= C（x），如果A（x）/= C（x），则Mi（A，x）= 1。ZPP NP算法学习多项式规模的电路SAT。证据设s′（n）poly（n）是一个布尔电路的大小，它决定了任何大小为n的布尔公式的可满足性。利用SAT的自约化性质，得到了s（n）poly（s′（n））回路的存在性，给定大小为n的布尔公式φ作为输入，输出FALSE如果φ是不可满足的，则T_RUE与φ的一个满意赋值一起，如果φ是可满足的。对于任何n，考虑由支付矩阵M给出的简洁的零和游戏，其行由大小为s（n）的电路C标记，其列由对标记。显然，博弈M i的值对所有i>s都是0.将定理10的ZPP NP算法应用于每个i = 1，. . . ，C依次，我们可以找到第一个i0≤ s，使得博弈M i0的值至多为1/4。类似于定理13的证明，我们得到一个小的多集的大小为i0的电路，使他们的大多数同意C的所有输入。不很 难 验 证 这 个 构 造 的 电 路 的 大 小 至 多 为 O（ni0+nlogn），如所要求的。定理14也可以用来检查ZPPNP是否给定的布尔电路是近似最小的可能性，即，如果没有尺寸小得多的等效电路，.X±2222| |2∈⇔ ∀ ∃||||2/∈/∈∈2222⊆5. 乘数近似在前面的章节中，我们研究了将给定的简洁零和博弈的值近似到一个可加因子内的问题。考虑乘法因子近似问题是很自然的：给定一个布尔电路C，计算一个未知值v的零和博弈的支付矩阵，以及一个参数（用一元表示），计算w=（1）v。从Luby和Nisan [21]的工作中可以得出，将给定简洁零和博弈的值近似到乘法因子λ（用一元表示）内是在PSPACE中。文[21]中的结果讨论了输入约束矩阵和约束向量均为正的显式给定[21]中的算法使用多项式数量的处理器，并且在输入矩阵的大小上以时间多项式和多项式运行。通过放大，得到了隐式给定零和的PSPACE算法在列上的分布至少可以获得收益2−|z|>0对于行参与人的任何策略y。因此，一个将简洁的零和博弈的值近似到乘法因子λ1内的算法可以用来确定语言L，这证明了引理。定理15的证明通过定理的假设和引理16，我们得到了φpφp，这意味着坍缩PH= φp。6. 结论我们已经证明了，近似的问题的价值简洁地给出零和游戏是完整的这似乎是第一个自然问题证明捕捉的复杂性SP。我们要指出的是，2个p平板电脑设备.我们不知道简洁的零和博弈的乘法因子近似是否可以在多项式时间层次中完成。这是一个有趣的开放式问题。然而，我们可以证明，除非多项式时间层次崩溃到第二层，乘法因子近似严格比加法因子近似更难。定理15. 如果每一个简洁的零和博弈的值都可以近似为在某个乘法常数因子φ<1内，则PH= φp。promise-S2 中唯一一个有趣的问题。 在Ap-我们证明了简洁集覆盖的一个版本是也是promise-Sp-complete。针对给定的简洁零和博弈，提出了一种学习近似值和近似最优稀疏策略的ZPPNP算法。我们的算法允许我们通过姚[30，32]发现的零和博弈与计算复杂性之间的联系，以完全一致的方式证明[7，9，20]中的一些结果。我们的结论是观察，去随机化我们的ZPPNP算法是不可能的，而不证明类EXPNP的超多项式电路下界。定理15的证明依赖于下面的简单引理。引理16. 将一个简洁的零和博弈的值近似到一个乘法常数因子λ 1内的问题是一<个困难的问题。定理17. 如果存在一个P NP算法，可以将任何给定的简洁零和博弈的值近似到一个加性因子内，则EXPNP/EXP/poly。证明素描。 我们的证据是矛盾的。 如果EXPNP=2证据 设L∈P是任意语言，R是P/poly，则EXPNP=EXP=MASp通过组合2多项式时间可计算三元关系，对于所有输入x，x L y zR（x，y，z），其中y和z是x的多项式。对于每个输入x，考虑以下零和博弈Mx：Buhrman和Homer [8]，Babai，Fortnow和Lund [3]，Russell和Sundaram [28]的结果由于通过定理3，一个简洁的零和博弈的值对于promise-Sp是完全的，所以假设该问题的PNP算法的存在将意味着崩溃.1如果R（x，y，z）为真0否则。Sp= P NP。因此，我们将得到EXPNP=PNP，即我们主张，如果x L，则博弈Mx的值大于0;如果xL，则Mx的值为0。事实上，如果xL，那么行参与人有一个纯策略y，对于列参与人的任何策略z，都能达到收益0。另一方面，如果x∈L，则一致致谢我们要感谢Joe Kilian让我们注意到[11]，感谢Christians Papadimitriou回答我们关于线性规划和零和博弈的问题。我们也感谢大卫·朱克曼的帮助讨论。Mx（ y，z）=不可能对角化。2 ⊆2引用[1] I.Alt hoéfer. 随 机 策略和凸组合的 稀 疏 逼 近 LinearAlgebra and its Ap-plications，1994.[2] L. 巴巴随机性的交易集团理论进行中-第17届ACM计算理论研讨会，第421-429页[3] L. 巴拜湖Fortnow和C.隆德非确定性博览会-基本时间有两个证明者交互协议。计算复杂性，1：3[4] L. Babai和S.莫兰 亚瑟梅林游戏：一个随机的-化证明系统和复杂性类的层次结构。计算机与系统科学杂志，36：254-276，1988。[5] M.贝拉雷岛Goldreich和E.彼得兰克 统一的一般-使用NP-oracle的NP-witnesses。信息与计算，163：510[6] G.布朗 虚拟博弈的迭代解。在T. Koopmans，编辑，生产和分配的活动分析，考尔斯委员会专著第13卷，第129-136页。威利，纽约，1951年。[7] N. 布绍伊河 Cl ev e，R. G a vald a`，S. Kannan和C. Ta-Mon. 预 言 机 和 查 询 ， 足 以 精 确 学 习 。 Journal ofComputer and System Sciences，52（3）：421[8] H. Buhrman和S. 侯默超多项式电路，几乎稀疏的神谕和指数层次。在R. Shyamasundar ， 编 辑 ， Proceedings of the TwelfthConference on Foundations of Software Technology andTheoretical Computer Science ， Volume 652 ofLectureNotes in Computer Science ， pages 116-127 ， Berlin ，Germany，1992。施普林格出版社[9] J. - Y.菜SpZPPNP.在第四十二届会议上，IEEE计算机科学Ence，第620-629页[10] R.卡内蒂关于BPP和多项式时间层次。信息处理信件，57：237[11] J. Feigenbaum，D. Koller，and P. Shor. 一个博弈论交互式复杂性分类。在Proceedings of the Tenth AnnualIEEE Conference on Computa- tional Complexity中，第227-237页[12] Y. Freund和R.夏皮尔博弈论，在线预测和提升。在Proceedings of the Ninth Annual Conferenceon Computational Learning Theory，第325-332页，1996年。[13] Y. Freund和R. 夏皮尔适应性游戏玩弄我们-乘法权重。博弈与经济行为，29：79[14] M. Goldmann，J. H acumberstad和A. 拉兹博尔湖多数gates与一般加权阈值门相比。计算复杂性，2：277[15] M. Grigoriadis和L.哈奇扬 近似解平 行 矩 阵 游 戏 在 p.Pardalos ， 编 辑 ， Advances inOptimization and Parallel Computing，第129-136页1992年，阿姆斯特丹，埃尔-塞维尔[16] M. Grigoriadis和L.哈奇扬一个次线性时间随机-矩阵对策的近似算法运筹学快报，18（2）：53[17] W.赫夫丁有界随机变量和的概率不等式。美国统计杂志，1963年，第13- 30页[18] R. 因 帕 利 亚 佐 一 些 困 难 问 题 的 硬 核 发 行 版 。 在Proceedings of the Thirty-Sixth Annual IEEE Symposiumon Foundations of Computer Science，第538-545页[19] M.耶鲁姆湖Valiant和V. Vazirani。从均匀分布随机生成组合结构。理论计算机科学，43：169[20] R. Lipton和N.年轻大型零和博弈的简单策略及其在复杂性理论中的应用.在第26届ACM计算理论研讨会的开幕式上，第734-740页[21] M.卢比和N.尼桑正线性规划的一个并行逼近算法在Proceedings of the Twenty-Fifth Annual ACM Symposiumon Theory of Computing，第448-45
我的内容管理
展开
