The Complexity of Logarithmic Space Bounded Counting Classes (Second Edition)

##plugins.pubIds.doi.readerDisplayName## https://doi.org/10.70593/978-93-7185-918-9

Authors

T. C. Vijayaraghavan

Keywords:

Structural Complexity, Computational Complexity, Counting Classes, Theory of Computation, Logarithmic Space

Synopsis

A logarithmic space bounded counting class is de ned based on the number of accepting and/or the number of rejecting computation paths of a NL-Turing machine. This monograph gives a nice in-depth exposition of logarithmic space bounded counting classes and many important results on them including their properties. A major portion of results shown by the author have not appeared in any textbook on computational complexity.
This textbook is intended to be an introductory material on logarithmic space bounded counting classes for advanced under-graduate students or graduate students and researchers who have prior knowledge of basics concepts in the Design and Analysis of Algorithms, Theory of Computation, Computational Complexity and Discrete Mathematics.

References

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and Grid Graph Reachability Problems. Theory of Computing Systems, 45: 675-723, 2009.

Eric Allender, Robert Beals and Mitsunori Ogihara. The complexity of matix rank and feasible systems of linear equations. Computational Complexity, 8:99–126, Birkhauser,1999.

Manindra Agrawal, Thanh Minh Hoang and Thomas Thierauf. The Polynomially Bounded Perfect Matching Problem Is in NC2. In STACS ’07: Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, LNCS 4393, pp. 489-499, Springer, 2007.

Carme A` lvarez and Birgit Jenner. A very hard log-space counting class. Theoretical Computer Science, 107(1):3-30, Elsevier, 1993.

Vikraman Arvind, Piyush P Kurur, T.C. Vijayaraghavan. Bounded Color Multiplicity Graph Isomorphism is in the Hierarchy.. In CCC ’05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 13-27, IEEE Computer Society, 2005.

Downloads

Full Book

Published

10 March 2026
Copyright (c) 2026 T. C. Vijayaraghavan

Details about the available publication format: E-Book

E-Book

ISBN-13 (15)

978-93-7185-918-9

Details about the available publication format: Book (Paperback)

Book (Paperback)

ISBN-13 (15)

978-93-7185-303-3

How to Cite

Vijayaraghavan, T. C. . (2026). The Complexity of Logarithmic Space Bounded Counting Classes (Second Edition). Deep Science Publishing. https://doi.org/10.70593/978-93-7185-918-9
Download Citation