15
$\begingroup$

$\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, 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). 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).

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$ Dec 17, 2010 at 1:08
  • 1
    $\begingroup$ @Robin: as always thanks a lot :). I missed it. $\endgroup$
    – Kaveh
    Dec 17, 2010 at 4:52
  • $\begingroup$ $\mathsf{AltTime}(O(1),O(\log n)) = \mathsf{AC^0}$. The classes are probably something around polynomial size clause/term/CNF/DNF. $\endgroup$
    – Kaveh
    Nov 11, 2011 at 20:34
  • $\begingroup$ 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? $\endgroup$ Nov 30, 2012 at 18:49
  • $\begingroup$ @Robin, no, I don't know the answer, but I suspect that they probably don't correspond to nice circuit complexity classes. $\endgroup$
    – Kaveh
    Dec 4, 2012 at 6:52

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
-11
$\begingroup$

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.

$\endgroup$
3
  • 6
    $\begingroup$ -1: I don't see how this is relevant to the OP's question. $\endgroup$ Dec 17, 2010 at 1:10
  • 5
    $\begingroup$ 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? $\endgroup$ Dec 17, 2010 at 3:22
  • 6
    $\begingroup$ 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. $\endgroup$ Dec 17, 2010 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.