The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity ... more >>>

Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n+r(n) where r in o(n) is a sublinear function. It is shown that there exist infinite time ... more >>>

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality. Translator's note: This is a translation of the ... more >>>

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input $f$, one wants to decide whether $f$ satisfies the property or is `far' from satisfying the property. It has been shown that regular languages are testable, and that there exist context free ... more >>>