ECCC-Report TR10-056https://eccc.weizmann.ac.il/report/2010/056Comments and Revisions published for TR10-056en-usMon, 22 Nov 2010 11:37:37 +0200
Revision 1
| Randomisation and Derandomisation in Descriptive Complexity Theory |
Kord Eickmeyer,
Martin Grohe
https://eccc.weizmann.ac.il/report/2010/056#revision1We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined from $\mathsf{PTIME}$.
Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, 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 $\mathsf{AC}^0$ 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 $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.
Mon, 22 Nov 2010 11:37:37 +0200https://eccc.weizmann.ac.il/report/2010/056#revision1
Paper TR10-056
| Randomisation and Derandomisation in Descriptive Complexity Theory |
Kord Eickmeyer,
Martin Grohe
https://eccc.weizmann.ac.il/report/2010/056We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined from $\mathsf{PTIME}$.
Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in $\mathsf{BPFO}$, the probabilistic version of first-order logic, but not in $\mathsf{C}^\omega_{\infty,\omega}$, 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 $\mathsf{AC}^0$ 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 $\mathsf{BPIFP+C}$, the probabilistic version of fixed-point logic with counting, captures the complexity class $\mathsf{BPP}$, even on unordered structures.
Thu, 01 Apr 2010 17:18:26 +0300https://eccc.weizmann.ac.il/report/2010/056