On generic complexity of theories of finite algebraic structures
Alexander Rybalov · Journal of Physics Conference Series · 2021
Abstract 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.