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 in 1976 (see References).

PropertyValue
dbpprop:abstract
  • 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 in 1976 (see References).
  • In der theoretischen Informatik ist eine alternierende Turing Maschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt. Erstere akzeptieren eine Eingabe wenn es eine mögliche Berechnung gibt die akzeptiert während zweitere nur akzeptieren wenn alle möglichen Berechnung akzeptieren.
  • 交替性チューリング機械（英: Alternating Turing Machine、ATM）は非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • 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 in 1976 (see References).
  • In der theoretischen Informatik ist eine alternierende Turing Maschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt. Erstere akzeptieren eine Eingabe wenn es eine mögliche Berechnung gibt die akzeptiert während zweitere nur akzeptieren wenn alle möglichen Berechnung akzeptieren.
  • 交替性チューリング機械（英: Alternating Turing Machine、ATM）は非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。
rdfs:label
  • Alternating Turing machine
  • Alternierende Turingmaschine
  • 交替性チューリング機械
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of