論文翻訳: On Span Programs

2020年2月25日 1993年の論文 #SP

M. Karchmer ^∗

Department of Mathematics
Massachusetts Inst. of Technology
Cambridge, MA 02138

A. Wigderson

Department of Computer Science
Hebrew University
Jerusalem, Israel 91904

Abstract

我々は計算の線形代数モデル、Span Program を導入しその上下限を証明する。これらの結果は複雑性と暗号化において次の適用をもたらす:

$\mathcal{SL} \subseteq \oplus \mathcal{L}$ ( $\mathcal{NP} \subseteq \oplus\mathcal{P}$ の弱い対数空間 (logspace) 類似物)。
数え上げ分岐プログラム (counting branch program) で最初の超線形サイズの下限。
情報理論的な秘密共有スキームを備えたより広範囲なクラスの機能。

span program と counting branch program 間の主な接続の証明では Razborov の一般的な近似方法の変種を使用する。

^*Partially supported by NSF grant CCR-9212184 and DARPA contract N00014-92-J-1799.

Abstract
1 導入
2 背景 [under construction]
3 The basic model: Span Programs
4 Symmetric vs. Counting Logspace
5 Canonical Span Programs
6 Lower bounds on Span Programs
1. 6.1 Affine dimension
2. 6.2 A lower bound for Majority
7 Monotone Span Programs
8 Monotone Span Programs and secret sharing
Acknowledgements
References
翻訳抄

1 導入

計算モデルに数え上げ能力を与えることは複雑性理論の古くて有益なテーマである。そのような方向の一つは無制限 fan-in 回路に mod $m$ ゲートを追加することだった。これは $m$ が素数の場合には Razborov and Smolensky [15, 21] の指数関数下限をもたらし、 $m$ が複素数の場合には $\mathcal{ACC}$ のパワーのフラストレーションの問題をもたらした。

もう一つの方向性は、非決定性多項式時間チューリングマシンに受け入れパス (accepting path) の数を数え上げさせることだった。mod 2 の計算するためにこれはクラス $\oplus \mathcal{P}$ を定義する ([12, 6])。Valiant and Vazirani [23] はこのモデルの威力を示すために、まず $\oplus \mathcal{P}$ に $\mathcal{NP}$ の確率論的なチューリング縮小を与えた。Toda [22] この手法を用いてより強力な結果を証明した。これは、多項式時間階層全体が $\oplus \mathcal{P}$ に確率論的チューリング縮小可能であることを証明した。さらに Allender [2] が示すように、上記の定深回路 (constant-depth circuit) に用いられた技術によっても同じ結果を得ることができる。

ここでは受け入れパス (mod $m$ ) の数を数え上げる非決定論的な対数空間マシンに興味がある。多項式数え上げクラス $\bmod_m \mathcal{P}$ の類似体 $\bmod_m \mathcal{L}$ は [5] で定義され最初に研究された。[5] では、 $GF(p)$ 上の線形代数における行列式、ランク付け、線形システムの解放など自然な問題のほとんどが $\bmod_p \mathcal{L}$ クラスの対数空間であることが示されているが、対数空間での数え上げについてはほとんど知られていない。例えば、多項式時間のケースと異なり、 $\mathcal{NL}$ と $\oplus \mathcal{L}$ 間の関係は不明である。さらに、これらの数え上げクラスを捕捉する数え上げ分岐プログラムには自明でない加減は知られていなかった。

この論文ではこれらの問題の両方についての進展を示している。対称非決定性クラス $\mathcal{SL}$ がすべての素数 $p$ に対する $\bmod_p \mathcal{L}$ に含まれることを示している ( $\mathcal{SL}$ , 対称対数空間 (symmetric logspace) は対数空間で無向 st-connectivity に縮小できるすべての問題のクラス)。これ以前は [1] の結果に従う $\mathcal{SL} \subseteq \mathcal{L}/{\rm poly}$ のみが知られていた。

