期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic we introduce a new logic \mathsfBP, bounded error probabilistic , which is defined from in a similar way as the
complexity class \mathsfBPP, bounded error probabilistic polynomial time, is defined from \mathsfPTIME.
Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in \mathsfBPFO, the probabilistic version of first-order logic, but not in \mathsfC, 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. We prove similar results for ordered structures and structures with an addition relation, showing that
certain uniform variants of \mathsfAC0 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 \mathsfBPIFP+C, the probabilistic version of fixed-point logic with counting, captures the complexity class \mathsfBPP, even on unordered structures.
