
PreviousNext
In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.
For any Boolean function $f$ let $L(f)$ be its formula size
complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and
every $k\le n/2$, we describe a probabilistic distribution
on formulas in the basis $\{\land,\oplus,1\}$ in some given set of
$n$ variables and of the ...
more >>>
We consider the question of determining whether
a given object has a predetermined property or is ``far'' from any
object having the property.
Specifically, objects are modeled by functions,
and distance between functions is measured as the fraction
of the domain on which the functions differ.
We ...
more >>>
PreviousNext