Comments
Description
Transcript
Nash 均衡の計算複雑度について
Title Author(s) Citation Issue Date Nash均衡の計算複雑度について 田中, 嘉浩 經濟學研究 = Economic Studies, 59(4): 9-15 2010-03-11 DOI Doc URL http://hdl.handle.net/2115/42773 Right Type bulletin (article) Additional Information File Information ES59-4_002.pdf Instructions for use Hokkaido University Collection of Scholarly and Academic Papers : HUSCAP 経済学研究 北海道大学 59−4 2010．3 Nash 均衡の計算複雑度について 田 １ 中 はじめに von Neumann and Morgenstern［27］によっ 嘉 浩 ２ 計算量の理論の発展 2.1 定 義 て 1944 年に 著 さ れ た名 著 Theory of Games Turing［25］が Turing マ シ ン を 提 案 し ， and Economic Behavior を嚆 矢とする ゲーム Church に より 計算 可能 とい う概 念が 1936 年 理論 に於いて ， 1950 年に Nash［18］が導 入し に定義されて以来，先ず「何が計算可能か？」と た重 要概念であ る Nash 均衡の 計算が「 効率的 いうこ とが問題 にされ， Cantor によっ て実数 解 法 」を持 た ず ， 従来 の NP 完 全 と 違っ た ， が有理数と違って不可算であることを示すこと PPAD 完全というクラスの問題に属するという に用いられた対角線論 法による Turing マシン 結果を，Daskalakis, Goldberg and Papadimi- の停止判定問題が計算不可能であることの証明 triou 等は国際計算機学会（ACM）のCommuni- ［25］等 の理論 的結果 が初期 の段階 で得ら れて cations of the ACM 誌 2009 年 2 月号に掲載さ いる。 れた論文［8］“The complexity of computing それ以降は「効率的解法」に関する研究から計 a Nash equilibrium” で彼等 自身 の研究 を中 算 複 雑 度 に 関 す る 理 論 が ， 特 に 1971 年 の 心に紹介した。 Cook の 充 足 可 能 性 判 定 問 題（Satisfiability; 更に ，21 世紀に 解決さ れるべき 数学の ７大 SAT）が NP 完全問題に属することの証明［7］， 未解決問題（ミレニアム懸賞問題）の一角である Karp［14］によ る 多 項式 時 間 帰着 可 能 によ る Poincaré 予 想が 2002∼2003 年に Perelman に NP 完全の証明法を嚆矢にして 大きく発展して よって解決されたからかどうか分らないが，未 きた。 解決問題を含む計算量に関する話題が最近脚光 簡単 に説明 すると ， クラス P と は多項 式時 を 浴 び つ つ あ る 。 Communications of the 間アルゴリズムで判定できる問題の集合であり， ACM 誌 2009 年 9 月号に Fortnow 氏によるサー クラス NP とはインスタンスが与えられた時に ベイ 論文［11］“ The status of the P versus YES で あるこ とを多 項式時 間で判 定でき る判 NP problem”が出て以来大変な反響を受けて 定問 題の 集合で ある 。 判定問 題 B 頴 NP は， おり， それを受け て更に一般紙 でも The New NP に属する他の全ての問題が B に多項式変換 York Times 紙（10 月 7 日）に一般向けに的を得 可 能な時 に NP 完 全（NP Complete）とい う。 た解説が為されている。 NP 完全問題は その定義から クラス NP の中で 本稿では計算量に関する概念や最近の研究を 概観し，多くの重要な応用を持つ Nash 均衡の 最も難しい部類の問題である。 クラス P に属する代表的な問題を示す。 計算量に関する論文［8］の結果を示す。 ・素数判定問題 10（564） 経 済 学 研 究 59−4 この問題は多項式時間で効率的に判定できるこ 変数の数が増大するにつれて計算量の爆発が起 とが保証されている。判定問題ではないが， き，どんなにコンピュータのハード面が進歩し ・ソーティング ようが大きなサイズの問題は急に解けなくなる。 ・最小木問題 P＝ NP ? 問題が 21 世紀に解決されるべき数学 ・辺数最大マッチング問題 の未解決問題の１つとして解決を嘱望されてい ・最大フロー問題 る所以である。 ・行列の積や連立一次方程式 最適 化問 題若 しく は判 定問題 B 頴 NP は， NP に属する他の全ての問題が B に多項式変換 ・割当問題 ・線形計画問題 可能な時 に NP 困 難という。 NP 困難 問題はそ 等の探索問題は多項式時間のアルゴリズムが知 の定義からクラス NP の中で最も難しい問題と られている。辺数最大マッチング問題はこの中 少なくとも同程度に難しい同等である。整数計 では特殊な問題だが，親しい者同士が分ってい 画問題や巡回セールスマン問題（TSP）は NP 困 る 集団で ペア の組 み方を 考え る問 題で あり， 難であるが，相転移のイジングモデルの基底状 Edmonds［10］が 1965 年に 効率 的な 多項 式時 態を見つける問題等も NP 困難として知られて 間アルゴリズムを考えている。なお，最小木問 いる。 題の様に マトロイド（matroid）とい う特定の構 造をもつ問題は貪欲算法によって効率的に解け ることが分っている。 ところで，線形計画問題（の許容解の判定）や 2.2 P 莞 NP への試み Razborov［21］は 1985 年に 回路 計算 量 に関 して， 大きなクリーク問題 を解く，NOT ゲー 素数 判定問題 は， YES に対す る問題 も NO に トを 含まない AND と OR からな る小さな（単 対する問題もどちらも多項式時間で判定でき， 調）回 路が存在しないこ とを示し， 回路を一般 良い特徴付けを もつ（NP 瓦 coNP に属する）ク 化 して P 莞 NP の証明 とな るこ とが 期待 され ラスの問題であることが分っている。このクラ たが，後に NOT ゲートを含めば旨く行かない スの問 題で線形計画問 題が 1979 年に， 素数判 こと等が彼等自身の研究で示されている。 定 問 題 が 2004 年 に 多 項 式 時 間 アル ゴ リ ズ ム トートロジーかどうかを判定する問題が NO ［1］が 発見さ れたこ とは興 味深い が， P＝（NP となる為には，そういうインスタンスを代入す 瓦 coNP）? 問題は未解決問題である。 れば 分るが ，YES となる 為には すべての イン NP 完全に属する代表的な問題を示す。 スタンスを考えることになる。導出（resolution） ・充足可能性判定問題（SAT） はトートロジーを証明する標準的な方法だが， ・点カバー問題（Vertex Cover） 1985 年に Haken は鳩巣原理を表すトートロジー ・Hamilton 閉路問題（Hamilton Circuit） を短い導出法で示せないことを示した。しかし ・クリーク問題（Clique） なが ら， こ の結 果は P 莞 NP を示す のに 必要 ・ 3 次元マッチング問題（ 3 DM） であるが，十分ではない。 ・分割問題（Partition） 定義から NP 完全に属する問題のどれか１つに 2.3 困難の扱い でも多項式時間 アルゴリズムがあれば，NP の NP 完全 の問題を実際に解かなければならな すべての問題が多項式時間で判定できることに い場 合， 仮 に P 莞 NP な らば そうい う方 法論 なるが，現在のところそういうアルゴリズムは が本流になるが，幾つかのアプローチが知られ 発見されておらず，寧ろ存在しないと信じられ ている。 ている。多項式アルゴリズムが存在しなければ 先ず最適に近い近似解を求める近似アルゴリ 2010.3 Nash 均衡の計算複雑度について 田中 ズムを考える試みが為されており，例えば，最 11（565 ） いる。 大 重 み カ ット 問 題（ NP 困 難 ）で は Goemans and Williamson［13］は半正定値計画を用いて 定 理２ cf.［2］ 最大 クリ ーク 問題 は P 莞 NP 1.139-近似アル ゴリズム（但し， k -近似 アルゴ ならば APX を持たない。 リズムとは，最小化問題（最大化問題）では最適 1 解の k 倍以 下（ k 倍 以上 ）の解 を多 項式時 間で 一方，分割問題から生じる最小 2 分割問題には 求めるアルゴリズム）を得ている。 PTAS が存在することが知られている。 ■ 2.4 節に関連 するが，近 似率 k 噂 1 が定数で ある時 にその様な 近似アルゴ リズムは APX， 更に， 任意の å 瓜 0 に 対して k 厩 1茨å とでき 2.5 P 莞 NP ? の応用 P ＝ NP ならば計算量の爆発の為に解けない でいた多くの重要な問題が一気に高速に解ける る時に PTAS と定義されている。 巡回セールスマ ン問題（NP 困難 ）で辺長を地 様になり，人類は大きな恩恵を受けることは間 図 上の 距離 で与 え る時（Euclidean TSP）， 三 違いない。しかしながら，P 莞 NP がもっとも 角不等式が成立するので近似可能と知られてい らしいと思われているが，だからこそ，計算の るが，Arora［3］は平 面の再帰的分割に基いた 困難性は積極的に応用されている。 PTAS を与えている。 暗号，特に日常的に認証や電子署名で良く使 計算量の理論では通常は最悪時間を問題にす われる公開鍵暗号では，P 莞 NP を仮定して成 るが，平均時間を扱えればより実態に合ってい 立しているのだが，それだけではなく，素因数 ることも多いが，Levin［15］は特定の確率分布 分解の平均複雑度に関する仮定も必要である。 を考えて P ＝ NP ? 問題の確率版を定義してい そこで公開鍵でなく ，例えば認証では，NP 完 るが， NP 完全が最悪時間 で成立する時に平均 全問題を用いて，証明者がその解を知っている 時間でも成立するかどうかは未解決問題である。 ことを検証者にゼロ知識証明で分らせる，とい う様な応用を考えることができる。 2.4 対話的証明と近似不可能性 問題 A に対して， 任意の 解 x をその 全ての ビッ トで はなく ， 入力の ビッ ト数を n と して 長さ r廓n 較の 乱数を 用いて ， q廓n 較個のラ ンダ 2.6 量子コンピュータと NP完全問題 素数判定 問題は 2004 年に 多項式時間 アルゴ リズム［1］が発見されたが，合成数の素因数分 ムビットを用いて検証することを考える。x が 解の効率的なアルゴリズムはまだ知られておら 真 に YES の時 に x を YES と判 断す る確 率が １ であり ， x が 真に NO の時 に x を NO と判 ず，現代暗号は素因数分解等の問題の困難さに 断す る確率が 1 2 以上 であるとき に，問 題 A は PCP 廓r廓n 較, q 廓n 較較に属するという。 基いて成立しているものである。 Shor［24］は 1997 年に 素 因数 問 題や 離散 対 数問題を効率的に解く仮想的な量子コンピュー タを提案したが，ハードでの実現を目指した研 究方向も進んでいる。 次の定理が成立する。 しかしながら，素因数問題も離散対数問題も 定理１（PCP 定理） ［2］ NP ＝ PCP（log n,1） ■ NP 完全 問題 より は易 しい クラ スであ り， NP 完全問題を量子コンピュータだけで効率的に解 けるとは思われていない。 PCP 定理を 用いて クリー ク問題 から生 じる 最大クリーク問題に対して次の結果が得られて 12（566） 2.7 経 済 更なる方向性 学 研 究 59−4 となる」 問題を 1 ステップで解く概念上の装置をオラ ク ル（oracle）とい うが ，Baker, Gill and Solovay［5］はオラ クル付きのチューリ ングマシン 時に 混 合戦略 の組 廓s1 , s 2, 且, si , 且, s n 較を 均衡 （Nash 均衡）と定義し， 「混合戦 略の範囲で少 なくとも１つ は均衡点 を考えることにより，P と NP が等しくなる様 が存在する」 に も P と NP が等 しく なら ない 様に も相 対化 ことを，角谷の不動点定理を用いて証明した。 （relativize）で きる こと を示し た。 停 止問 題が しかしながら非ゼロ和対称２人ゲームでさえ， 計算不可能である証明に用いられた対角線論法， Nash 均衡が２つ以上 あるかどうか判定するの ひいては集合論的方法は相対化を利用しそうな は NP 完全問題 であることが分っている［12］。 ので P ＝ NP ? 解決に無力と思われている。 Razborov and Rudich［22］は “ natural ” という概念を提案し， NASH： 混合 戦略の範 囲で Nash 均 衡を１ つ求めよ。 「一般の（単調でない ）回路に対する 超多項式 下界は，暗号の様に逆関数の計算が困難な一方 と 定 義 す る 。 NASH は ， ゼ ロ 和 ゲ ー ム で は 向性関数の存在の仮定の下で，“natural proof” 1920 年 代に von Neumann によっ て線形 計画 は存在しない」という結果を得ている。 に定式化できることが示されているので高速に Mulmuley and Sohoni［17］は 幾 何 学 的 計 解ける。しかしながら，非ゼロ和（双行列）ゲー 算 量 の 理 論（Geometric Complexity Theory; ムでは Lemke-Howson のアルゴリ ズムがある GCT）を 用いて P ＝ NP ?を扱 う方法 を提 案し ものの， 多項式時間アルゴリ ズムではない ている。彼等は或る代数的変数上での群表現に ［23］こと が知ら れてお り， 効率的 な解法 が知 基い た高次元 多面体 Pn を考 え， もし全て の n られていない。そこで効率的な解法の探求と共 に対して Pn が整数点を含 むならば，入 力 n の に，その計算量に関する研究が進展してきた。 Hamilton 路が 多 項 式で な い O廓n log n 較下界 を 持つことが示され，P 莞 NP となることを示し 3.2 全探索問題 ている。彼等自身は理論の完成には 100 年掛か 第２節では判定問題に対するクラスを紹介し ると言っているが，代数幾何を用いる方法は有 たが，探索問題，しかも必ず解を持つ探索問題 望視されている。 には，単に NP 完全を探索問題に拡張した FNP や 必ず 解を 持つ 探索 問題 に拡 張し た TFNP だ ３ Nash 均衡の計算複雑度 けではない，より細かいクラスを考えれる。 「有向グ ラフで入次数 と出次数の違 う点があ 3.1 背 景 れば，必ずもう１つそういう点がある」 von Neumann 等 によ って 1940 年 代に 創始 という事実を用いて解の存在を示し，正確には されたゲーム理論は経済学だけでなく政治学， も う １つ の 点 を求 め る 線終 端 問 題（END OF 行動科学等重要な応用を持っている。 THE LINE）に 帰着 さ れ る 全て の 探 索問 題 は Nash［18］は非ゼロ和非協力ゲームに於いて， プ レ イヤ ー i, i 頴 格1, 且, n隔の 混 合 戦略 を si , 利得関数を fi とする時に， 「各プ レイヤー i に対 して， 他のどの プレイ ヤーも混合戦略を変える動機がない，即ち， 袷 E拡fi廓s1, s2, 且, si, 且, sn 較 郭噂 E拡fi廓s1, s2, 且, si , 且, sn 較 郭 PPAD （Polynomial Parity Argument in a Directed graph）と定義 される。 PPAD は 完全問 題を 持つ ことが 分って おり， そ れを PPAD 完 全という。 PPADは FP と FNP の間にある複雑度の問題 であるが，実験結果からは効率的なアルゴリズ 2010.3 Nash 均衡の計算複雑度について 田中 13（567 ） ムはないと信じられている。 の確率（混合戦略）を表す変数と媒介プレイヤー 3.3 への利得を考えることによって実現される。各 3 点 x 頴 拡0,1 郭 を 3 人 プレイ ヤー X1, X2, X3 の Nash 均衡と PPAD Daskalakis, Goldberg and Papadimitriou “go”の確率を並べた点と考える。Nash 均衡 ［8］は次の結果を示している。この節の定理自 点 廓y 1 , y2 , y 3 較で 終 わ る 様に X1 , X2 , X3 に 利 体 は前 に Papadimitriou［19］によ って 単 独に 得を与えることにより，BROUWER を 3 人ゲー 得られているが，別証明の［8］のアイディアを ムの NASH で計算できる様に構成できる。よっ 示す。 て定理 3 は証明された。 定理 3［8］ NASHは PPAD 完全である。 ■ 3.4 近似計算について Nash 均衡を効率的に解 くアルゴリズムは知 これを証明する為に彼等は間に次の不動点を られておらず，幾つかの近似アルゴリズムが考 えられて いる。近似 アルゴリズムに於 いて，± 近似 Nash 均衡とは各々の戦略が ± 近似最適反 求める問題を考えている。 m BROUWER：リ プシ ッツ連 続関 数 F: 拡0,1郭 応戦略であることを言う。 m 臆 拡0,1 郭 に対 して， 精度 å 瓜 0 が 与えら れた m 時 に d廓F廓x 較, x較閏 å を 満た す x 頴 拡0,1 郭 を NASH の 近 似 ア ル ゴ リ ズ ム は 例 え ば Daskalakis, Mehta and Papadimitriou［9］ 求めよ。 によ る多項 式時間 0.38 近似 アルゴ リズム が得 られており，APX が存在するとは言える。 BROUWER が PPAD であることが，三角分割， 色 付け ， 等の 手法 により Sperner の 補題 を用 いて， BROUWER が線終端問題（PPAD 完全） に帰着されることから示されている。 NASH が BROUWER に帰着されることは， 均衡点でなければ，現戦略を他戦略に変えよう NASH の 近 似 ア ル ゴ リ ズ ム で ， 任 意 の å 瓜 0 に 対 し て は ， Lipton, Markakis and Mehta［16］は n 人ゲー ムに対して準 指数時間 2 O廓nl og n 慰å 較の近 似ア ルゴ リズ ムを 提案 し てい る。しかしながら，PTAS が存在するかどうか はまだ未解決問題である。 とする不満足なプレーヤーが存在するので戦略 から戦略への選好関数を構成することで示せる。 ４ 終わりに これで NASH が PPADであることは示された。 次に， NASH を クラス PPADで完全 である Nash 均衡解の計算はゼ ロ和２人ゲームの場 ことを示す為に，線終端問題のグラフを対応す 合でさえ，戦略数が非常に多く，混合戦略の空 るゲームに変換する。まず，線終端問題のグラ 3 フ を 拡0,1郭 に 埋め 込 む こと で BROUWER に 変換できることから次の定理が成立する。 間次元が高くなって扱いにくい問題があるが， ∼ Pena［20］はその混合戦略の単体に対して知ら れ てい る近接 関数（prox-function）を 用い て滑 らかな問題にしてから非線形計画の手法である 定理 4［8］ BROUWERは PPAD 完全である。 ■ 勾配法を適用する提案やポーカーへの応用を示 している， Papadimitriou［19］は［8］の論文 より前 に， BROUWERの F を計算するのに， 加算，乗 必ず 解を 持つ探 索問 題に対 して PPAD だ けで 算，比較等の演算子を組合わせて構成するのだ なく幾つかの重要なクラスを提案している。 が， そ れらの 各演 算子は プレイ ヤー の“go” その中では， 14（568） 経 済 「有向グ ラフで閉路を 持たないもの は必ず終 59−4 学 研 究 other geometri c prob lems, ” J ourn al of the ACM 45 , 753-782 （199 8）. 点を持つ」 と い う 事 実 に 基 い て 解 の 存 在 を 示 す PLS ［ 4 ］ Arrow, K .J., an d Debreu, G.,“ Existence of （Polynomial Local Search）というクラスと， an equi librium for a competitive econ omy, ” 「グラフ で奇数次数の 点があれば必 ずもう１ つ奇数次数の点がある」 Econometrica 27, 265 -290（ 1954）. ［ 5 ］Bak er, T.P., Gill, J, and Solovay, R.,“ Rela- と い う 事 実 に 基 い て 解 の 存 在 を 示 す PPA tivizati ons of the P＝ ? NP Question,” SIAM （Polynomial Parity Argument）という クラス Journal on Co mpu ting 4, 431-442 （197 5）. も定 義さ れてお り， PLS が完 全問 題を持 つこ ［ 6 ］Con itzer, V ., and S an dholm, T.,“N ew com- とや ，PPAD 盈 PPA が成立 すること等 が示さ plexity results about Nash equlibria,” Games れている。 and Econ omic Behavio r 63 , 621-641 （200 8）. 次の定理が成立することも興味深い。 ［ 7 ］ Cook, S .A., “ The compl exity of theorem proving procedures,” Proc. 3rd Ann ual ACM 定 理 5 交換均衡 問題（Exchange Equilibrium） Symposium on the Theory of Computing, New や 競 争 均衡 問 題（Competitive Equilibrium）は York, 151 -1 58（1 971）. PPAであり，更に PPAD 完全である。 ［ 8 ］ Daskalakis, C., Goldberg, P.W., an d Pap adimitriou, C.H.,“The complexity of com- ［証 明］ 交換均衡については［19］Lemma 4 の Corollary 。 競 争 均 衡 に つ い て は ， 同 puting a Nash equilibri um,” Communications of the ACM 5 2, 89-97（ 2009 ）. Corollary か ら 角 谷 の 不 動 点 を 求 め る 問 題 が ［ 9 ］Daskalakis, C., Mehta, A., and Papadimitriou, PPAD 完全であることと，角谷の不動点を応用 C.H.,“A note on approximate Nash equilibria,” し て競争 均衡 が求 まる こと［4］と ， 単位 球面 ・ S n芋1 上に p の 方向に矢 印で方 向付けれ ること ［1 0］ Edomonds, J.,“ Path s, trees and owners, ” から PPAD 完全であると言える。 ■ Proc. 2nd WINE, 297-306（2006）. Canadian J. Math . 17, 449-4 67（1 965）. ［1 1］ Fortnow, L.,“ The status of the P versus いずれにしても Nash 均衡解の計算という重 要な 問題のク ラスが Brouwer や角谷の 不動点 NP problem, ” Communications of the ACM 52, 78 -8 6（20 09）. の計算 と同じ特定の 計算の困難な クラスの ［1 2］ Gilboa, I, an d Z emel, E.,“ Nash and corre- PPAD 完全であるという結果が確立されたこと lated equilib ria: Some complexity considera- は意義深い。 tions, ”Games and Economic Behavior 1, 8093（ 1989）. 参考 文献 ［ 1 ］ Agrawal, M., K ayal , N., an d Saxena, N., “ PRIMES is in P” Ann. Math . 1 60, 781-7 93 （200 4）. ［ 2 ］ Arora, S.,“ Probabil istic checking of proofs and the hardness of approximation problems,” Ph. D. thesi s, U C Berkeley,（ 1994 ）. ［ 3 ］ Arora, S., “ Polynomial time ap proximation schemes for Euclid ean traveling salesman and ［1 3］Goemans, M.X., and Williamson, D.P.,“ Improved approximation algorithms for maximum cut and satisfiab ility p roblems using semidefinite programmi ng, ” Journal of the ACM 42 , 1115-11 45（1 995）. ［1 4］ K arp , R.M., “ Reducib ility among combinatorial probl ems, ” in: Complexity of Computer Computations, Mill er et al. Eds., Plenum, 85103 （1972 ）. 2010.3 Nash 均衡の計算複雑度について 田中 ［1 5］Levin, L.,“Average case complete problems,” SIAM J. Com pu ting 1 5, 285-28 6（19 86）. ［1 6］ Lipton, R.J., Markakis, E., an d Meh ta, A., “ Playing l arge games using samp le strategies,”Pro c. 4rd EC, 36-41 （200 4）. 15（569 ） Soviet Math ematics Doklady 31, 485-493（1985） . ［2 2］ Razborov, A., and Ru dich, S., “ Natural proofs,” J. Co mp. Syst. Sci. 55 , 24-35 （19 97）. ［2 3］ S avan i, R., and Stengel, B.,“Hard-to-solve bimatrix games,”Econometrica 74, 397-429（2006）. ［1 7］ Mulmuley, K., and S ohoni, M.,“ Geometric ［2 4］ Shor, P., “ Polynomial-time algorithms for complexity th eory I: An app roach to th e P vs. prime factorization and discrete l ogarithms on NP and related problem,” SIAM Journal on a Computin g 3 1, 496-526 （197 5）. ［1 8］ Nash, J., “ Noncooperative games, ” A nn. Math. 54 , 2 89-295 （195 1）. ［1 9］ Papadimitriou, C.H.,“ On the complexity of the parity argument and other inefficient p roofs of existence,” J. Comp. Syst. Sci. 48, 498-5 32 （199 4）. ∼ ［2 0］ Pen a, J.,“ Nash eq uilibria comp utation via quantu m computer, ” SIAM Journal o n Computin g 26 , 1484-15 09（1 997）. ［2 5］ Turin g, A.,“O n computable numbers, with an application to the En tscheid ungsproblem”, Proc. Lond on Math. Soc., 42 230-265 （1 936） , 43 5 44-546 （1937 ）. ［2 6］U zawa, H.,“Walras's existence theorem and Brouwer's fixp oint theorem,” Econ. Stud. Quart. 13, 59 -6 2（19 62）. smoothing techniques,”Optima 78, 12-13（2008）. ［2 7］ von Neumann , J., and Morgenstern, O., ［2 1］Razb orov, A.,“Lower bounds on the mon o- Theory of Games and Economic Behavior, Prin- tone complexity of some Booloean functions,” ceton U niv. Press, Princeton,（ 1944）.