Inhomogeneity of the p-s-Degrees of Recursive Functions
Let \(|x|\) be the length of \(x\) in binary notation. A singulary function \(f\) has polynomial growth rate (p.g.r.) if there is a polynomial \(p\) such that \(|f(x)|\leq p(|x|)\) for all \(x\). The functions considered in the paper are recursive with p.g.r. For functions \(f\) and \(g,f\) is p-s-reducible to \(g\) iff \(f\) is uniformly computable from \(g\) in polynomial time, i.e., \(f(x)=\Phi (x,g(x))\) for polynomial computable \(\Phi\) (G. Miller). This relation induces the partitioning of the singulary recursive functions with p.g.r. into the p-s-degrees. Under the natural partial order, these degrees form an upper semilattice \(\underset\sim {R}^p_s\). An upper semilattice \(U\) is distributive iff whenever \(a\leq b\vee c\), \(U\) contains \(b'\leq b\) and \(c'\leq c\) such that \(a=b'\vee c'\). A closed interval of a semilattice is again a semilattice. A function \(f\) is \(n\)-valued iff \(x< n\) for all \(x\in\text{rng}(f)\). A principal result of this paper shows that if \(\underset\sim {a}\) is the (possibly nonzero) degree of a 2-valued recursive function, the interval \([\underset\sim {0},\underset\sim {a}]\) is distributive. Since it is known that there is a degree \(\underset\sim {b}\) for which \([\underset\sim {0},\underset \sim{b}]\) is nondistributive, it is concluded that \(\underset\sim {R}^p_s\) is inhomogeneous. Additionally, it is shown that for any \(n\geq 2\), the p-s-degrees containing \(n\)-valued functions are downward closed and have a maximal element.
This page was built for publication: Inhomogeneity of the p-s-Degrees of Recursive Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511551)
