<p>A version of NLOGTIME restricted such that the NTM (with input access by means of an index tape so that it can work in sublinear time) can only make one input query in each run, after which it halts immediately (the “Ruzzo convention”), is characterized by DLOGTIME-uniform polynomial-size disjunctions of literals. If you drop this restriction, NLOGTIME sits somewhere between the latter class and DLOGTIME-uniform polynomial-size DNF circuits with bottom fan-in <span class="math-container">$O(\log n)$</span>. This is the case <span class="math-container">$d=1$</span> of <a href="https://cstheory.stackexchange.com/a/36910">https://cstheory.stackexchange.com/a/36910</a>. (The Ruzzo convention is perhaps the right model for <span class="math-container">$d\ge2$</span>, but it is rather defective for <span class="math-container">$d=1$</span>, as it yields a nonuniversal model of computation.)</p>
<p>DLOGTIME languages are computable by DLOGTIME-uniform decision trees of <span class="math-container">$O(\log n)$</span> depth, but again, this is not an exact characterization, I suppose.</p>

CC BY-SA 4.0
2023-02-08T12:26:13.740Z
2023-02-08T13:13:22.143Z
2023-02-08T13:13:22.143Z
Emil Jeřábek
<p>I think it is far more interesting that the circuit complexity classes used by CS complexity theory make different predictions and use different metrics than those in the VLSI community.  From <a href="https://doi.org/10.1007/3-540-13331-3_55" rel="nofollow noreferrer">The VLSI complexity of Boolean functions</a>:</p>
<blockquote>
<p>It is well-known that all Boolean functions of <span class="math-container">$n$</span> variables can be computed by a logic circuit with <span class="math-container">$O(2^n/n)$</span> gates (Lupanov's theorem) and that there exist Boolean functions of n variables which require logic circuits of this size (Shannon's theorem). We present corresponding results for Boolean functions computed by VLSI circuits, using Thompson's model of a VLSI chip. We prove that all Boolean functions of <span class="math-container">$n$</span> variables can be computed by a VLSI circuit of <span class="math-container">$O(2^n)$</span> area and period 1, and we prove that there exist Boolean functions of <span class="math-container">$n$</span> variables for which every (convex) VLSI chip must have <span class="math-container">$\Omega(2^n)$</span> area.</p>
</blockquote>
<p>Interestingly, VLSI circuit complexity has a tendency to treat depth as &quot;irrelevant&quot; as there is one and only one &quot;depth&quot; that matters: the critical path.  For most practical purposes, an arbitrarily complex circuit can be treated as <span class="math-container">$O(1)$</span> with a latency of <span class="math-container">$n$</span>.</p>
<p>In fact, I'm not even sure that the concept of <span class="math-container">$DLogTime$</span> / <span class="math-container">$NLogTime$</span> directly translates in to VLSI circuit complexity.  Even Shannon's <span class="math-container">$2^n/n$</span> result does not readily translate: Shannon's results is valid <em>only</em> for a Boolean basis consisting of arity <span class="math-container">$\le2$</span> {AND, OR, NOT}.  This is not the only basis, and the number of &quot;gates&quot; needed drops dramatically as you allow more and more gate types.  The following are <span class="math-container">$area^2$</span> from a commercial VLSI standard cell library normalized to the size of a 2 input NAND gate:</p>
<pre>        2    3    4    &lt;- Arity
and    1.14 1.28 1.41
nand   1.00 1.14 1.28
or     1.14 1.41 1.41
nor    1.00 1.14 1.41
xor    1.62 2.44
xnor   1.62 2.44

buf    1.14
inv    0.80

aoi22  1.28
aoi222 1.62
aoi33  1.62
oai22  1.41
oai222 1.72
oai33  1.62

