Bijective polynomial-time enumeration of languages in P and the D-classes of regular elements of the semigroup fP

The semigroup $fP$ of polynomially balanced, polynomial-time computable partial functions on $\{0,1\}^*$ was introduced by Birget as an algebraic lens on the $P$ vs $NP$ problem: worst-case one-way functions are exactly its non-regular elements, so $fP$ is a regular semigroup iff $P=NP$. Birget asked whether all regular elements of $fP$ with infinite image lie in a single $\mathcal D$-class, that of the identity, equivalently whether every infinite language in $P$ is the image of an injective, total, polynomial-time computable function (a bijective polynomial-time enumeration), possibly an invertible (regular) or a one-way one. The universal reading is false: any total polynomial-time injection with image $L$ forces the number of strings of $L$ of length at most $n$ to grow at least like $2^{n^c}$, so sparse infinite languages in $P$ are counterexamples; for the invertible version this density obstruction is published as Corollary 4.24 of Grochow's polynomial-time cardinality theory, whose p-countability is exactly the invertible version of the enumerator question and whose p-cardinals match the $\mathcal D$-classes of the regular elements of $fP$. The surviving open problem is the characterization: determine which infinite languages in $P$ admit a total injective polynomial-time enumerator and which are p-countable, closing the gap between the necessary condition of exponential density and sufficient conditions such as strong p-rankability within the exponentially dense regime; in the flagship instance, decide whether every exponentially dense language in $P$ is p-countable.

Background

Let $A=\{0,1\}$ and let $A^*$ be the set of all finite strings over $A$. Birget (2015) introduced the semigroup $fP$ of all partial functions $f:A^*\to A^*$ that are polynomially balanced (also called honest: there are polynomials $p,q$ with $|f(x)|\le p(|x|)$ and $|x|\le q(|f(x)|)$ for all $x$ in the domain of $f$) and computable by a deterministic polynomial-time Turing machine; composition makes this a semigroup. The motivation is that a worst-case one-way function, meaning a function in $fP$ for which no polynomial-time algorithm, given $y$ in the image, finds any preimage of $y$, is exactly a non-regular element of $fP$ in the semigroup-theoretic sense (an element $x$ of a semigroup is regular if $xx'x=x$ for some $x'$ in the semigroup; a semigroup is regular if all its elements are regular). These one-way functions are based on worst-case, not average-case, complexity, and $fP$ is a regular semigroup iff $P=NP$.

Green's relations organize any semigroup: $x\le_{\mathcal R}y$ iff $x=yu$ for some element $u$ (equality of principal right ideals up to inclusion), $\mathcal L$ is the left-right dual, and two elements are $\mathcal D$-equivalent if some element is $\mathcal R$-equivalent to one and $\mathcal L$-equivalent to the other; $\mathcal D$-classes are the standard coarse blocks of a semigroup's structure. In $fP$, the $\mathcal R$-classes of regular elements are indexed by their images: a regular $f$ with image $L$ satisfies $f\equiv_{\mathcal R}\mathrm{id}_L$, where $\mathrm{id}_L$ is the identity map restricted to $L$; moreover the image of a regular element of $fP$ is exactly a language in $P$, and every infinite $L\in P$ contributes the regular element $\mathrm{id}_L$ of $fP$ with infinite image. Birget's Proposition 2.2 states that a regular $f\in fP$ with infinite image lies in the $\mathcal D$-class of the identity $\mathrm{id}_{A^*}$ iff there exists $g\in fP$ that is injective, total (defined on all of $A^*$) and regular, with $\mathrm{Im}(g)=\mathrm{Im}(f)$; for such a total injective $g$, regularity is equivalent to the inverse of $g$ being polynomial-time computable on the image. Birget's questions, whether all regular elements with infinite image share one $\mathcal D$-class and whether every infinite language in $P$ is the image of an injective total polynomial-time function, therefore amount to asking for a bijective polynomial-time enumeration of the languages in $P$.

