Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Katsushi Inoue:

TR00-027 | 11th April 2000
Pavol Duris, Juraj Hromkovic, Katsushi Inoue

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

The investigation of the computational power of randomized computations
is one of the central tasks of current complexity and algorithm theory.
In this paper for the first time a "strong" separation between the power
of determinism, Las Vegas randomization, and nondeterminism for a compu-
ting model is proved. The computing ... more >>>

ISSN 1433-8092 | Imprint