Vrijeme računanja

U računskoj teoriji složenosti, vrijeme računanja je mjera za broj koraka koje koristi neki apstraktni stroj u pojedinom računanju. Za bilo koji dani model apstraktnog stroja, vrijeme računanja korišteno od strane tog apstraktnog stroja je računski resurs koji može biti korišten za rješavanje računskog problema. Mnoge su važne klase složenosti definirane određenom količinom vremena računanja na određenom apstraktnom stroju. Ove vremenske klase dijele mnoge zajedničke značajke, ali njihovi međusobni odnosi, kao i odnosi sa drugim klasama složenosti za druge resurse, još uvijek nisu većim dijelom shvaćene.

Najuobičajeniji model apstraktnog stroja korištenog za brojanje vremena računanja je Turingov stroj. Bilo koji apstraktni stroj sličan Turingovom stroju posjeduje upravljačku jedinku, i glava iznad trake za čitanje i pisanje može mjeriti računsko vrijeme, u terminima broja koraka upravljačke jedinke i glave. Stoga se za različite apstraktne modele mogu definirati različiti apstraktni resursi: determinističko vrijeme za deterministički Turingov stroj, nedeterminističko vrijeme za nedeterministički Turingov stroj, kvantno vrijeme za kvantni Turingov stroj, itd. Vrijeme računanja za ulaz je jednako dubini stabla računanja na tom ulazu.

Mjere vremena računanja zadovoljavaju teorem o vremenskoj hijerarhiji, što znači da će asimptotski veće količine vremena računanja uvijek dopustiti računanje strogo većih klasa složenosti.