On generic complexity of theories of finite algebraic structures
| Autor: | Alexander Rybalov |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Journal of Physics: Conference Series. 1901:012046 |
| ISSN: | 1742-6596 1742-6588 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|