交替性チューリング機械

ウィキペディア

交替性チューリング機械

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/06 00:17 UTC 版)

交替性チューリング機械（こうたいせいチューリングきかい、英: Alternating Turing Machine, ATM）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。