{"docId":714,"paperId":714,"url":"https:\/\/lmcs.episciences.org\/714","doi":"10.2168\/LMCS-7(3:14)2011","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":138,"name":"Volume 7, Issue 3"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"1107.3430","repositoryVersion":2,"repositoryLink":"https:\/\/arxiv.org\/abs\/1107.3430v2","dateSubmitted":"2010-11-17 00:00:00","dateAccepted":"2015-06-25 11:40:40","datePublished":"2011-09-21 00:00:00","titles":["Randomisation and Derandomisation in Descriptive Complexity Theory"],"authors":["Eickmeyer, Kord","Grohe, Martin"],"abstracts":["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."],"keywords":["Computer Science - Logic in Computer Science","F.4.1, F.1.2"]}