The Complexity of Logarithmic Space Bounded Counting Classes

TLDR

This monograph studies complexity classes that are defined using O(\log n)-space bounded non-deterministic Turing machines and proves salient results of Computational Complexity in this topic such as the Immerman-Szelepcs Theorem, the Isolating Lemma, theorems of Mahajan-Vinay on the determinant and many consequences.

摘要

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-Szelepcs $\rm\acute{e}$ nyi Theorem, the Isolating Lemma, theorems of Mahajan-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.