{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:11Z","timestamp":1753889771664,"version":"3.41.2"},"reference-count":39,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,9,21]],"date-time":"2011-09-21T00:00:00Z","timestamp":1316563200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:14)2011","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T13:45:24Z","timestamp":1415972724000},"source":"Crossref","is-referenced-by-count":0,"title":["Randomisation and Derandomisation in Descriptive Complexity Theory"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7942-1243","authenticated-orcid":false,"given":"Kord","family":"Eickmeyer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2011,9,21]]},"reference":[{"key":"10.2168\/LMCS-7(3:14)2011_abenor84","doi-asserted-by":"crossref","unstructured":"Miklos Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. InProceedings of the sixteenth annual ACM symposium on Theory of computing, STOC, pages 471-474, New York, NY, USA, 1984. ACM.","DOI":"10.1145\/800057.808715"},{"key":"10.2168\/LMCS-7(3:14)2011_ab09","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Boaz Barak.Computational Complexity. Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"issue":"3","key":"10.2168\/LMCS-7(3:14)2011_bis90","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"David A. Mix Barrington, Neil Immerman,","year":"1990","journal-title":"J. Comput. Syst. Sci."},{"key":"10.2168\/LMCS-7(3:14)2011_barfef85","unstructured":"J. Barwise and S. Feferman, editors.Model Theoretic Logics. Perspectives in Mathematical Logic. Springer-Verlage, 1985."},{"key":"10.2168\/LMCS-7(3:14)2011_bl06","unstructured":"Christoph Behle and Klaus-J\u00f6rn Lange. FO[<]-uniformity. InIEEE Conference on Computational Complexity, pages 183-189, 2006."},{"issue":"4","key":"10.2168\/LMCS-7(3:14)2011_cfi92","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai, M. F\u00fcrer, and N. Immerman","year":"1992","journal-title":"Combinatorica"},{"key":"10.2168\/LMCS-7(3:14)2011_dhk95","doi-asserted-by":"crossref","unstructured":"Anuj Dawar, Lauri Hella, and Phokion G. Kolaitis. Implicit definability and infinitary logic in finite model theory. InICALP, volume 944 ofLNCS, pages 624-635. Springer Verlag, 1995.","DOI":"10.1007\/3-540-60084-1_110"},{"key":"10.2168\/LMCS-7(3:14)2011_ebb85","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus. Extended logics: The general framework. In J. Barwise and S. Feferman, editors,Model-Theoretic Logics, pages 25-76. Springer-Verlag, 1985.","DOI":"10.1017\/9781316717158.005"},{"key":"10.2168\/LMCS-7(3:14)2011_ebbflu95","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum.Finite Model Theory. Perspectives in Mathematical Logic. Springer-Verlag, 2nd edition, 1999.","DOI":"10.1007\/3-540-28788-4"},{"key":"10.2168\/LMCS-7(3:14)2011_csl2011","unstructured":"Kord Eickmeyer. Non-definability results for random first-order logic. InComputer Science Logic, September 2011."},{"key":"10.2168\/LMCS-7(3:14)2011_fag74","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Richard M. Karp, editor,Complexity of Computation, volume 7 ofSIAM-AMS Proceedings, pages 43-73, 1974."},{"key":"10.2168\/LMCS-7(3:14)2011_fag76","doi-asserted-by":"crossref","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","journal-title":"Journal of Symbolic Logic"},{"key":"10.2168\/LMCS-7(3:14)2011_fellerI","unstructured":"W. Feller.An Introduction to Probability Theory and Its Aplications, volume I. John Wiley & Sons, 1957."},{"key":"10.2168\/LMCS-7(3:14)2011_gleetal69","first-page":"17","volume":"2","author":"Y.V. Glebskii, D.I. Kogan, et al.","year":"1969","journal-title":"Kibernetika"},{"key":"10.2168\/LMCS-7(3:14)2011_gklmsvvw07","unstructured":"E. Gr\u00e4del, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M.Y. Vardi, Y. Venema, and S. Weinstein.Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. Springer-Verlag, 2007."},{"key":"10.2168\/LMCS-7(3:14)2011_gur88","unstructured":"Y. Gurevich. Logic and the challenge of computer science. In E. B\u00f6rger, editor,Current trends in theoretical computer science, pages 1-57. Computer Science Press, 1988."},{"issue":"4","key":"10.2168\/LMCS-7(3:14)2011_hkl96","doi-asserted-by":"crossref","first-page":"422","DOI":"10.2307\/421173","volume":"2","author":"L. Hella, P.G. Kolaitis, and K. Luosto","year":"1996","journal-title":"The Bulletin of Symbolic Logic"},{"key":"10.2168\/LMCS-7(3:14)2011_imm86","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","journal-title":"Information and Control"},{"key":"10.2168\/LMCS-7(3:14)2011_imm99","doi-asserted-by":"crossref","unstructured":"N. Immerman.Descriptive Complexity Theory. Graduate Texts in Computer Science. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"10.2168\/LMCS-7(3:14)2011_impwid97","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. InProceedings of the 29th ACM Symposium on Theory of Computing, pages 220-229, 1997.","DOI":"10.1145\/258533.258590"},{"key":"10.2168\/LMCS-7(3:14)2011_impag06","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo. Can every randomized algorithm be derandomized? InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, STOC '06, pages 373-374, 2006.","DOI":"10.1145\/1132516.1132571"},{"key":"10.2168\/LMCS-7(3:14)2011_kay02","unstructured":"P. Kaye. A logical characterisation of the computational complexity class BPP. Technical report, University of Waterloo, 2002."},{"key":"10.2168\/LMCS-7(3:14)2011_kolvar92b","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. G. Kolaitis and M. Y. Vardi","year":"1992","journal-title":"Information and Computation"},{"issue":"4","key":"10.2168\/LMCS-7(3:14)2011_lau83","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","journal-title":"Information Processing Letters"},{"key":"10.2168\/LMCS-7(3:14)2011_lib04","doi-asserted-by":"crossref","unstructured":"L. Libkin.Elements of Finite Model Theory. Texts in Theoretical Computer Science. Spinger-Verlag, 2004.","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"3","key":"10.2168\/LMCS-7(3:14)2011_lyn82","doi-asserted-by":"crossref","first-page":"659","DOI":"10.2307\/2273595","volume":"47","author":"J.F. Lynch","year":"1982","journal-title":"Journal of Symbolic Logic"},{"key":"10.2168\/LMCS-7(3:14)2011_makowski04","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"10.2168\/LMCS-7(3:14)2011_mitmitsce98","doi-asserted-by":"crossref","unstructured":"J.C. Mitchell, M. Mitchell, and A. Scedrov. A linguistic characterization of bounded oracle computation and probabilistic polynomial time. InProceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 725-733, 1998.","DOI":"10.1109\/SFCS.1998.743523"},{"key":"10.2168\/LMCS-7(3:14)2011_motrag95","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan.Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"10.2168\/LMCS-7(3:14)2011_mueller08","unstructured":"M. M\u00fcller. Valiant-vazirani lemmata for various logics.Electronic Colloquium on Computational Complexity (ECCC), 15(063), 2008."},{"key":"10.2168\/LMCS-7(3:14)2011_niswid94","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan and A. Wigderson","year":"1994","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"10.2168\/LMCS-7(3:14)2011_nis91","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"Noam Nisan","year":"1991","journal-title":"Combinatorica"},{"key":"10.2168\/LMCS-7(3:14)2011_otto96","doi-asserted-by":"crossref","unstructured":"M. Otto.Bounded Variable Logics and Counting. Lecture Notes in Logic. Springer-Verlag, 1996.","DOI":"10.1007\/978-3-662-21676-7"},{"issue":"3","key":"10.2168\/LMCS-7(3:14)2011_res62","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1017\/S0022481200118742","volume":"27","author":"N. Rescher","year":"1962","journal-title":"Journal of Symbolic Logic"},{"issue":"2-3","key":"10.2168\/LMCS-7(3:14)2011_Schweikardt06","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.tcs.2005.10.025","volume":"350","author":"Nicole Schweikardt","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"10.2168\/LMCS-7(3:14)2011_sto77","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"10.2168\/LMCS-7(3:14)2011_tod91","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-7(3:14)2011_var82","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. The complexity of relational query languages. InProceedings of the 14th ACM Symposium on Theory of Computing, pages 137-146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"10.2168\/LMCS-7(3:14)2011_vio04","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"Emanuele Viola","year":"2004","journal-title":"Computational Complexity"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/714\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/714\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:03:24Z","timestamp":1747159404000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,21]]},"references-count":39,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:14)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1107.3430","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1107.3430","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,9,21]]},"article-number":"714"}}