Non-finite generation of semirings of p-cardinalities
Non-finite generation of semirings of p-cardinalities
Let be a standard complexity class, such as , , , or . Consider the semiring formed by the p-cardinalities of languages in , together with the corresponding semiring of equivalence classes of p-cardinalities.
Non-finite-generation conjecture. For every such complexity class , the semiring of p-cardinalities of languages in 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 , , , and . 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
Sign in to submit a solution.
No solutions have been posted yet.