Some derivations among Logarithmic Space Bounded Counting Classes

S. Madhan; T. C. Vijayaraghavan; V. Janaki

arxiv: 2310.11874 · v4 · submitted 2023-10-18 · 💻 cs.CC · math.LO

Some derivations among Logarithmic Space Bounded Counting Classes

V. Janaki , S. Madhan , T. C. Vijayaraghavan This is my paper

Pith reviewed 2026-05-24 06:56 UTC · model grok-4.3

classification 💻 cs.CC math.LO

keywords logarithmic spacecounting classes#LNLC_=LPLclosure properties

0 comments

The pith

Derivations from closure properties of #L establish NL equals C_=L and both sit inside PL.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper uses closure properties of the counting class #L to perform derivations that relate several logarithmic-space counting classes. These steps produce the equalities and inclusions NL = C_=L ⊆ PL. A reader following the argument sees how properties already known for #L can be applied to collapse or contain the nondeterministic, exact-counting, and probabilistic variants of logspace.

Core claim

Using closure properties of #L, the authors derive a chain of relations among logarithmic space bounded counting classes that yields the result NL = C_=L ⊆ PL.

What carries the argument

Closure properties of #L that are applied to obtain inclusions and equalities among the classes NL, C_=L and PL.

If this is right

NL equals the exact counting class C_=L.
C_=L is contained in the probabilistic class PL.
The landscape of logspace classes collapses at these three points.
Any further closure property of #L can be used to obtain additional relations among the same classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the same closure properties hold for other resource bounds, similar collapses might appear in polynomial space or other regimes.
The result supplies a concrete route by which known facts about #L can be turned into statements about NL and PL without new simulations.
It suggests checking whether the same derivation chain works when the underlying machine model is changed from deterministic to nondeterministic transducers.

Load-bearing premise

The invoked closure properties of #L remain valid and are strong enough to carry the derivations to the stated equalities and inclusions.

What would settle it

An explicit construction of a language in NL that is not in C_=L, or in C_=L that is not in PL, would refute the claimed relations.

read the original abstract

In this paper we show derivations among logarithmic space bounded counting classes based on closure properties of $\#L$ that leads us to the result that $NL=C_=L\subseteq PL$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims NL = C_=L from #L closures, but the equality step does not follow from those properties.

read the letter

The main takeaway is that this paper asserts NL equals C_=L based on closure properties of #L, leading to NL = C_=L ⊆ PL, but that equality does not follow from the usual closures. The paper does well in recalling the standard inclusions that come from #L being closed under addition and multiplication. Those properties correctly support NL ⊆ C_=L by building GapL functions that vanish on non-members and C_=L ⊆ PL because GapL functions sit inside PL. The derivations for those directions look routine and unproblematic if the closures are applied as stated. The soft spot is the jump to equality. Standard closures do not give a way to decide whether an arbitrary GapL function is zero inside NL, so C_=L ⊆ NL requires an explicit reduction or simulation that the closures alone do not supply. If the paper only re-derives the known chain and then states equality, the central claim is unsupported. This work is aimed at the narrow circle of researchers who follow logspace counting classes. A reader already familiar with the area will notice the gap at once and gain little. Someone outside the subfield will see a reminder of the inclusions but will be left with an incorrect impression about equality. I would not bring this to a reading group. I would not cite it. It does not deserve peer review because the key step for the equality is missing.

Referee Report

1 major / 0 minor

