On generic complexity of theories of finite algebraic structures

On generic complexity of theories of finite algebraic structures Full article

Journal

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

Output data

Year: 2021, Volume: 1901, Number: 1, Article number : 012046, Pages count : DOI: 10.1088/1742-6596/1901/1/012046

Authors

Rybalov A. ¹

Affiliations

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

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