EUVIMEDEUVIMED entdecken
Crossref

ON PUNCTUAL AND POLYNOMIAL-TIME COMPUTABLE PRESENTATIONS OF THE POLYNOMIAL RING

Javokhir Ruzimov

Journal of Mathematics Mechanics and Computer Science · 06.08.2026 · 131 (3) · 61-77

DOI: 10.26577/jmmcs131320265 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Mathematics Mechanics and Computer Science, online erschienen am 06.08.2026. Verfasst von Javokhir Ruzimov.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Ruzimov, J. (2026). ON PUNCTUAL AND POLYNOMIAL-TIME COMPUTABLE PRESENTATIONS OF THE POLYNOMIAL RING. Journal of Mathematics Mechanics and Computer Science, 131(3), 61-77. https://doi.org/10.26577/jmmcs131320265

Vancouver

Ruzimov J. ON PUNCTUAL AND POLYNOMIAL-TIME COMPUTABLE PRESENTATIONS OF THE POLYNOMIAL RING. Journal of Mathematics Mechanics and Computer Science. 2026;131(3):61-77. doi:10.26577/jmmcs131320265

BibTeX
@article{Ruzimov2026,
  author = {Ruzimov, Javokhir},
  title = {ON PUNCTUAL AND POLYNOMIAL-TIME COMPUTABLE PRESENTATIONS OF THE POLYNOMIAL RING},
  journal = {Journal of Mathematics Mechanics and Computer Science},
  year = {2026},
  volume = {131},
  number = {3},
  pages = {61--77},
  doi = {10.26577/jmmcs131320265}
}
Kostenlos starten →