О сложности проблемы эквивалентности хорновским формулам. II

Изучается сложность проблемы существования хорновского предложения, эквивалентного данному предложению. Доказывается, что для сигнатуры, состоящей из одного одноместного функционального символа и любого конечного числа одноместных предикатных символов, данная проблема вычислима. Если же сигнатура содержит хотя бы два одноместных функциональных символа, устанавливается, что указанная проблема является $m$-полным $\Sigma^0_1$-множеством.