All reports by Author Martin Grohe:

__
TR10-056
| 1st April 2010
__

Kord Eickmeyer, Martin Grohe#### Randomisation and Derandomisation in Descriptive Complexity Theory

Revisions: 1

Kord Eickmeyer, Martin Grohe

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the

complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ...
more >>>