Randomisation and Derandomisation in Descriptive Complexity Theory

Details Randomisation and Derandomisation in Descriptive Complexity Theory Randomisation and Derandomisation in Descriptive Complexity Theory

2011-07-18

arxiv.org/abs/1107.3430v2

LMCS 7 (3:14) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(3:14)2011

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.

Affiliated with

Also associated with

No associations

Rating

Randomisation and Derandomisation in Descriptive Complexity Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomisation and Derandomisation in Descriptive Complexity Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomisation and Derandomisation in Descriptive Complexity Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-271578