Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-056 | 22nd November 2010 11:37

Randomisation and Derandomisation in Descriptive Complexity Theory

RSS-Feed




Revision #1
Authors: Kord Eickmeyer, Martin Grohe
Accepted on: 22nd November 2010 11:37
Downloads: 3311
Keywords: 


Abstract:

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 from $\mathsf{PTIME}$.

Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that
certain uniform variants of $\mathsf{AC}^0$ bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes
can be derandomised.

Finally, we note that $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.



Changes to previous version:

Journal version including additional proofs.


Paper:

TR10-056 | 1st April 2010 09:54

Randomisation and Derandomisation in Descriptive Complexity Theory





TR10-056
Authors: Kord Eickmeyer, Martin Grohe
Publication: 1st April 2010 17:18
Downloads: 4073
Keywords: 


Abstract:

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 from $\mathsf{PTIME}$.

Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that
certain uniform variants of $\mathsf{AC}^0$ bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes
can be derandomised.

Finally, we note that $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.



ISSN 1433-8092 | Imprint