On generic complexity of theories of finite algebraic structures | Sciact - Система учета научной деятельности ИМ СО РАН

On generic complexity of theories of finite algebraic structures Научная публикация

Журнал

Journal of Physics: Conference Series
ISSN: 1742-6588 , E-ISSN: 1742-6596

Вых. Данные

Год: 2021, Том: 1901, Номер: 1, Номер статьи : 012046, Страниц : DOI: 10.1088/1742-6596/1901/1/012046

Авторы

Rybalov A. ¹

Организации

1	Sobolev Institute of Mathematics, prospekt Koptyuga 4, Novosibirsk, 630090, Russian Federation

This article is devoted to investigation of generic complexity of universal and elementary theories of finite algebraic structures with universal set with more than one element of finite predicate signature with equality. We prove that there are no polynomial strongly generic algorithm, recognizing any such theory, provided P = BPP and P ≠ NP (P ≠ PSPACE). The author is supported by Russian Science Foundation, grant 19-11-00209.

Rybalov A.
On generic complexity of theories of finite algebraic structures
Journal of Physics: Conference Series. 2021. V.1901. N1. 012046 . DOI: 10.1088/1742-6596/1901/1/012046 Scopus OpenAlex

Scopus:	2-s2.0-85107377649
OpenAlex:	W3164219352

Пока нет цитирований