Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

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

Lefteris Kirousis, Phokion G. Kolaitis

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