Большие системы

Задачи регулярной реализуемости для описаний конечных отношений

М. Н. Вялый, А. А. Рубцов

Национальный исследовательский университет “Высшая школа экономики”, Москва

Аннотация: Рассмотрены описания конечных отношений на множестве неотрицательных целых чисел в формате, предложенном П. Вольф и Х. Фернау, и связанные с ними задачи регулярной реализуемости. Доказана универсальность этих задач относительно дизъюнктных сводимостей за полиномиальное время для унарных отношений; относительно дизъюнктных сводимостей на полиномиальной памяти для инвариантных бинарных отношений; а также относительно сводимостей по Тьюрингу с $\mathrm{NP}$-оракулом для инвариантных унарных отношений, заданных в унарном алфавите.

Ключевые слова: регулярная реализуемость, сводимость, NP-оракул.

УДК: 621.391 : 519.7

Поступила в редакцию: 05.09.2024
После переработки: 17.10.2024
Принята к печати: 22.10.2024

DOI: 10.31857/S0555292324030069