eng
episciences.org
Logical Methods in Computer Science
1860-5974
2011-09-21
Volume 7, Issue 3
10.2168/LMCS-7(3:14)2011
714
journal article
Randomisation and Derandomisation in Descriptive Complexity Theory
Kord Eickmeyer
https://orcid.org/0000-0001-7942-1243
Martin Grohe
https://orcid.org/0000-0002-0292-9142
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.
https://lmcs.episciences.org/714/pdf
Computer Science - Logic in Computer Science
F.4.1, F.1.2