Non-finite generation of semirings of p-cardinalities

From papers

Let CP\mathcal{C} \supseteq \mathsf{P} be a standard complexity class, such as P\mathsf{P}, NP\mathsf{NP}, PSPACE\mathsf{PSPACE}, or EXP\mathsf{EXP}. Consider the semiring formed by the p-cardinalities of languages in C\mathcal{C}, together with the corresponding semiring of equivalence classes of p-cardinalities.

Non-finite-generation conjecture. For every such complexity class C\mathcal{C}, the semiring of p-cardinalities of languages in C\mathcal{C} is not finitely generated. The same holds for the semiring of equivalence classes of p-cardinalities.

This predicts a strong algebraic complexity phenomenon even within standard complexity classes, including P\mathsf{P}, NP\mathsf{NP}, PSPACE\mathsf{PSPACE}, and EXP\mathsf{EXP}. The supplied text gives no resolution, so both non-finite-generation assertions remain open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Joshua A. Grochow, “Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality”, arXiv:2301.07123 (2023).

Solutions 0

No solutions have been posted yet.