Редактирование: Полнота относительно L-сведения. NL-полнота. P-полнота
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 7: | Строка 7: | ||
{{ Определение | {{ Определение | ||
|definition=<tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL}</tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>. | |definition=<tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL}</tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>. | ||
+ | }} | ||
+ | |||
+ | {{ Определение | ||
+ | |definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе. | ||
}} | }} | ||
Строка 12: | Строка 16: | ||
| statement = <tex>\mathrm{A} \leq_{\widetilde{L}} \mathrm{B}</tex> и <tex>\mathrm{B} \in \mathrm{L} \Rightarrow \mathrm{A} \in \mathrm{L}</tex>. | | statement = <tex>\mathrm{A} \leq_{\widetilde{L}} \mathrm{B}</tex> и <tex>\mathrm{B} \in \mathrm{L} \Rightarrow \mathrm{A} \in \mathrm{L}</tex>. | ||
| proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}</tex>. Просто выполнить <tex>f(x)</tex> и передать результат в качестве ввода МТ для <tex>\mathrm{B}</tex> нельзя, так как для этого требуется <tex>\Omega(n)</tex> дополнительной памяти. Поэтому будем хранить только позицию <tex>i</tex> головки МТ для <tex>\mathrm{B}</tex> на входной ленте (в двоичной записи это требует <tex>O(\log n)</tex> памяти), и вычислять <tex>i</tex>-ый бит <tex>f(x)</tex> при необходимости обращения к нему путём исполнения <tex>f(x)</tex> без записи результата целиком. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению. | | proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}</tex>. Просто выполнить <tex>f(x)</tex> и передать результат в качестве ввода МТ для <tex>\mathrm{B}</tex> нельзя, так как для этого требуется <tex>\Omega(n)</tex> дополнительной памяти. Поэтому будем хранить только позицию <tex>i</tex> головки МТ для <tex>\mathrm{B}</tex> на входной ленте (в двоичной записи это требует <tex>O(\log n)</tex> памяти), и вычислять <tex>i</tex>-ый бит <tex>f(x)</tex> при необходимости обращения к нему путём исполнения <tex>f(x)</tex> без записи результата целиком. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению. | ||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||