|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Порождение малых сложностных классов с помощью логических формул, схем и операций ограниченной конкатенациистатья Исследовательская статья
- Авторы: Савицкий И.В., Марченков С.С.
- Сборник: Математические вопросы кибернетики
- Том: 21
- Год издания: 2023
- Место издания: ФИЗМАТЛИТ Москва
- Первая страница: 52
- Последняя страница: 110
- DOI: 10.20948/mvk-2023-52
- Аннотация: Классы FO и FOM — это малые классы рекурсивных функций, характеризующие параллельные вычисления с константным временем работы и полиномиальным числом процессоров. В статье дан обзор результатов, описывающих основные свойства классов FO и FOM. Приведены различные способы определения этих классов и доказательство эквивалентности этих определений. Охарактеризовано положение FO и FOM в иерархии сложностных классов. Представлены результаты о принадлежности различных функций классам FO и FOM. Описаны базисы по суперпозиции в классах FO и FOM и приведено полное доказательство результата о базисе по суперпозиции в классе FOM, состоящем только из простых, преимущественно арифметических функций.
- Добавил в систему: Савицкий Игорь Владимирович