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