Back Màquina de Turing alternant Catalan Alternierende Turingmaschine German Máquina de Turing alternante Spanish ماشین تورینگ متناوب Persian Machine de Turing alternante French Alternirajući Turingov stroj Croatian 交替性チューリング機械 Japanese 교대 튜링 기계 Korean Máquina de Turing alternada Portuguese 交替式图灵机 Chinese
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (May 2011) |
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer[1] and independently by Kozen[2] in 1976, with a joint journal publication in 1981.[3]
- ^ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4.
- ^ Kozen, D. (1976). "On parallelism in Turing machines". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. hdl:1813/7056.
- ^ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation" (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. S2CID 238863413. Archived from the original (PDF) on April 12, 2016.