|
Математическая логика, алгебра и теория чисел
О вычислениях над упорядоченными кольцами
И. В. Латкинa, А. В. Селиверстовb a D. Serikbayev East Kazakhstan Technical University, Protozanov Street, 69, Ust-Kamenogorsk, 070004, The Republic of Kazakhstan
b Institute for Information Transmission Problems of the Russian Academy of Sciences, Bolshoy Karetny, 19, Moscow, 127051, Russia
Аннотация:
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. Moreover, various types of non-deterministic machines are considered.
Ключевые слова:
generalized register machine, ring, integral domain, integers, ultrapower, non-deterministic computations, polynomial time, oracle.
Поступила 20 января 2022 г., опубликована 29 декабря 2022 г.
Образец цитирования:
И. В. Латкин, А. В. Селиверстов, “О вычислениях над упорядоченными кольцами”, Сиб. электрон. матем. изв., 19:2 (2022), 1054–1076
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1558 https://www.mathnet.ru/rus/semr/v19/i2/p1054
|
Статистика просмотров: |
Страница аннотации: | 91 | PDF полного текста: | 19 | Список литературы: | 15 |
|