Summary. The paper claims to establish derivations among logarithmic space bounded counting classes (including #L, GapL, C_=L, NL and PL) by invoking closure properties of #L, and concludes that these derivations yield the equality NL = C_=L ⊆ PL.

Significance. If the derivations are valid, the result would collapse NL with C_=L, a nontrivial statement in space-bounded complexity. The manuscript credits closure properties (addition, multiplication, and composition) of #L as the sole engine for the inclusions and equality.

major comments (1)

[main result / abstract] The central derivation of NL = C_=L (abstract and main result section) asserts that closure properties of #L suffice for both directions. While these closures are known to establish NL ⊆ C_=L (via GapL functions vanishing on non-members) and C_=L ⊆ PL, the reverse inclusion C_=L ⊆ NL does not follow from closure properties alone; it requires an explicit NL simulation or reduction of arbitrary GapL zero-testing that is not supplied by the listed closures.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive comment. We address the concern regarding the claimed derivation of NL = C_=L below.

read point-by-point responses

Referee: [main result / abstract] The central derivation of NL = C_=L (abstract and main result section) asserts that closure properties of #L suffice for both directions. While these closures are known to establish NL ⊆ C_=L (via GapL functions vanishing on non-members) and C_=L ⊆ PL, the reverse inclusion C_=L ⊆ NL does not follow from closure properties alone; it requires an explicit NL simulation or reduction of arbitrary GapL zero-testing that is not supplied by the listed closures.

Authors: We agree that the referee's observation is correct. The closure properties of #L (addition, multiplication, and composition) suffice to establish NL ⊆ C_=L and C_=L ⊆ PL, but do not by themselves yield the reverse inclusion C_=L ⊆ NL. The manuscript's abstract and main result section overstate the reach of these closures by claiming they lead to the equality NL = C_=L. We will revise the abstract, introduction, and main result section to state only the inclusions that follow directly from the closures (NL ⊆ C_=L ⊆ PL) and to remove or qualify the equality claim. If the authors wish to retain an equality result, an explicit simulation argument would need to be supplied in a future version; no such argument appears in the current manuscript. revision: yes

Circularity Check

0 steps flagged

Derivations use standard #L closures; no reduction to inputs by construction

full rationale

The paper claims to derive NL=C_=L⊆PL from closure properties of #L. No equations, definitions, or self-citations appear in the provided text that would make any step self-definitional, a fitted input renamed as prediction, or dependent on a load-bearing self-citation chain. The central claim is presented as following from independently known closures (addition, multiplication, composition) without the result being equivalent to the inputs by definition. This is the normal case of a self-contained argument against external benchmarks; no circularity is exhibited.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.0 · 5544 in / 1052 out tokens · 21359 ms · 2026-05-24T06:56:14.977201+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

The complexity of matix rank and feasible systems of linear equations

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

work page 1999
[2]

A very hard log-space counting class

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

work page 1993
[3]

Relationships among PL, \# L and the Determinant

Eric Allender and Mitsunori Ogihara. Relationships among PL, \# L and the Determinant . RAIRO-Theoretical Informatics and Applications , 30:1--21, 1996

work page 1996
[4]

Hemaspaandra and Mitsunori Ogihara

Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion , Springer, 2001

work page 2001
[5]

Lov \'a sz, J

L. Lov \'a sz, J. Pelikan and K. Vesztergombi. Discrete Mathematics: Elementary and Beyond , Springer, 2003

work page 2003
[6]

Introduction to the Theory of Computation, Third edition , Cengage Learning, 2013, First Indian reprint, 2018

Michael Sipser. Introduction to the Theory of Computation, Third edition , Cengage Learning, 2013, First Indian reprint, 2018

work page 2013
[7]

Complexity Classes Defined by Counting Quantifiers , Journal of the ACM , 38(3): 753-774, 1991

Jacobo Toran. Complexity Classes Defined by Counting Quantifiers , Journal of the ACM , 38(3): 753-774, 1991

work page 1991

[1] [1]

The complexity of matix rank and feasible systems of linear equations

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

work page 1999

[2] [2]

A very hard log-space counting class

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

work page 1993

[3] [3]

Relationships among PL, \# L and the Determinant

Eric Allender and Mitsunori Ogihara. Relationships among PL, \# L and the Determinant . RAIRO-Theoretical Informatics and Applications , 30:1--21, 1996

work page 1996

[4] [4]

Hemaspaandra and Mitsunori Ogihara

Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion , Springer, 2001

work page 2001

[5] [5]

Lov \'a sz, J

L. Lov \'a sz, J. Pelikan and K. Vesztergombi. Discrete Mathematics: Elementary and Beyond , Springer, 2003

work page 2003

[6] [6]

Introduction to the Theory of Computation, Third edition , Cengage Learning, 2013, First Indian reprint, 2018

Michael Sipser. Introduction to the Theory of Computation, Third edition , Cengage Learning, 2013, First Indian reprint, 2018

work page 2013

[7] [7]

Complexity Classes Defined by Counting Quantifiers , Journal of the ACM , 38(3): 753-774, 1991

Jacobo Toran. Complexity Classes Defined by Counting Quantifiers , Journal of the ACM , 38(3): 753-774, 1991

work page 1991