感度定理

計算複雑性において、2019年にハオ・ホアンによって証明された感度定理^[1]は、ブール関数の感度は少なくともその次数の平方根であると述べており、これにより1992年にニサンとセゲディによって提起された予想が解決されました。 ^[2]これまでの進歩が限られていたことを考えると、証明は特に簡潔です。^[3]${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$

1980年代後半から1990年代前半にかけてのいくつかの論文^{[4] [5] [6] [7]では、}ブール関数のさまざまな決定木複雑度尺度が多項式関係にあることが示されており、つまり、 がそのような尺度2つである場合、ある定数 に対して となる。NisanとSzegedy ^[2]は、次数と近似次数もこれらすべての尺度と多項式関係にあることを示した。彼らの証明は、Nisanによって導入されたブロック感度というさらに別の複雑度尺度を介して行われた。 ^[7]ブロック感度は、以前に登場したより自然な尺度である（臨界）感度を一般化したものである。^{[8] [9] [10]}${\displaystyle \alpha (f),\beta (f)}$${\displaystyle \alpha (f)\leq C\beta (f)^{C}}$${\displaystyle C>0}$

ニサンとセゲディは^[11]、ブロック感度が感度によって多項式的に制限されるかどうかを尋ねました（感度はせいぜいブロック感度であるため、他の方向は直接的です）。これは、感度がさまざまな決定木の複雑さの尺度、および次数、近似次数、および長年にわたってこれらと多項式的に関連していることが示されているその他の複雑さの尺度と多項式に関連しているかどうかを尋ねることと同じです。^[12]これは感度予想として知られるようになりました。^[13]

長年にわたり、感度予想のいくつかの特殊なケースが証明されました。^{[14] [15]感度定理は最終的に、ゴッツマンとリニアルの縮約を使用して、黄[1]} によって完全に証明されました。^[16]

すべてのブール関数は、多重線型多項式として一意に表現できます。の次数は、 と表記されるこの一意の多項式の次数です。 ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$${\displaystyle f}$${\displaystyle \deg(f)}$

点におけるブール関数の感度は、 となるようなインデックスの数です。ここで、 は、番目の座標を反転することによってから得られます。 の感度は、任意の点における の最大感度であり、 と表記されます。 ${\displaystyle f}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle i\in [n]}$${\displaystyle f(x^{\oplus i})\neq f(x)}$${\displaystyle x^{\oplus i}}$${\displaystyle x}$${\displaystyle i}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle s(f)}$

感度定理は、

${\displaystyle s(f)\geq {\sqrt {\deg(f)}}.}$

一方、タル^{[17]は、ニサンとセゲディ[2]}の以前の境界を改良し、

${\displaystyle s(f)\leq \deg(f)^{2}.}$

感度定理はAND-of-OR関数に対して厳密である: ^[18]

${\displaystyle \bigwedge_{i=1}^{m}\bigvee_{j=1}^{m}x_{ij}}$

この機能には次数と感度があります。 ${\displaystyle m^{2}}$${\displaystyle m}$

を次数 のブール関数とします。の任意の最大項式、つまり を表す一意の多重線型多項式における次数 の単項式を考えます。単項式で言及されていない座標に任意の値を代入すると、次数、さらにを持つ座標上の関数が得られます。 に対する感度定理を証明すれば、 に対しても証明されます。したがって、これからは一般性を失うことなく、 が次数 であると仮定します。 ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$${\displaystyle d}$${\displaystyle f}$${\displaystyle d}$${\displaystyle f}$${\displaystyle F}$${\displaystyle d}$${\displaystyle d}$${\displaystyle s(f)\geq s(F)}$${\displaystyle F}$${\displaystyle f}$${\displaystyle f}$${\displaystyle n}$

新しい関数を定義する ${\displaystyle g\colon \{0,1\}^{n}\to \{0,1\}}$

${\displaystyle g(x_{1},\dots ,x_{n})=f\oplus x_{1}\oplus \cdots \oplus x_{n}.}$

