68
правок
Изменения
м
Нет описания правки
Заметим, что данная формула имеет экспоненциальный размер, так как за один шаг рекурсии длина пути уменьшается на одни, а размер формулы удваивается. Поэтому воспользуемся квантором <tex>\forall</tex> и перепишем её следующим образом:
<tex>\phi(A, B, t) = \exists R \,\forall U \,\forall V \, \{\phi(U, V, t-1) \lor -> [\neg(U = A \land V = R) \land lor \neg(U = R \land V = B)]\}</tex>.
Размер полученной функции <tex>\phi(A, B, t)</tex> полиномиален относительно <tex>n</tex>.
