section_heading: Klase složenosti i usporedba s determinističkim Turingovim strojevima
paragraph_text: Ove su klase slične definicijama klasa P, PSPACE i EXPTIME, uzimajući u obzir resurse koje troši ATS za razliku od determinističkog Turingovog stroja. Chandra, Kozen, i Stockmeyer su dokazali sljedeće važne teoreme: