The Complexity of Logarithmic Space Bounded Counting Classes

##plugins.pubIds.doi.readerDisplayName## https://doi.org/10.70593/978-93-7185-647-8

Authors

T. C. Vijayaraghavan
Vels Institute of Science, Technology & Advanced Studies, (Vistas), Velan Nagar, P. V. Vaithiyalingam Road, Pallavaram, Chennai-600117, Tamil Nadu, India

Keywords:

Logarithmic Space, Turing machine, Probabilistic Logarithmic space, Boolean circuits, Turing reductions

Synopsis

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 M. 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.

References

Richard Beigel, Nick Reingold and Daniel Spielman. PP is Closed under Intersection, Journal of Computer and System Sciences, 50: 191-202, 1995.

Chris Bourke, Raghunath Tewari and N. V. Vinodchandran. Directed Planar Reachability Is in Unambiguous Log-Space, ACM Transactions on Computation Theory, Vol. 1, No. 1, Article 4, 2009.

Andrew Chiu, George Davida and Bruce Litow. Division in logspace-uniform NC1. RAIRO-Theoretical Informatics and Applications, 35:259-276, 2001.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Fourth edition. MIT Press, 2022.

Stephen A. Cook. A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control, 64(1-3):2-21, 1985.

Ding-Zhu Du and Ker-I Ko. Theory of Computational Complexity, Second Edition. John Wiley & Sons, 2014.

John D. Dixon and Brian Mortimer. Permutation Groups. Graduate Texts in Mathematics 163, 1996.

Lance Fortnow. Counting Complexity, In Complexity Theory Retrospective II, editors Lane A. Hemaspaandra and Alan Selman, pp. 81-107, Springer, 1997.

Downloads

Book Preview

Published

9 December 2025
Copyright (c) 2025 T. C. Vijayaraghavan

Details about the available publication format: E-Book

E-Book

ISBN-13 (15)

978-93-7185-647-8

Details about the available publication format: Book (Paperback)

Book (Paperback)

ISBN-13 (15)

978-93-7185-687-4

How to Cite

Vijayaraghavan, T. C. . (2025). The Complexity of Logarithmic Space Bounded Counting Classes. Deep Science Publishing. https://doi.org/10.70593/978-93-7185-647-8
Download Citation