交替式图灵机
维基百科,自由的 encyclopedia
交替式图灵机(英语:Alternating Turing Machine, ATM)是计算复杂度理论中定义的一种非确定型图灵机(NTM)。与一般非确定型图灵机不同,交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer(英语:Larry Stockmeyer)于1976年提出。
交替式图灵机(英语:Alternating Turing Machine, ATM)是计算复杂度理论中定义的一种非确定型图灵机(NTM)。与一般非确定型图灵机不同,交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer(英语:Larry Stockmeyer)于1976年提出。