On computations over ordered rings

Authors

  • Alexandr Seliverstov Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)
  • Иван Латкин D. Serikbayev East Kazakhstan Technical University

Keywords:

generalized register machine, ring, integral domain, integers, ultrapower, polynomial time, oracle

Abstract

We consider generalized register machines over ordered rings with an auxiliary binary operation. In particular, we consider the ring of integers, its infinite Cartesian power, and ultrapowers. The feasibility and computational complexity of some algorithms are discussed. There is also given an example of a non-factorial ring, which is elementarily equivalent to the ring of integers. It is shown that non-deterministic computations with integers can be implemented as computations over the Cartesian power of the ring of integers. It is also possible to model calculations with an oracle using such machines. This provides an algebraic approach to describing some classes of computational complexity. However, this model of computation differs significantly from alternating machines.

Author Biography

Иван Латкин, D. Serikbayev East Kazakhstan Technical University

Кафедра Инженерная математика 

Ученая степень: доктор PhD

 Должность: Ассоциированный профессор

Published

2023-08-03

Issue

Section

Mathematical logic, algebra and number theory