DLOGTIME - DLOGTIME
Ve výpočetní složitosti teorie , DLOGTIME je třída složitosti všech výpočetních problémů řešitelných v logaritmické množství výpočetního času na deterministický Turing stroj . Musí to být definováno na Turingově stroji s náhodným přístupem , protože jinak je vstupní páska delší než rozsah buněk, ke kterým může stroj přistupovat. Jedná se o velmi slabý model časové složitosti: žádný Turingův stroj s náhodným přístupem s menší deterministickou časovou vazbou nemá přístup k celému vstupu.
Příklady
DLOGTIME zahrnuje problémy týkající se ověření délky vstupu, například problém „ Je vstup sudé délky? “, Který lze vyřešit v logaritmickém čase pomocí binárního vyhledávání .
Aplikace
DLOGTIME - uniformita je důležitá ve složitosti obvodu .