Статья в сборнике "Математические вопросы кибернетики" №21, Москва, 2023
Авторы:Савицкий И.В., Марченков С.С.
Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенации
Аннотация:
Классы FO и FOM — это малые классы рекурсивных функций, характеризующие параллельные вычисления с константным временем работы и полиномиальным числом процессоров. В статье дан обзор результатов, описывающих основные свойства классов FO и FOM. Приведены различные способы определения этих классов и доказательство эквивалентности этих определений. Охарактеризовано положение FO и FOM в иерархии сложностных классов. Представлены результаты о принадлежности различных функций классам FO и FOM. Описаны базисы по суперпозиции в классах FO и FOM и приведено полное доказательство результата о базисе по суперпозиции в классе FOM, состоящем только из простых, преимущественно арифметических функций.
Ключевые слова:
малые классы рекурсивных функций, класс FO, класс FOM, параллельные вычисления, операция ограниченной конкатенации, базис по суперпозиции