addf   2.64</pre>
<p>Specifically, note the <code>aoi</code> / <code>oai</code> gates which are <code>And Or Invert</code> / <code>Or And Invert</code> consisting of <em>arity</em> sized <em>first function</em> feeding the second function, where the number of <em>first function</em> gates is equal to the number of times <em>arity</em> appears.  For example, <code>aoi22</code> represents &quot;Two 2 input AND gates feeding a NOR gate&quot;.</p>
<p>My point is: Taken separately, a <code>oai222</code> function can be built using three 2 input OR gates and a 3 input NAND gate, for a total area of ~4.56, not including any area used for interconnect.  Yet this primitive can be realized in an area of just 1.72, which means a discrete manifestation of the same Boolean function consumes 2.65 times more area.</p>
<p>Also note that the area for an <span class="math-container">$n$</span> input {AND, NAND, OR, NOR, XOR, XNOR} gate, where <span class="math-container">$n\ge2$</span>, is much less than the area that it would take to build the same function using discrete 2 input gates.  Also note that while the area given for {XOR, XNOR} for this process is &quot;large&quot; relative to the other gates, there are other ways to build the same <span class="math-container">$n$</span> input gates using less area.</p>
<p>The propagation properties for the more complex primitives is also significantly better than what would be achieved using discrete gates.</p>
<p>Why is this important?  Because for me, at least, I've spent a simply enormous amount of time sifting through results from complexity theory that are built on a set of assumptions that has the effect of either rendering the result useless or wrong once the assumption is violated.  The following is from Steven Cooks <a href="https://web.archive.org/web/20130314011936/http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf" rel="nofollow noreferrer"><span class="math-container">$\mathcal{P}$</span> vs <span class="math-container">$\mathcal{NP}$</span></a>:</p>
<blockquote>
<p>Thus to prove <span class="math-container">$\mathcal{P} \ne \mathcal{NP}$</span> it suffices to prove a super-polynomial lower bound on the size of any family of Boolean circuits solving some specific <span class="math-container">$\mathcal{NP}$</span>-complete problem, such as 3-SAT. Back in 1949 Shannon proved that for almost all Boolean functions <span class="math-container">$f : \{0,1\}^n \to \{0,1\}$</span>, any Boolean circuit computing <span class="math-container">$f$</span> requires at least <span class="math-container">$2^n/n$</span> gates. Unfortunately, his counting argument gives no clue as to how to prove lower bounds for problems in <span class="math-container">$\mathcal{NP}$</span>.</p>
</blockquote>
<p>I find Cooks' reasoning curious.  Shannon's result is valid for all <span class="math-container">$f : \{0,1\}^n \to \{0,1\}$</span>, therefore if a <span class="math-container">$\mathcal{NP}$</span> problem can be described in <span class="math-container">$\{0,1\}^n$</span> bits, there must be a {AND, OR, NOT} basis circuit that can decide if it is satisfiable in ~<span class="math-container">$2^n/n$</span> gates (the actual paper gives a larger upper, but finite, bound for every possible function).  What this tells us is that anything that uses more than <span class="math-container">$n$</span> gates, where <span class="math-container">$n$</span> is the upper bound for the size of the <span class="math-container">$\mathcal{NP}$</span> problem, is using more gates than is required.  Using a larger, but complete, Boolean basis only reduces the number of gates required.  Using a different circuit complexity model, i.e. VLSI, gives even &quot;better&quot; result bounds.  Curious.  But we know for a fact that any solution to a <span class="math-container">$\mathcal{NP}$</span> problem that uses more than ~<span class="math-container">$2^n/n$</span> &quot;gates&quot; (where gates is used loosely for steps / operations) is doing so in a sub-optimal fashion... and there's an infinite number of ways to find a solution in a sub-optimal fashion.</p>
<p><a href="https://doi.org/10.1109/12.73590" rel="nofollow noreferrer">On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication</a> shows that predicting circuit complexity using a OBDD model over-estimates the actual circuit complexity:</p>
<blockquote>
<p>Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity <span class="math-container">$AT^2 = \Omega (n^2)$</span> also proves that any OBDD representation of the function has <span class="math-container">$\Omega(c^n)$</span> vertices for some <span class="math-container">$c&lt;1$</span> but that the converse is not true. There are functions for which any OBDD representation is of exponential size, but there is a VLSI implementation of complexity <span class="math-container">$AT^2 = O(n^{1+c})$</span>.</p>
<p>An integer multiplier for word size <span class="math-container">$n$</span> with outputs numbered 0 (least significant) through <span class="math-container">$2n-1$</span> (most significant) is described. For the Boolean function representing either output <span class="math-container">$i-1$</span> or output <span class="math-container">$2n-i-1$</span>, where <span class="math-container">$1\le i\le n$</span>, the following lower bounds are proved: any VLSI implementation must have <span class="math-container">$AT^2 = \Omega(i^2)$</span> and any OBDD representation must have <span class="math-container">$\Omega(1.09^i)$</span> vertices.</p>
</blockquote>

