DLOGTIME
Sign in to saveIn 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.
Article · 中文
在複雜度理論內，DLOGTIME是一個複雜度類，其問題可以用決定型圖靈機，在對數成長的時間內解決。這是使用決定型時間，所能定義出最小且非單純（non-trivial）的複雜度類。這類複雜度一定使用隨機存取圖靈機來定義，因為機器沒有足夠的時間來讀取整個輸入（輸入的大小，成長率是O(n)）。 DLOGTIME-均一性（uniformity）在電路複雜性裡面是很重要的。 詢問輸入字串的長度這個問題屬於DLOGTIME，因為我們可以對可能的輸入大小進行折半搜索演算法（binary search）。
Abstract from DBpedia / Wikipedia · CC BY-SA