We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any reference known?)?
$\begingroup$
$\endgroup$
1
-
5$\begingroup$ See the fairly recent paper Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. Logical Methods in Computer Science 7(3) (2011). According to the paper: "... probabilistic classes such as BPP have received very little attention in descriptive complexity theory yet ..." $\endgroup$– Marzio De BiasiJul 1, 2019 at 6:34
Add a comment
|