Kord Eickmeyer ; Martin Grohe - Randomisation and Derandomisation in Descriptive Complexity Theory

lmcs:714 - Logical Methods in Computer Science, September 21, 2011, Volume 7, Issue 3 - https://doi.org/10.2168/LMCS-7(3:14)2011
Randomisation and Derandomisation in Descriptive Complexity Theory

Authors: Kord Eickmeyer ; Martin Grohe

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is defined from PTIME. Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in BPFO, the probabilistic version of first-order logic, but not in Cinf, 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. Similarly, we present a query on ordered structures which is definable in BPFO but not in monadic second-order logic, and a query on additive structures which is definable in BPFO but not in FO. The latter of these queries shows that certain uniform variants of AC0 (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 BPIFP+C, the probabilistic version of fixed-point logic with counting, captures the complexity class BPP, even on unordered structures.

Volume: Volume 7, Issue 3
Published on: September 21, 2011
Accepted on: June 25, 2015
Submitted on: November 17, 2010
Keywords: Computer Science - Logic in Computer Science,F.4.1, F.1.2


Consultation statistics

This page has been seen 1538 times.
This article's PDF has been downloaded 260 times.