また $\bmod 2$ を数え上げる分岐プログラムの最初の非自明な加減を証明する。最も興味深い (最も大きいわけではないが) ことは Majority 関数を計算するそのようなプログラムのサイズのわずかに超線形 ( $\Omega(n \log \log \log^* n)$ ) な下限である。実際、個の証明は線形サイズのプログラムを受け入れるこれらのしきい値関数を特徴付ける。非決定性分岐プログラムにおける Majority の加減は Razborv [18] によって証明されており、実際に我々は彼の機構の多くを使用している。対照的に、より弱い決定性分岐プログラムに対して Majority [3] に対する最良の下限は $\Omega(n \log n / \log \log n)$ である。

両方のタイプの結果へのルートは同じデバイス ─ span program を経由する。(任意の体 $K$ 上の) span program は $n$ 個の変数に対する関数 $f$ を次のように計算する線形代数モデルである。 $K$ 上のベクトル空間 $W$ 、非ゼロベクトル $w \in W$ を固定し、 $X_i^\epsilon$ ( $1 \leq n$ , $\epsilon \in \{0,1\}$ ) を $f$ の $2n$ 個のリテラルに対応する $W$ の $2n$ 個の部分空間とする。任意の真理値 $\sigma$ を変数に割り当てると正確に $n$ 個のリテラルが "true" となる。 $f(\sigma)=1$ の場合に限り $n$ 個の関連する部分空間が固定ベクトル $w$ にまたがることを要求する。このモデルのサイズ測定値は $2n$ 個の部分空間の次元の合計である。

span program のサイズが対称分岐プログラムのサイズの下限であることは非常に簡単に理解できる。我々が証明した重要な関係は span program サイズが数え上げ分岐プログラムの下限であることである。次に、Majority の span program は超線形サイズを必要とし、前述の下限を意味することを証明する。線形代数、特に双対性を用いて canonical span program の概念を開発した。これらは一般的なモデルと同様に強力だが、そのためには下限を得ることがより容易である。canonical モデルはまた span program サイズが制約を適用するときに増加できないという点で、ブール関数の自然な複雑性尺度であることを確立するのに有用である。これは定義からは明らかでないことに注意。

また、 $n$ 個の製のリテラルに対してのみ部分空間を割り当てる、span program の単調 (monotone) バージョンも検討した。このモデルはいくつかの理由で興味深い。第一に、単調関数のみを計算するが、その計算自体が非単調演算、すなはち有限体上の線形代数を伴うことに注意。第二に、しきい値関数における単調 span program サイズに対する厳しい厳密な境界を取得し、このモデルでは (他と違って) これらすべての関数 (AND, OR 以外) が同等であることを発見した: Majority, Threshold-2 およびそのほかのすべては正確に $\Theta(n \log n)$ のサイズを必要とする。第三に、このモデルが Shamir [20] の意味での情報理論的秘密共有を捕捉することを示す。これにより Rudich [19] の結果を拡張し、このような効率的秘密共有スキームが存在する関数のクラスを拡大することができる。他の方法では、既存のスキームは span program に上限を与えることができ、実際、 $O(n \log n)$ の Majority の上限は Shamir の構造に触発された。