CC BY-SA 2.5
2010-12-17T01:10:19.390Z
-1: I don't see how this is relevant to the OP's question.
Robin Kothari
CC BY-SA 2.5
2010-12-17T03:22:54.200Z
Your bit in the middle about Shannon and Cook doesn't seem to make any sense. Shannon showed that "most" functions require an exponentially large circuit. How can we conclude that any NP problem only requires a linear sized family? And you do realize that we are talking about families of circuits, right?
Mark Reitblatt
CC BY-SA 2.5
2010-12-17T06:35:51.323Z
johne: this is not an appropriate forum for what can only be described as rants about the VLSI community vis-a-vis the CS community.
Suresh Venkat
CC BY-SA 4.0
2010-12-17T01:01:42.990Z
2023-02-08T11:44:47.867Z
2023-02-08T11:44:47.867Z
johne
<p>$\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).</p>

<p>After reading this <a href="https://cstheory.stackexchange.com/q/3743/186">question</a>, I become interested to see if the separation between these two classes is known, and in fact it is easy to separate them since $OR(x_1,...,x_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$ (thanks to Robin Kothari. See also <a href="http://dx.doi.org/10.1016/S0304-3975(96)00288-5" rel="nofollow noreferrer">known</a>). Now I am interested to know their corresponding circuit complexity characterization. I have searched a little bit and have asked a few people but was not able to find the answer.</p>

<blockquote>
  <p>Do we have nice circuit complexity characterizations for complexity classes $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$?</p>
</blockquote>

<p>Note: $\mathsf{DLogTime}$ shows up a lot in defining uniformity for small complexity classes. Note that the small time bound does not allow these machines to read the whole input, they can only read $\lg n$ bits from the input, and the classes are defined using machines that can write the address of a bit and then read that bit directly (i.e. don't need to go over all previous bits to reach there).</p>

CC BY-SA 2.5
2010-12-17T01:08:49.517Z
It is easy to separate the two classes. NLOGTIME can compute the OR function, whereas DLOGTIME cannot, because it can't read the entire input. This fact can be used to construct a language that separates the two using standard tricks.
Robin Kothari
CC BY-SA 2.5
2010-12-17T04:52:33.147Z
@Robin: as always thanks a lot :). I missed it.
Kaveh
CC BY-SA 3.0
2011-11-11T20:34:21.647Z
$\mathsf{AltTime}(O(1),O(\log n)) = \mathsf{AC^0}$. The classes are probably something around polynomial size clause/term/CNF/DNF.
Kaveh
CC BY-SA 3.0
2012-11-30T18:49:23.880Z
Did you finally find an answer to this question? A circuit characterization for DLOGTIME would have two parts, the kind of circuits allowed and the uniformity condition imposed on them. Do you know the answer to one of these?
Robin Kothari
CC BY-SA 3.0
2012-12-04T06:52:29.623Z
@Robin, no, I don't know the answer, but I suspect that they probably don't correspond to nice circuit complexity classes.
Kaveh
CC BY-SA 3.0
2012-12-04T15:24:43.613Z
Does logarithmic sized circuits define some reasonable complexity class (possibly DLOGTIME)? I don't know what uniformity condition to use. Perhaps log size circuits with DLOGTIME uniformity?
Robin Kothari
CC BY-SA 3.0
2012-12-04T21:05:14.807Z
@Robin, is it clear that $\mathsf{DLogTime} \subseteq \mathsf{Size}(\lg n)$? It seems to me that if we use something like Cook-Levin to get the circuits we will have circuits of size $\omega(\lg n)$. For uniformity, I guess $\mathsf{DLogTime}$ should be fine.
Kaveh
CC BY-SA 3.0
2012-12-04T21:21:15.353Z
I see what you mean. Maybe polylog sized circuits might define deterministic polylogarithmic time? I also remember something like NLOGTIME is contained in depth-2 polysize circuits where the first layer has AND gates of logarithmic fanin and the second layer has a single OR gate of polynomial fanin.
Robin Kothari
<cc.complexity-theory><circuit-complexity>
Circuit Complexity Charaterization for DLogTime and NLogTime
Kaveh
# Circuit Complexity Charaterization for DLogTime and NLogTime

(Asked by: username_0 on 2010-12-16)

$\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).

