Randomisation and derandomisation in descriptive complexity theory

DOI10.1007/978-3-642-15205-4_23MaRDI QIDQ5901153zbMATH OpenOpenAlexFDO

Publication date 3 September 2010

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.3430

Descriptive complexity and finite models (68Q19)

Abstract: 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.

Recommendations

Cited in

(9)

This page was built for publication: Randomisation and derandomisation in descriptive complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901153)