Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with computational and structural complexity:
TR97-029 | 20th August 1997
Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

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 ... more >>>

TR00-082 | 17th August 2000
Lefteris Kirousis, Phokion G. Kolaitis

The Complexity of Minimal Satisfiability Problems

Revisions: 2

A dichotomy theorem for a class of decision problems is
a result asserting that certain problems in the class
are solvable in polynomial time, while the rest are NP-complete.
The first remarkable such dichotomy theorem was proved by
T.J. Schaefer in 1978. It concerns the ... more >>>

ISSN 1433-8092 | Imprint