並列計算論文

計算複雑性理論において、並列計算テーゼとは、（適切な）並列マシンが使用する時間は、逐次マシンが使用するスペースと多項式的に関係しているという仮説である。並列計算テーゼは、1976年にチャンドラとストックマイヤーによって提唱された。^[1]

言い換えれば、計算が分岐して制限なく並列に実行できる計算モデルの場合、長さnの入力に対してモデルの下で ステップ 以内で決定可能な形式言語は、ある定数kに対して 単位 以内のストレージを使用する非分岐マシンによって決定可能です。同様に、非分岐モデルのマシンが 単位 以内のストレージを使用して言語を決定する場合、並列モデルのマシンは、ある定数kに対して ステップ以内で言語を決定できます。 ${\displaystyle t(n)}$${\displaystyle t(n)^{k}}$${\displaystyle s(n)}$${\displaystyle s(n)^{k}}$

並列計算のテーゼは厳密な形式的記述ではない。なぜなら、許容可能な並列モデルを構成する要素が明確に定義されていないからである。並列マシンは、シーケンシャル空間に多項式的に関連する時間でシーケンシャルマシンをエミュレートできるほど強力でなければならない。チューリングマシン、非決定性チューリングマシン、および交代チューリングマシンを比較せよ。N. Blum (1983) は、このテーゼが成り立たないモデルを導入した。^[2] しかし、このモデルは、ステップの後に並列計算スレッドを許可している。(ビッグオー記法を参照) Parberry (1986) は、このテーゼを擁護して、より「合理的な」境界はまたはであると示唆した。^[3] Goldschlager (1982) は、このテーゼに従う、すべての「合理的な」並列モデルをエミュレートできるほど普遍的なモデルを提案した。^[4] チャンドラとストックマイヤーは、決定論的チューリングマシンと交代型チューリングマシンの命題に関連する結果を最初に形式化し、証明しました。これがこの命題の起源です。^[5]${\displaystyle 2^{2^{O(T(n))}}}$${\displaystyle T(n)}$${\displaystyle 2^{O(T(n))}}$${\displaystyle 2^{T(n)^{O(1)}}}$