section_heading: Stroj sa k alternacija
paragraph_text: Na primjer, razmatranjem problema minimizacije kruga - za dani krug A koji računa bulovsku funkciju f i broj n, odredi postoji li krug s najviše n vrata koji računa istu funkciju f. Alternirajući Turingov stroj s jednom alternacijom, počinjući u egzistencijalnom stanju, može riješiti problem u polinomnom vremenu (pogađanjem kruga B s najviše n stanja, i tada skačući u univerzalno stanje, pogađajući ulaz, i provjeravajući da izlaz od B za taj ulaz odgovara izlazu od A na tom ulazu).