Статьи автора

О проверке выполнимости алгебраических формул над полем из двух элементов

Номер выпуска 1 от 18.09.2025

Построен вероятностный полиномиальный алгоритм проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для задачи PIT основан на лемме Шварца - Зиппеля, а предложенный в этой статье алгоритм проверки выполнимости основан на лемме Вельянта - Вазирани.

11 0

ЗАДАЧИ РЕГУЛЯРНОЙ РЕАЛИЗУЕМОСТИ ДЛЯ ОПИСАНИЙ КОНЕЧНЫХ ОТНОШЕНИЙ

Номер выпуска 3 от 18.09.2025

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

12 0