Open AccessOn generic complexity of theories of finite algebraic structures
Author(s) -
Alexander Rybalov
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1901/1/012046
Subject(s) - predicate (mathematical logic) , signature (topology) , mathematics , algebraic number , algebra over a field , discrete mathematics , set (abstract data type) , computer science , pure mathematics , geometry , mathematical analysis , programming language
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.