DLOGTIME
id:
dlogtime-275-18426282
title:
DLOGTIME
text:
In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since otherwise the input tape is longer than the range of cells that can be accessed by the machine. It is a very weak model of time complexity: no random-access Turing machine with a smaller deterministic time bound can access the whole input.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/DLOGTIME
date created:
date modified:
2021-05-28T12:27:45Z
main entity:
{"identifier":"Q5205561","url":"https://www.wikidata.org/entity/Q5205561"}
image:
fields total:
13
integrity:
13