Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных

Доказана $\Sigma^0_1$-трудность различных теорий бинарного предиката в языке с тремя предметными переменными и бинарной предикатной буквой (без констант и равенства). Показано, что при добавлении равенства, композиции и транзитивного замыкания получаются $\Pi_1^1$-трудные теории бинарного предиката при двух предметных переменных в языке.