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 TheoryArticle

Authors: Kord Eickmeyer ORCID; Martin Grohe ORCID

    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
    Imported on: November 17, 2010
    Keywords: Computer Science - Logic in Computer Science,F.4.1, F.1.2

    Consultation statistics

    This page has been seen 2338 times.
    This article's PDF has been downloaded 454 times.