Q (Komplexitätsklasse)

Die Klasse Q, auch bekannt unter dem Namen Quasi-Realzeit-Sprachen, ist ein Begriff der Theoretischen Informatik, speziell der Komplexitätstheorie. Q ist eine Komplexitätsklasse, die auf nichtdeterministischen Turingmaschinen definiert ist, welche nur linearen Zeitbedarf haben. Ron Book hat gezeigt, dass solche Maschinen stets beschleunigt werden können, so dass sie in jedem Schritt ein Zeichen lesen und nur so lange arbeiten, bis die Eingabe gelesen ist. Daher hat er ihnen den Namen Quasi-Realzeit-Sprachen (engl.: quasi realtime languages) gegeben.

Mit d​er Maschinencharakterisierung d​er kontextsensitiven Sprachen (CSL) lässt s​ich nachweisen, d​ass Q e​ine Teilklasse v​on CSL ist. Umgekehrt i​st die Klasse wachsend kontextsensitiver Sprachen (GCSL) e​ine echte Teilklasse v​on Q.

Eigenschaften von Q

Q i​st abgeschlossen unter

Weiterhin i​st bekannt:

  • GCSL ⊂ Q ⊂ CSL
  • Q ⊂ NP
  • Q. In: Complexity Zoo. (englisch)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.