は次数を持つので、 は不平衡（つまり ）であることが示され、 とします。 によって誘導される超立方体のサブグラフ（ 2つの頂点が1つの座標だけ異なる場合に接続されている 上のグラフ）を考えます。感度定理を証明するには、に次数が少なくとも である頂点があることを示すだけで十分です。この簡約は、Gotsman と Linial によるものです。^[16]${\displaystyle f}$${\displaystyle n}$${\displaystyle g}$${\displaystyle |g^{-1}(0)|\neq |g^{-1}(1)|}$${\displaystyle |g^{-1}(1)|>2^{n-1}}$${\displaystyle G}$${\displaystyle \{0,1\}^{n}}$${\displaystyle S=g^{-1}(1)}$${\displaystyle G}$${\displaystyle {\sqrt {n}}}$

Huang ^[1]は、任意の正方形に沿った符号の積が となる超立方体の符号を構成します。これは、この特性を満たすように超立方体のすべての辺に符号を割り当てる方法があることを意味します。同じ符号は、異なる固有値がほとんどないグラフの符号に興味を持っていた Ahmadiら^{[19]によって以前に発見されていました。}${\displaystyle -1}$

を符号に対応する符号付き隣接行列とします。すべての正方形の符号の積が であるという性質はを意味し、したがって の固有値の半分は で、半分は です。特に、(次元) の固有空間は(次元)によってサポートされるベクトルの空間と交差するため、上でサポートされる固有値 を持つの固有ベクトルが存在することを意味します。(これは、Shalev Ben-David ^[20]による Huang の元の議論の簡略化です。) ${\displaystyle A}$${\displaystyle -1}$${\displaystyle A^{2}=nI}$${\displaystyle A}$${\displaystyle {\sqrt {n}}}$${\displaystyle -{\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$${\displaystyle 2^{n-1}}$${\displaystyle S}$${\displaystyle >2^{n-1}}$${\displaystyle v}$${\displaystyle A}$${\displaystyle {\sqrt {n}}}$${\displaystyle S}$

を最大化する点を考えます。一方では、です。他方では、は最大でもにおけるのすべての近傍の絶対値の合計であり、これは最大でも です。したがって です。 ${\displaystyle x\in S}$${\displaystyle |v_{x}|}$${\displaystyle Av={\sqrt {n}}v}$${\displaystyle Av}$${\displaystyle x}$${\displaystyle S}$${\displaystyle \deg _{G}(x)\cdot |v_{x}|}$${\displaystyle \deg _{G}(x)\geq {\sqrt {n}}}$

Huang ^{[1] は、}署名を再帰的に構築しました。 のとき、任意の署名を取ることができます。次元ハイパーキューブの署名が与えられた場合、次のようにの署名を構築します。 を2 つのコピーに分割します。の 1 つに を使用し、もう 1 つに を使用して、2 つのコピー間のすべての辺に符号 を割り当てます。 ${\displaystyle n=1}$${\displaystyle \sigma _{n}}$${\displaystyle n}$${\displaystyle Q_{n}}$${\displaystyle Q_{n+1}}$${\displaystyle Q_{n+1}}$${\displaystyle Q_{n}}$${\displaystyle \sigma _{n}}$${\displaystyle -\sigma _{n}}$${\displaystyle 1}$

同じ符号を直接表現することもできます。をハイパーキューブの辺とします。が異なる最初の座標である場合、符号 を使用します。 ${\displaystyle (x,y)}$${\displaystyle i}$${\displaystyle x,y}$${\displaystyle (-1)^{x_{1}+\cdots +x_{i-1}}}$

感度定理は次のように言い換えることができる。

${\displaystyle \deg(f)\leq s(f)^{2}.}$

ラプランテら^[21]はこれを次のように改良した。

${\displaystyle \deg(f)\leq s_{0}(f)s_{1}(f),}$

ここで、 は内の点における の最大感度です。さらに、この境界は超立方体の 2 つの隣接する点で達成されることが示されました。 ${\displaystyle s_{b}(f)}$${\displaystyle f}$${\displaystyle f^{-1}(b)}$

Aaronson、Ben-David、Kothari、Tal ^{[22] は}、のスペクトル感度という新しい尺度を定義し、 と表記しました。これは、 の感度グラフの隣接行列の最大固有値であり、これはすべての感度辺（となる2点を結ぶ辺）からなるハイパーキューブのサブグラフです。彼らは、Huang の証明が2つのステップに分解できることを示しました。 ${\displaystyle f}$${\displaystyle \lambda (f)}$${\displaystyle f}$${\displaystyle x,y}$${\displaystyle f(x)\neq f(y)}$

• ${\displaystyle \deg(f)\leq \lambda (f)^{2}}$。
• ${\displaystyle \lambda (f)\leq s(f)}$。

この尺度を使用して、ブール関数の複雑さの尺度との間にいくつかの密接な関係があることを証明しました。ここで、は決定論的クエリ複雑さであり、は量子クエリ複雑さです。 ${\displaystyle \deg(f)=O(Q(f)^{2})}$${\displaystyle D(f)=O(Q(f)^{4})}$${\displaystyle D(f)}$${\displaystyle Q(f)}$

Dafniら^[23]は、対称群と完全マッチング 関連スキーム上のブール関数に次数と感度の概念を拡張し、そのような関数に対する感度定理の類似性を証明した。彼らの証明は、Huangの感度定理への還元を使用している。

• 決定木モデル

• アーロンソン、スコット; ベン・デイビッド、シャレフ; コタリ、ロビン; ラオ、シュラヴァス; タル、アヴィシャイ (2021-06-15).次数と近似次数、および黄の感度定理の量子的意味。ACM。pp . 1330–1342。arXiv : 2010.12629。doi : 10.1145 / 3406325.3451047。ISBN 978-1-4503-8053-9。
• アフマディ、バフマン。アリナギプール、ファテメ。ケイバーズ、マイケル S.ファラット、ショーン。ミーガー、カレン。ナセラスル、シャーラ（2013 年 9 月）。 「グラフの個別の固有値の最小数」。線形代数の電子ジャーナル。２６．国際線形代数協会: 673–691。arXiv : 1304.1205。土井：10.13001/1081-3810.1679。ISSN  1081-3810。
• バフナ、ミタリ。ロカム、サティアナラーヤナ V.タベナス、セバスチャン。ベリンカー、アメヤ。ファリシェフスキ、ピョートル。ムショール、アンカ。ニーダーマイヤー、ロルフ (2016)。 「Read -k式の感度予想について」。コンピューターサイエンスの数学的基礎に関する第 41 回国際シンポジウム (MFCS 2016)。 p. 14ページ。土井：10.4230/LIPICS.MFCS.2016.16。ISSN  1868-8969。
• Dafni, Neta; Filmus, Yuval; Lifshitz, Noam; Lindzey, Nathan; Vinyals, Marc; Lee, James R. (2021). 「対称群の複雑性測定とその先 (拡張要約)」。第12 回理論計算機科学の革新 (ITCS) 会議。p. 5 ページ、326343 バイト。doi : 10.4230 /LIPICS.ITCS.2021.87。ISSN 1868-8969  。
• Ben-David, Shalev (2019 年 7 月 3 日)。「感度推測に対するコメント #35 が解決されました」。
• Blum, Manuel; Impagliazzo, Russell ( 1987 )。「ジェネリック オラクルとオラクル クラス」。第 28 回コンピュータ サイエンスの基礎に関する年次シンポジウム (sfcs 1987)。IEEE。doi :10.1109/sfcs.1987.30。
• Buhrman, Harry; de Wolf, Ronald (2002). 「複雑性の尺度と決定木の複雑性: 概観」.理論計算機科学. 288 (1). Elsevier BV: 21–43. doi :10.1016/s0304-3975(01)00144-x. ISSN  0304-3975.
• CS, Karthik; Tavenas, Sébastien; Lal, Akash; Akshay, S.; Saurabh, Saket; Sen, Sandeep (2016). 「選言正規形の感度予想について」。第36 回 IARCS 年次会議ソフトウェア技術および 理論計算機科学の基礎 (FSTTCS 2016)。p. 15 ページ。doi : 10.4230/LIPICS.FSTTCS.2016.15。ISSN 1868-8969。
• Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger ( 1986)。「同時書き込みのない並列ランダム アクセス マシンの上限と下限の時間境界」。SIAM Journal on Computing。15 ( 1): 87–97。doi :10.1137/0215006。ISSN 0097-5397  。
• Gotsman, Chaim; Linial, Nati (1992). 「立方体上の2つの問題の同値性」。Journal of Combinatorial Theory、シリーズA。61 ( 1 ). Elsevier BV: 142–146. doi : 10.1016/0097-3165(92)90060-8 . ISSN  0097-3165.
• Hartmanis, Juris; Hemachandra, Lane A. (1991). 「一方向関数とNP完全集合の非同型性」.理論計算機科学. 81 (1): 155–163. doi : 10.1016/0304-3975(91)90323-T .
• ハタミ、プーヤ。クルカルニ、ラーガブ。パンクラトフ、デニス (2011)。 「感受性予想のバリエーション」。コンピューティング理論。1 (1): 1 ～ 27。土井：10.4086/toc.gs.2011.004。ISSN  1557-2862。
• Huang, Hao (2019-11-01). 「ハイパーキューブの誘導サブグラフと感度予想の証明」Annals of Mathematics . 190 (3). arXiv : 1907.00847 . doi :10.4007/annals.2019.190.3.6. ISSN  0003-486X.
• Klarreich, Erica (2019 年 7 月 25 日)。「数十年にわたるコンピューター サイエンスの推測が 2 ページで解決」。Quanta Magazine。
• Laplante, Sophie; Naserasr, Reza; Sunny, Anupa; Wang, Zhouningxin (2023-03-07). 「感度予想と符号付きハイパーキューブ」. HAL オープンアーカイブ. 2024-04-25閲覧。
• Nisan, Noam (1991). 「CREW PRAM と決定木」. SIAM Journal on Computing . 20 (6): 999–1007. doi :10.1137/0220062. ISSN  0097-5397.
• Nisan, Noam; Szegedy, Mario (1994). 「ブール関数の実多項式としての次数について」.計算複雑性. 4 (4): 301–313. doi :10.1007/BF01263419. ISSN  1016-3328.
• Simon, Hans-Ulrich (1983)。「並列 Ram が非縮退ブール関数を計算する時間の厳密な Ω(loglog n) 境界」。計算理論の基礎。コンピュータ サイエンスの講義ノート。第 158 巻。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 439–444。doi : 10.1007 / 3-540-12689-9_124。ISBN 978-3-540-12689-8。
• Tal, Avishay (2013-01-09)。「ブール関数合成の特性と応用」。ITCS '13: 理論計算機科学におけるイノベーションに関する第 4 回会議の議事録。ACM。doi : 10.1145 / 2422436.2422485。ISBN 978-1-4503-1859-4。
• Tardos, G. (1989). 「クエリの複雑さ、またはランダムオラクルから分離することがなぜ難しいのか?」Combinatorica . 9 (4): 385–392. doi :10.1007/BF02125350. ISSN  0209-9683.${\displaystyle NP^{A}\cap coNP^{A}}$${\displaystyle P^{A}}$${\displaystyle A}$
• ウェゲナー、インゴ（1987）。ブール関数の複雑性。シュトゥットガルト、チチェスター、ニューヨーク、ブリスベン[その他]：ジョン・ワイリー＆サンズ。ISBN 0-471-91555-6。