editor
143
правки
Изменения
Нет описания правки
{{ Определение
|definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе.
}}
{{ Теорема
| statement = <tex>\mathrm{A} \leq_{\widetilde{L}} \mathrm{B}</tex> и <tex>\mathrm{B} \in \mathrm{L} \Rightarrow <tex>\mathrm{A} \in \mathrm{L}</tex>.
| proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow \mathrm{f(x)} \in \mathrm{B}.</tex> МТ для <tex>\mathrm{B}</tex> не может хранить ввод, так как работает на <tex> O(\log n) </tex> памяти. Будем поэтому хранить только позицию головки, и на каждом шаге вычислять соответствующий бит с помощью функции <tex>\mathrm{f}</tex>. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению.
}}
