Pith. sign in

REVIEW

Step Recursion: A Three-Parameter Refinement of the Grzegorczyk Hierarchy

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2608.04871 v1 pith:N47MVNWD submitted 2026-08-05 cs.LO cs.CC

classification cs.LOcs.CC
keywords varphistepbasisgrzegorczykhierarchyrecursionboundedclass
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We introduce bounded step recursion and a three-parameter hierarchy refining the Grzegorczyk hierarchy. For a strictly increasing function $\varphi:\mathbb N\to\mathbb N$ with $\varphi(x)\ge x+1$, its generalized inverse $$\rho_\varphi(y)=\min\{z:\varphi(z)\ge y\}$$ replaces the ordinary predecessor and generates the descent schedule $y,\rho_\varphi(y),\rho_\varphi^{[2]}(y),\ldots,0$. From a Grzegorczyk basis $B_m$, composition, and bounded step recursion with step $g_n^{[l]}$, we define classes $H^m_{n,l}$, where $m$ measures the initial-function strength, $n$ selects a growth scale, and $l$ fixes the stride through its canonical layers. For all $n,n'\ge2$, we obtain an exact criterion for $H^a_{n,l}\subseteq H^b_{n',l'}$. Below horizontal collapse, fixed strides are ordered by reverse divisibility: inclusion at equal row is governed by $l'\mid l$, not by the numerical order of $l$ and $l'$. All fixed strides collapse from initial basis $m=n$, and the common class equals the ordinary bounded-recursion class $E^m$ exactly from $m=n+1$. Positive inclusions use exact-depth simulations; separations use a direct piecewise-monotone trace theorem and a canonical-zone invariant for selected dependency chains. The doubling row $g_1(x)=2x+1$ is exceptional at low bases. We prove $H^m_{1,l}=E^m$ for all $m\ge3$, construct the first vertical bridge at basis $2$, and show that every fixed-arity function in $H^2_{1,l}$ is binary polynomial-time computable, with $H^2_{1,l}\subsetneq FP$. Equality $H^2_{1,l}=E^2$ would imply $P=NP$.

Discussion (0). Continue with ORCID to comment.

Pith tools