Komputada tempo
En komputa komplikteorio, komputada tempo aŭ kalkulada tempo estas mezuro de tio kiel multaj paŝoj estas uzataj per iu abstrakta komputilo por kalkulado de donita komputa problemo. Por ĉiu donita modelo de abstrakta komputilo, la kalkulada tempo uzata per ĉi tiu abstrakta komputilo estas komputa rimedo kiu povas esti uzata por solvi la problemojn.
La plej komuna abstrakta komputilo uzata por konsidero de la kalkulada tempo estas la maŝino de Turing. Ĉi tia abstrakta komputilo havas regon de stato kaj kapon ĉe bendo, kaj la komputa tempo povas esti prenita kiel kvanto de paŝoj farataj per la rego de stato kaj la kapo.
Sur reala komputilo, komputada tempo havas eĉ pli realan sencon, ĝi povas esti konsiderata kiel tempo (mezurata ekzemple en sekundoj) bezonata por plenumi donitan taskon. Ankaŭ, pro tio ke plejparto de realaj komputiloj havas horloĝan generilon kun certa horloĝa frekvenco, la kalkulada tempo povas esti konsiderata kiel bezonata kvanto de periodoj de la frekvenco, kio estas fakte la kvanto de paŝoj farataj per la procesoro.
Multaj gravaj komplikecaj klasoj estas difinitaj kiel klasoj de problemoj bezonantaj certan kvanton de kalkulada tempo sur certa abstrakta komputilo.
Ĉi tiuj tempaj klasoj havas multajn komunajn karakterizojn, sed iliaj interrilatoj unu al la alia kaj al komplikecaj klasoj bazitaj sur la aliaj rimedoj, ekzemple la uzata memoro (spaca komplikeco), estas ankoraŭ de multaj flankoj nesciataj.
Por diversaj okazoj de determinismeco kaj nedeterminismeco, oni povas difini malsamajn komputajn rimedojn: determinisma tempo sur determinisma maŝino de Turing, nedeterminisma tempo sur nedeterminisma maŝino de Turing, kvantuma tempo sur kvantuma maŝino de Turing, kaj tiel plu.
La kalkulada tempo sur donita enigo estas egala al la profundo de la kalkulada arbo sur la enigo. Kalkulada tempo kontentigas tempajn hierarkiajn teoremojn, kiuj statas ke asimptote pli granda kvanto da kalkulada tempo ĉiam permesas kalkuli problemojn de severe pli grandaj komplikecaj klasoj.