Search

• < Previous
• 1
• Next >

---

Randomisation and Derandomisation in Descriptive Complexity Theory

Kord Eickmeyer ; Martin Grohe.

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&nbsp;[&hellip;]

---

L-Recursion and a new Logic for Logarithmic Space

Martin Grohe ; Berit Grußien ; André Hernich ; Bastian Laubner.

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and&nbsp;[&hellip;]

---