A density obstruction bounds any affirmative answer. If $g$ is total, injective and polynomial-time computable with time bound $p$, then $|g(x)|\le p(|x|)$, since a machine cannot print more symbols than its running time; hence the $2^{k+1}-1$ inputs of length at most $k$ must map to distinct elements of $L=\mathrm{Im}(g)$ of length at most $p(k)$. So the census function $c_L(n)=|L\cap A^{\le n}|$ must satisfy $c_L(p(k))\ge 2^{k+1}-1$, i.e. $L$ must be exponentially dense ($c_L(n)\ge 2^{n^c}$ for some constant $c>0$). Sparse infinite languages in $P$, such as $L=\{0^{n^2}:n\ge 1\}$, admit no such $g$, and $\mathrm{id}_L$ is a regular element of $fP$ with infinite image outside the $\mathcal D$-class of $\mathrm{id}_{A^*}$. For the invertible version this necessity of exponential density is published as Corollary 4.24 of Grochow (2023).

Grochow (2023) independently developed the invertible version under the name polynomial-time cardinality: two languages are p-equipollent if there is a bijection between them computable in polynomial time with a polynomial-time inverse, and a language is p-countable if it is p-equipollent to $A^*$ (honesty of the maps is automatic, since the inverse's running time bounds the length of the preimage it prints). Combining Birget's Proposition 2.2 with these definitions, one checks that for infinite $L_1,L_2\in P$ the elements $\mathrm{id}_{L_1}$ and $\mathrm{id}_{L_2}$ are $\mathcal D$-equivalent in $fP$ iff $L_1$ and $L_2$ are p-equipollent, and that $\mathrm{id}_L$ lies in the $\mathcal D$-class of $\mathrm{id}_{A^*}$ iff $L$ is p-countable; the minor differences between $fP$'s polynomially balanced partial functions and Grochow's partial polynomial-time functions do not affect these equivalences. So the source's $\mathcal D$-classification question is exactly the p-cardinality classification of the languages in $P$, the p-cardinal of a language being its p-equipollence class. Grochow's Theorem 4.25 states that for exponentially dense languages strong p-rankability implies p-countability, through the chain: strongly p-rankable implies p-scalable implies p-countable implies weakly p-rankable with respect to some length-related order. Here a language is strongly p-rankable if its ranking function $x\mapsto|\{z\in L:z\le_{\mathrm{lex}}x\}|$, counting the lexicographic predecessors of $x$ inside $L$, is computable in polynomial time (Grochow also generalizes rankability to other length-related total orders $\prec$, meaning orders with $x\prec y$ implying $|x|\le\mathrm{poly}(|y|)$); weakly p-rankable weakens this to polynomial-time computability only on inputs that lie in $L$; and a language is p-scalable if it is p-isomorphic to a strongly p-rankable set, where p-isomorphic, in the sense of Berman and Hartmanis, means related by a total polynomial-time bijection of all of $A^*$, with polynomial-time inverse, carrying one language onto the other. The density hypothesis is essential: strong p-rankability alone does not imply p-countability, since the sparse language $\{0^{n^2}:n\ge 1\}$ is strongly p-rankable while, by the density obstruction above, no sparse language is p-countable. Grochow also proves that p-countability is preserved under finite differences, and that there are languages in $P$ with incomparable p-cardinals, as well as an infinite language in $P$ that is not p-equipollent to any proper subset of itself (a Dedekind p-finite set) and has sub-logarithmic density. All of these negative examples fail exponential density. Which exponentially dense languages in $P$ are p-countable is left open there (the converses of the Theorem 4.25 implications are stated as believed false); enumerating a language in lexicographic order would require computing its ranking function, and no general polynomial-time method for ranking languages in $P$ is known.

Problem Statement

Let $A=\{0,1\}$ and let $fP$ be the semigroup of polynomially balanced (meaning $|f(x)|\le p(|x|)$ and $|x|\le q(|f(x)|)$ for polynomials $p,q$, for all $x$ in the domain of $f$), polynomial-time computable partial functions $A^*\to A^*$. Recall that $f\in fP$ is regular if $ff'f=f$ for some $f'\in fP$; that $\mathcal D$-equivalence is Green's relation, under which two elements are $\mathcal D$-equivalent if some element is $\mathcal R$-equivalent to one and $\mathcal L$-equivalent to the other; that a language $L$ is exponentially dense if its census function $c_L(n)=|L\cap A^{\le n}|$ satisfies $c_L(n)\ge 2^{n^c}$ for some constant $c>0$; and that $L$ is p-countable if it is p-equipollent to $A^*$, i.e. in polynomial-time bijection with $A^*$ via maps with polynomial-time inverse. The source paper asks (i) whether all regular elements of $fP$ with infinite image lie in a single $\mathcal D$-class, namely that of the identity $\mathrm{id}_{A^*}$, and (ii) whether every infinite language $L\in P$ is the image of an injective, total, polynomial-time computable function $g$, with $g$ possibly regular (polynomial-time invertible on its image) or one-way (admitting no polynomial-time preimage-finder on its image). As recorded in the background, both universal readings are false as stated: any such $g$ forces $L$ to be exponentially dense, so sparse infinite languages in $P$ such as $\{0^{n^2}:n\ge 1\}$ are counterexamples, and their identity maps are regular elements with infinite image outside the $\mathcal D$-class of $\mathrm{id}_{A^*}$. The problem, in the generality that survives, is the corresponding characterization:

1. Determine exactly which infinite languages $L\in P$ are the image of a total injective $g\in fP$ (a bijective polynomial-time enumeration of $L$), and which of those admit a regular such $g$, equivalently are p-countable.
2. Equivalently, in semigroup terms: classify the $\mathcal D$-classes of the regular elements of $fP$ with infinite image. Since for infinite $L_1,L_2\in P$ one has $\mathrm{id}_{L_1}\equiv_{\mathcal D}\mathrm{id}_{L_2}$ iff $L_1$ and $L_2$ are p-equipollent, this is the same as classifying the p-cardinals (p-equipollence classes) of the languages in $P$.
3. In particular, close the gap between the known necessary condition (exponential density of the census function) and the known sufficient conditions (strong p-rankability within the exponentially dense regime, and finite modification of p-countable sets): does every exponentially dense language in $P$ admit a total injective polynomial-time enumerator, and is every exponentially dense language in $P$ p-countable, i.e. is $\mathrm{id}_L$ in the $\mathcal D$-class of $\mathrm{id}_{A^*}$ for every exponentially dense $L\in P$? Where such enumerators exist, determine whether $g$ can be chosen one-way (non-invertible).
4. At the level of pairs, as the source also asks: characterize which infinite languages in $P$ can be mapped onto each other by elements of $fP$, i.e. determine for which infinite $L_1,L_2\in P$ there exists $f\in fP$ whose restriction to $L_1$ has image exactly $L_2$. The enumeration question of items 1--3 corresponds to the case $L_1=A^*$ with the map additionally required to be injective; this surjectivity relation is related to, but distinct from, the injective comparison of p-cardinals ($L_2$ p-equipollent to a subset of $L_1$) and from the $\mathcal R$-order among the elements $\mathrm{id}_L$, which by Proposition 2.1 of the source records only inclusion between images.

References

1. J.C. Birget, 'Semigroups and one-way functions', International Journal of Algebra and Computation 25(1-2):3-36 (2015). DOI: 10.1142/S0218196715400019; arXiv:1306.1447; https://arxiv.org/abs/1306.1447
2. J.C. Birget, 'Infinitely generated semigroups and polynomial complexity', International Journal of Algebra and Computation 26(4):727-750 (2016). DOI: 10.1142/S0218196716500314; arXiv:1503.04610; https://arxiv.org/abs/1503.04610
3. J.C. Birget, 'Polynomial-time right-ideal morphisms and congruences', International Journal of Algebra and Computation 28:791-835 (2018). DOI: 10.1142/S0218196718500364; arXiv:1511.02056; https://arxiv.org/abs/1511.02056
4. J.C. Birget, 'Inverse monoids associated with the complexity class NP', Semigroup Forum 98:369-397 (2019). DOI: 10.1007/s00233-018-9990-x; arXiv:1703.02519; https://arxiv.org/abs/1703.02519
5. Joshua A. Grochow, 'Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality', Theory of Computing Systems 67(3):627-669 (2023). DOI: 10.1007/s00224-023-10118-y; arXiv:2301.07123; https://arxiv.org/abs/2301.07123