{
  "id": "dlogtime-593031-8b77f035411ad5f1",
  "slug": "dlogtime",
  "title": "DLOGTIME",
  "qid": "Q5205561",
  "lead": "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. DLOGTIME machines are rarely used as-is. Instead, they are usually used as part of a theoretical construct for studying reducibility. They cannot be used to produce output that is longer than logarithmic length. However, they can be used to indirectly produce such an output, in the following sense: Given any log-length binary address, it produces the corresponding bit of the output. Since a polynomial-sized integer has logarithmic-length binary representation, this is possible in DLOGTIME.",
  "body": "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. DLOGTIME machines are rarely used as-is. Instead, they are usually used as part of a theoretical construct for studying reducibility. They cannot be used to produce output that is longer than logarithmic length. However, they can be used to indirectly produce such an output, in the following sense: Given any log-length binary address, it produces the corresponding bit of the output. Since a polynomial-sized integer has logarithmic-length binary representation, this is possible in DLOGTIME. ==Examples== DLOGTIME can solve some problems relating to verifying the length of the input, such as \"Is the input of even length?\", which can be solved in logarithmic time using binary search. More generally, for any p \\geq 1 and integer k , it can decide if |x| \\equiv k \\mod p . It does so by first converting |x| to its binary representation on the work tape, using binary search, then going through the binary representation bit by bit, keeping track of its mod-p status using the lookup table stored in the Turing machine's state-transition table. The family of DLOGTIME-decidable problems is closed under finite union, finite intersection, and negation. L_f=\\left\\{\\langle x, i, c\\rangle \\mid f(x)_i=c\\right\\} is DLOGTIME-decidable. This allows definition of DLOGTIME-computation of Boolean circuit families. Note: Because DLOGTIME machine only has enough time to check O(\\log n) \\ll n entries in the input, we usually must restrict the input to the function f to only unary input. That is, the input to the function can only be \\epsilon, 1, 11, 111, \\dots , to avoid trivial failures. ==Circuit complexity== DLOGTIME-uniformity is used in circuit complexity. A Boolean circuit family C_0, C_1, \\dots is DLOGTIME-uniform iff the function 1^n \\mapsto desc(C_n) is implicitly DLOGTIME computable, where desc(C_n) is a description of the circuit. It is very weak in the following sense: \\mathsf{AC}^0_0 \\subsetneq \\mathsf{DLOGTIME} \\subsetneq \\mathsf{AC}^0_2 , where AC consists of DLOGTIME-uniform unlimited fan-in circuits of depth between 0 and 2. Also, \\mathsf{DLOGTIME} is not comparable with \\mathsf{AC}^0_1 , meaning that neither one of them contains the other (XOR is in DLOGTIME, AND and OR are in \\mathsf{AC}^0_1 ). The assumption of DLOGTIME-uniformity is important, since otherwise even a \\mathsf{AC}^0_0 circuit family may encode a non-computable sequence in the choice of their indices. To show \\mathsf{DLOGTIME} \\subset \\mathsf{AC}^0_2 , note that the machine can perform only O( \\log n) random-access reads, each returning one input bit. Call the transcript of such a computation the ordered list \\left(\\left(p_1, b_1\\right), \\ldots,\\left(p_{c \\log n}, b_{c \\log n}\\right)\\right) of the positions it probes and the bits it observes. Since each p_t is determined by the previously read bits, there are only 2^{c\\log n} = \\mathsf{poly}(n) possible transcripts. For each accepting transcript, build an AND gate that checks exactly those c \\log n literals \\mapsto \"position p_j contains bit \\mathrm{b}_j \". Wire all these gates into one big OR. That yields a \\mathsf{AC}_2^0 circuit. It is clear, by construction, that this construction is \\mathsf{DLOGTIME} -uniform. ==References==",
  "categories": [
    "23057298"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1333819509",
  "content_hash": "8b77f035411ad5f1bb07c3bdbd9116e788ec4515cb7a62e06f2d1c76a826964d",
  "created_at": 1792311280.98725,
  "updated_at": 1768859786.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "dlogtime-593031-8b77f035411ad5f1",
    "type": "webpage",
    "title": "DLOGTIME",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/dlogtime",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:dlogtime-593031-8b77f035411ad5f1",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1333819509",
    "note": "Immutable snapshot dlogtime-593031-8b77f035411ad5f1, content root 8b77f035411ad5f1…"
  }
}