The Complexity of Logarithmic Space Bounded Counting Classes

Abstract

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.

Minors typos, errors in almost all the chapters have been corrected. Some figures have been redrawn. Main results in the last chapter have been checked for correctness and re-written to improve clarity and precision