THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES

DOI10.32523/2077-9879-2022-13-1-44-68zbMath1499.03031OpenAlexW4288283913MaRDI QIDQ5086506

I. V. Latkin

Publication date: 5 July 2022

Published in: Eurasian Mathematical Journal (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/emj431

zbMATH Keywords

decidable theoriespolynomial timelower complexity boundpolynomial spacetheory of equalitycoding of computations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Basic properties of first-order languages and structures (03C07)

Cites Work

• The most nonelementary theory
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
• Ranks for families of all theories of given languages
• DISTRIBUTIONS OF COUNTABLE MODELS OF QUITE O-MINIMAL EHRENFEUCHT THEORIES
• Computational Complexity
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES