We define the sharply bounded hierarchy, SBHQL, a hierarchy of classes within P, using quasilinear-time computation and quantification over values of length log n. It generalizes the limited nondeterminism hierarchy introduced by Buss and Goldsmith, while retaining the invariance properties. The new hierarchy has several alternative characterizations. We define both ... more >>>

In this paper, we address the problem of evaluating the Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over the set of natural numbers. The problem is a natural extension to the integer expression by Stockmeyer and Mayer, and is also studied by Mckenzie, Vollmer and Wagner in their ``Polynomial ... more >>>

An almost complete set A for a complexity class C is a language of C which is not complete, but that has the property that ``many'' languages of C reduce to A, where the term ``many'' is used in reference to Lutz's resource bounded measure (rbm). The question of the ... more >>>

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>