Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

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

1 Answer

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 Shannons $2^n/n$ result does not readily translate: Shannons 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. Shannons 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.

share|improve this answer
5  
-1: I don't see how this is relevant to the OP's question. –  Robin Kothari Dec 17 '10 at 1:10
5  
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 Dec 17 '10 at 3:22
6  
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 Dec 17 '10 at 6:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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