The Complexity of Logarithmic Space Bounded Counting Classes
It provides a comprehensive textbook for researchers and students in computational complexity theory, focusing on foundational results in logarithmic-space counting classes.
The monograph tackles the study of complexity classes defined by logarithmic-space bounded non-deterministic Turing machines, presenting key results like the Immerman-Szelepcsenyi Theorem and theorems on the determinant, but does not report new experimental or numerical outcomes.
In this monograph, we study complexity classes that are defined using $O(\log n)$-space bounded non-deterministic Turing machines. We prove salient results of Computational Complexity in this topic such as the Immerman-Szelepcsenyi Theorem, the Isolating Lemma, theorems of Meena Mahajan and V. Vinay on the determinant and many consequences of these very important results. The manuscript is intended to be a comprehensive textbook on the topic of The Complexity of Logarithmic Space Bounded Counting Classes.