Journal of Mathematics Mechanics and Computer Science, 2026, т. 131, № 3, с. 61-77
ON PUNCTUAL AND POLYNOMIAL-TIME COMPUTABLE PRESENTATIONS OF THE POLYNOMIAL RING
Novosibirsk State University, Novosibirsk, Russia
Аннотация · Abstract
This paper studies the existence and properties of punctual and polynomial-time computable presentations of polynomial rings. We focus on the one-variable polynomial ring R[x] over a commutative ring R with unity and establish a relatively simple criterion for the existence of a primitive recursive (p.r.) and punctual presentation of this structure. The notion of punctual computability, which requires that the atomic diagram of a structure be computable in real time, has recently attracted significant attention in computable model theory due to its natural algorithmic interpretation. We prove that a p.r. and punctual presentation of R[x] exists under mild algebraic assumptions on the base ring R, thereby generalizing earlier results on computable rings. Furthermore, we investigate the polynomial-time computable (P-computable) presentation of R[x] and demonstrate that such a presentation arises naturally whenever the base ring R admits a P-computable presentation. In particular, we show that the standard construction of polynomial rings preserves polynomial-time computability, providing an efficient representation of ring operations. In addition, we analyze the punctual dimension of R[x] and establish a dichotomy: the punctual dimension is either exactly 1 or infinite, with no intermediate values possible. This classification reveals a sharp structural boundary and offers new insights into the interface between effective algebra and computational complexity theory.
Сведения · Details
- DOI 10.26577/jmmcs131320265
- Журнал · Journal Journal of Mathematics Mechanics and Computer Science
- Язык · Language английский
- Цитирования (Crossref) · Citations 0