k回の交替のある機械
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/06 00:17 UTC 版)
「交替性チューリング機械」の記事における「k回の交替のある機械」の解説
k回の交替のある交替性チューリング機械とは、存在的状態から全称的状態への切り替え、あるいはその逆の切り替えが k 回以上発生しない交替性チューリング機械である。この場合、状態は k 個の集合に分割される。状態が偶数個の集合に分割されるなら、全体として全称的であり、奇数個なら存在的となる（あるいは逆。初期状態がどちらであるかに依存する）。集合 i に含まれる状態と、j < i であるような集合 j に含まれる状態との間に遷移は存在しない。 例として回路最小化問題を考える。あるブール関数 f を計算する回路 A と数 n があるとき、最大 n 個の論理ゲートで同じ関数 f を計算する回路が存在するかどうかを決定する問題である。1回の交替のある交替性チューリング機械で存在的状態から動作を開始する場合、この問題を多項式時間で解くことができる。最大 n ゲートの回路 B を想定し、全称状態に交替し、入力を想定し、B にその入力を与えたときの出力と A に同じ入力を与えたときの出力を比較する。 k回の交替のある交替性チューリング機械が存在的状態から動作開始する場合、クラス Σ k P {\displaystyle \Sigma _{k}{\rm {P}}} に属する問題を多項式時間で解くことができる（あるいは、全称的状態から動作開始する場合は、 Π k P {\displaystyle \Pi _{k}{\rm {P}}} ）。詳しくは多項式階層を参照されたい。
※この「k回の交替のある機械」の解説は、「交替性チューリング機械」の解説の一部です。
「k回の交替のある機械」を含む「交替性チューリング機械」の記事については、「交替性チューリング機械」の概要を参照ください。
- k回の交替のある機械のページへのリンク
