Computational Complexity of Theories of a Binary Predicate with a Small Number of Variables
Михаил Николаевич Рыбаков · Doklady Mathematics · 2022
Abstract— We prove $$\Sigma _{1}^{0}$$ -hardness of a number of theories of a binary predicate with three individual variables (in languages without constants or equality). We also show that, in languages with equality and the operators of composition and of transitive closure, theories of a binary predicate are $$\Pi _{1}^{1}$$ -hard with only two individual variables.