最後に、下限に span program を使用するというアイディアの進化について説明する。この論文は [18] と [9] の論文から着想を得たものであり、どちらも共通の祖先として論文 [16] を持っている。[16] では Razborov が一般化近似法を導入している。彼はすべてのブール関数 $f$ に集合被覆問題 (set cover problem) ( $\Delta_M(f)$ , $S_M(f)$ ) を割り当てる方法を示した。ここで $\Delta_M(f)$ は被覆するユニバースであり、 $S_M(f)$ は被覆するユニバースのサブセットのファミリーである。下付き文字 $M$ は、このユニバースが (本質的に) $f$ のゼロ集合上のすべての単調関数 (monotone functional) であるとという事実を表している。彼は最小被覆数 $\delta_M(f)$ が $f$ のブール回路サイズの下限であることを証明した。さらに、この数は多項式因子に厳密であるため $\mathcal{P}$ を特徴づけるために使用できる。この (またはその他の) 方法ではまだ超線形回路サイズは証明されていないが、Razborov は分岐プロブラムにこの一般化近似法をうまく適用した。[18] の中で彼は被覆問題 ( $\Delta_M(f)$ , $S'_M(f)$ ) を定義した。彼は被覆数 $\delta'_M(f)$ が $f$ の非決定性分岐プログラムのサイズと性格に等しい (したがって $\mathcal{NL}$ を特徴づける) ことを示した。最後に、彼は上で述べた下限を暗示する $\delta'_M({\it Majority})$ の超線形下限を証明することができた。

[9] では被覆されるべきユニバースが $f$ のゼロ集合上のすべての線形関数 (linear functinals) の集合である近似法の変種を提案している。我々は被覆問題 ( $\Delta_L(f)$ , $S'_L(f)$ ) の被覆数 $\delta_L(f)$ 、下限非決定論的回路サイズ、 $\mathcal{NP}$ を特徴づけるために使用できることを証明した。[18, 9] のアイディアを組み合わせることにより Counting Branching Programs のサイズの下限となる制約被覆数を得た。さらに、制約被覆問題 ( $\Delta_L(f)$ , $S'_L(f)$ ) は線形代数捜査の後、我々の第一モデルである span program を単純化する。

2 背景

我々はすべてのモデルを不均一に定義する。これは下限をより強くする。その一方で、すべての上限が対数空間的に一様であることが容易に分かるだろう。漸近表記を用いる場合、我々は $n$ でパラメータ化された関数群を通常のように考える。

定義 1 . Branching Program は 2 つの特定のノード $s, t \in V$ とラベリング $\mu: E \to \{x_i^\epsilon | i \in [n], \epsilon = 0,1\} \cup \{1\}$ (ここで $x^1=x$ および $x^0=\bar{x}$ とする) を持つ有効非巡回ラベル付きグラフ $G(V,E,\mu)$ である。 $G$ のサイズ $s(G)$ は 1 とラベル付けされていないエッジの数として定義される。 $G$ が $t$ を除くすべての頂点から正確に 2 つの出力エッジを持つように制限され、相補的リテラルによってラベル付けされているなら、分岐プログラムは決定論的であるという。

各 (入力) シーケンス $\sigma \in \{0,1\}^n$ に対し、 $\mu(e)=1$ であるか、または $\mu(e)=x_i^\epsilon$ かつ $\sigma_i=\epsilon$ である場合に限り、 $e=E_\sigma$ を持つ $G$ の (ラベルなし) 部分グラフとなるように $G_\sigma(V,E_\sigma)$ を定義する。

Figure 1 の表はいくつかの受け入れ基準、プログラム制限、指定された基準と制約を持つ Branching Programing の最小サイズの表記法、および多項式の複雑性を許可することによって定義される分類である。入力 $\sigma \in \{0,1\}^n$ の受け入れ基準は $G_\sigma$ の $s-t$ 個の経路の数に関連している。

Accepting Criteria	Restriction on $BP$	Program size	Complexity Class
$1 \pmod{2}$	none	$\oplus BP(f)$	$\oplus \mathcal{L}$
$1 \pmod{m}$	none	$\bmod_m BP(f)$	$\bmod_m \mathcal{L}$
$\gt 0$	none	$NBP(f)$	$\mathcal{NL}$
$\gt 0$	$G$ undirected	$SBP(f)$	$\mathcal{SL}$
$\gt 0$	deterministic	$BP(f)$	$\mathcal{L}$

Figure 1: 複雑性クラスの違い

クラス $\mathcal{NL}$ , $\mathcal{SL}$ , $\mathcal{L}$ はそれぞれ非決定論的、対称、および決定論的対数空間と呼ばれる。 $\mathcal{L}$ が他の 4 つのクラス全てに含まれていること、そして $\mathcal{SL} \subseteq \mathcal{NL}$ は自明であり、他の自明でない関係は知られていない。 $\mathcal{SL}$ が $\oplus \mathcal{L}$ に含まれていることを後で証明する。正のリテラルのみが分岐プログラムのエッジにラベル付けすることを許すことにより定義された $\mathcal{NL}$ , $\mathcal{SL}$ および $\mathcal{L}$ の単調類似体 (monotone analogue) を $m\mathcal{NL}$ , $m\mathcal{SL}$ および $m\mathcal{L}$ で示す。

代数分岐プログラムの下限は知られていない。Neciprouk[11]は決定性分岐プログラムに対してΩ((n/ログn)2)の下限を与える方法を示した。Pudĺak[13]は、この方法が非決定性分岐プログラムに対してΩ(n 3/2/log n)形式の下限を与えることを観測した。ここでは、Pudl'akのアイデアが代数モデルに継承されていることがわかります。

変数set [n] の分割をk個の互いに素な部分集合Ai,i∈ [k] に固定する。i∈ [k] ごとに、ci (f) を、残りの変数をあらゆる可能な方法で定数に固定することによって得られる変数Ai上のfの別個の部分関数の数とする。

3 The basic model: Span Programs

4 Symmetric vs. Counting Logspace

5 Canonical Span Programs

6 Lower bounds on Span Programs

6.1 Affine dimension

6.2 A lower bound for Majority

7 Monotone Span Programs

Acknowledgements

We are very grateful to A. Razborov for his observations which lead us to a simpler proof of proposition 1. We are also grateful to P. Pudlák for helpful comments.

References

R. Aleluinas, R. M. Karp, R. J. Lipton, R. J. Lovász, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 218–223, 1979.
E. Allender. A note on the power of threshold circuts. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 580–584, 1989.
L. Babai, P. Pudlák, V. Rödl, and E. Szemeredi. Lower bounds in complexity of symmetric Boolean functions. Theoretical Computer Science, pages 313–323, 1988.
R. B. Boppana and M. Sipser. The complexity of finite functions. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, vol. A (Algorithms and Complexity), chapter 14, pages 757–804. Elsevier Science Publishers B.V. and The MIT Press, 1990.
G. Buntrock, C. Damm, H. Hertrampf, and C. Meinel. Structure and importance of the logspace-mod class. Math. Systems Theory, 25:223–237, 1992.
L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions. TCS, 43:43–58, 1986.
R. L. Graham and B. L. Rothchild and J. H. Spencer. Ramsey Theory Wiley-Interscience, 1980.
M. Grigni and M. Sipser. Monotone complexity. In M. Paterson, editor, Proceedings of LMS workshop on Boolean function complexity, Durham. Cambridge University Press, 1990.
M. Karchmer and A. Wigderson. Characterizing non-deterministic circuit size, To appear in STOC’93.
R. E. Krichevskii. Complexity of contact circuits realizing a function of logical algebra. Doklady of the Academy of Sciences of the USSR, 151(4):803–806 (in Russian), 1963. English translation in Soviet Physics Doklady 7:4, pages 770–772 (1964).
E. I. Nečiporuk. On a Boolean function. Doklady of the Academy of Sciences of the USSR, 169(4):765–766 (in Russian), 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999-1000.
C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI conference on Theoretical Computer Science, Lecture Notes in Computer Science, 145, pages 269–276, Berlin, 1983. Springer-Verlag.
P. Pudlák. Private communication.
P. Pudlák and V. Rödl. A combinatorial approach to complexity. Combinatorica, 12:221–226, 1992.
A. Razborov. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):598–607, 1987. English translation in 41:4, pages 333-338.
A. Razborov. On the method of approximation. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 167–176, 1989.
A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81–93, 1990.
A. Razborov. Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions. Mathematical Notes of the Academy of Sciences of the USSR, 48(6):79–91, 1990.
S. Rudich. Private communication.
A. Shamir. How to share a secret. CACM, 22:612–613, 1979.
R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 77–82, 1987.
S. Toda. On the computational power of $P$ $P$ and ⊕ $P$ . In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 514–519, 1989.
L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85–93, 1986.

翻訳抄

Span Program に関する 1993 年の論文。

M. Karchmer, A. Wigderson. On Span Programs, Proc. 8-th Annual Structure in Complexity Theory Conference, San Diego, California, 18-21 May 1993. IEEE Computer Society Press, pp. 102-111.