After reading this [question](https://cstheory.stackexchange.com/q/3743/186), I become interested to see if the separation between these two classes is known, and in fact it is easy to separate them since $OR(x\_1,...,x\_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$ (thanks to Robin Kothari. See also [known](http://dx.doi.org/10.1016/S0304-3975(96)00288-5)). Now I am interested to know their corresponding circuit complexity characterization. I have searched a little bit and have asked a few people but was not able to find the answer.

> Do we have nice circuit complexity characterizations for complexity classes $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$?

Note: $\mathsf{DLogTime}$ shows up a lot in defining uniformity for small complexity classes. Note that the small time bound does not allow these machines to read the whole input, they can only read $\lg n$ bits from the input, and the classes are defined using machines that can write the address of a bit and then read that bit directly (i.e. don't need to go over all previous bits to reach there).

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: It is easy to separate the two classes. NLOGTIME can compute the OR function, whereas DLOGTIME cannot, because it can't read the entire input. This fact can be used to construct a language that separates the two using standard tricks.  
> **username_0**: @Robin: as always thanks a lot :). I missed it.  
> **username_0**: $\mathsf{AltTime}(O(1),O(\log n)) = \mathsf{AC^0}$. The classes are probably something around polynomial size clause/term/CNF/DNF.  
> **username_1**: Did you finally find an answer to this question? A circuit characterization for DLOGTIME would have two parts, the kind of circuits allowed and the uniformity condition imposed on them. Do you know the answer to one of these?  
> **username_0**: @Robin, no, I don't know the answer, but I suspect that they probably don't correspond to nice circuit complexity classes.  
> **username_1**: Does logarithmic sized circuits define some reasonable complexity class (possibly DLOGTIME)? I don't know what uniformity condition to use. Perhaps log size circuits with DLOGTIME uniformity?  
> **username_0**: @Robin, is it clear that $\mathsf{DLogTime} \subseteq \mathsf{Size}(\lg n)$? It seems to me that if we use something like Cook-Levin to get the circuits we will have circuits of size $\omega(\lg n)$. For uniformity, I guess $\mathsf{DLogTime}$ should be fine.  
> **username_1**: I see what you mean. Maybe polylog sized circuits might define deterministic polylogarithmic time? I also remember something like NLOGTIME is contained in depth-2 polysize circuits where the first layer has AND gates of logarithmic fanin and the second layer has a single OR gate of polynomial fanin.  

---

## 2 answers

### Answer by username_2 on 2023-02-08. Score: 3

A version of NLOGTIME restricted such that the NTM (with input access by means of an index tape so that it can work in sublinear time) can only make one input query in each run, after which it halts immediately (the “Ruzzo convention”), is characterized by DLOGTIME-uniform polynomial-size disjunctions of literals. If you drop this restriction, NLOGTIME sits somewhere between the latter class and DLOGTIME-uniform polynomial-size DNF circuits with bottom fan-in $O(\log n)$. This is the case $d=1$ of <https://cstheory.stackexchange.com/a/36910>. (The Ruzzo convention is perhaps the right model for $d\ge2$, but it is rather defective for $d=1$, as it yields a nonuniversal model of computation.)

DLOGTIME languages are computable by DLOGTIME-uniform decision trees of $O(\log n)$ depth, but again, this is not an exact characterization, I suppose.


---

### Answer by username_3 on 2010-12-17. Score: -11

I think it is far more interesting that the circuit complexity classes used by CS complexity theory make different predictions and use different metrics than those in the VLSI community.  From The VLSI complexity of Boolean functions:

It is well-known that all Boolean functions of $n$ variables can be computed by a logic circuit with $O(2^n/n)$ gates (Lupanov's theorem) and that there exist Boolean functions of n variables which require logic circuits of this size (Shannon's theorem). We present corresponding results for Boolean functions computed by VLSI circuits, using Thompson's model of a VLSI chip. We prove that all Boolean functions of $n$ variables can be computed by a VLSI circuit of $O(2^n)$ area and period 1, and we prove that there exist Boolean functions of $n$ variables for which every (convex) VLSI chip must have $\Omega(2^n)$ area.

Interestingly, VLSI circuit complexity has a tendency to treat depth as "irrelevant" as there is one and only one "depth" that matters: the critical path.  For most practical purposes, an arbitrarily complex circuit can be treated as $O(1)$ with a latency of $n$.
In fact, I'm not even sure that the concept of $DLogTime$ / $NLogTime$ directly translates in to VLSI circuit complexity.  Even Shannon's $2^n/n$ result does not readily translate: Shannon's results is valid only for a Boolean basis consisting of arity $\le2$ {AND, OR, NOT}.  This is not the only basis, and the number of "gates" needed drops dramatically as you allow more and more gate types.  The following are $area^2$ from a commercial VLSI standard cell library normalized to the size of a 2 input NAND gate:
        2    3    4    <- Arity
and    1.14 1.28 1.41
nand   1.00 1.14 1.28
or     1.14 1.41 1.41
nor    1.00 1.14 1.41
xor    1.62 2.44
xnor   1.62 2.44

buf    1.14
inv    0.80

aoi22  1.28
aoi222 1.62
aoi33  1.62
oai22  1.41
oai222 1.72
oai33  1.62

addf   2.64
Specifically, note the aoi / oai gates which are And Or Invert / Or And Invert consisting of arity sized first function feeding the second function, where the number of first function gates is equal to the number of times arity appears.  For example, aoi22 represents "Two 2 input AND gates feeding a NOR gate".
My point is: Taken separately, a oai222 function can be built using three 2 input OR gates and a 3 input NAND gate, for a total area of ~4.56, not including any area used for interconnect.  Yet this primitive can be realized in an area of just 1.72, which means a discrete manifestation of the same Boolean function consumes 2.65 times more area.
Also note that the area for an $n$ input {AND, NAND, OR, NOR, XOR, XNOR} gate, where $n\ge2$, is much less than the area that it would take to build the same function using discrete 2 input gates.  Also note that while the area given for {XOR, XNOR} for this process is "large" relative to the other gates, there are other ways to build the same $n$ input gates using less area.
The propagation properties for the more complex primitives is also significantly better than what would be achieved using discrete gates.
Why is this important?  Because for me, at least, I've spent a simply enormous amount of time sifting through results from complexity theory that are built on a set of assumptions that has the effect of either rendering the result useless or wrong once the assumption is violated.  The following is from Steven Cooks $\mathcal{P}$ vs $\mathcal{NP}$:

Thus to prove $\mathcal{P} \ne \mathcal{NP}$ it suffices to prove a super-polynomial lower bound on the size of any family of Boolean circuits solving some specific $\mathcal{NP}$-complete problem, such as 3-SAT. Back in 1949 Shannon proved that for almost all Boolean functions $f : \{0,1\}^n \to \{0,1\}$, any Boolean circuit computing $f$ requires at least $2^n/n$ gates. Unfortunately, his counting argument gives no clue as to how to prove lower bounds for problems in $\mathcal{NP}$.

I find Cooks' reasoning curious.  Shannon's result is valid for all $f : \{0,1\}^n \to \{0,1\}$, therefore if a $\mathcal{NP}$ problem can be described in $\{0,1\}^n$ bits, there must be a {AND, OR, NOT} basis circuit that can decide if it is satisfiable in ~$2^n/n$ gates (the actual paper gives a larger upper, but finite, bound for every possible function).  What this tells us is that anything that uses more than $n$ gates, where $n$ is the upper bound for the size of the $\mathcal{NP}$ problem, is using more gates than is required.  Using a larger, but complete, Boolean basis only reduces the number of gates required.  Using a different circuit complexity model, i.e. VLSI, gives even "better" result bounds.  Curious.  But we know for a fact that any solution to a $\mathcal{NP}$ problem that uses more than ~$2^n/n$ "gates" (where gates is used loosely for steps / operations) is doing so in a sub-optimal fashion... and there's an infinite number of ways to find a solution in a sub-optimal fashion.
On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication shows that predicting circuit complexity using a OBDD model over-estimates the actual circuit complexity:

Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity $AT^2 = \Omega (n^2)$ also proves that any OBDD representation of the function has $\Omega(c^n)$ vertices for some $c<1$ but that the converse is not true. There are functions for which any OBDD representation is of exponential size, but there is a VLSI implementation of complexity $AT^2 = O(n^{1+c})$.
An integer multiplier for word size $n$ with outputs numbered 0 (least significant) through $2n-1$ (most significant) is described. For the Boolean function representing either output $i-1$ or output $2n-i-1$, where $1\le i\le n$, the following lower bounds are proved: any VLSI implementation must have $AT^2 = \Omega(i^2)$ and any OBDD representation must have $\Omega(1.09^i)$ vertices.

> **Comments:**
> **username_1**: -1: I don't see how this is relevant to the OP's question.  
> **username_4**: Your bit in the middle about Shannon and Cook doesn't seem to make any sense. Shannon showed that "most" functions require an exponentially large circuit. How can we conclude that any NP problem only requires a linear sized family? And you do realize that we are talking about families of circuits, right?  
> **username_5**: johne: this is not an appropriate forum for what can only be described as rants about the VLSI community vis-a-vis the CS community.  

---

