О вычислениях над упорядоченными кольцами
Ключевые слова:
обобщённая регистровая машина, кольцо, область целостности, целые числа, ультрастепень, полиномиальное время, оракулАннотация
Мы рассматриваем обобщённые регистровые машины над упорядоченными кольцами со вспомогательной бинарной операцией. В частности, мы рассматриваем кольцо целых чисел, его бесконечную декартову степень и ультрастепени. Обсуждаются существование и вычислительная сложность некоторых алгоритмов. Также дан пример нефакториального кольца, элементарно эквивалентного кольцу целых чисел. Показано, что недетерминированные вычисления с целыми числами могут быть реализованы как вычисления над декартовой степенью кольца целых чисел. Также можно моделтровать вычисления с оракулом, используя такие машины. Это открывает алгебраичекий подход к описанию некоторых классов вычислительной сложности. Однако эта модель вычислений существенно отличается от альтернирующих машин.
