10.2168/LMCS-7(3:14)2011
https://lmcs.episciences.org/714
Eickmeyer, Kord
Kord
Eickmeyer
0000-0001-7942-1243
Grohe, Martin
Martin
Grohe
0000-0002-0292-9142
Randomisation and Derandomisation in Descriptive Complexity Theory
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.
episciences.org
Computer Science - Logic in Computer Science
F.4.1, F.1.2
arXiv.org - Non-exclusive license to distribute
2015-06-25
2011-09-21
2011-09-21
eng
journal article
arXiv:1107.3430
10.48550/arXiv.1107.3430
1860-5974
https://lmcs.episciences.org/714/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 7, Issue 3
Researchers
Students