Редактирование: Полнота относительно L-сведения. NL-полнота. P-полнота
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 11: | Строка 11: | ||
{{ Теорема | {{ Теорема | ||
| 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} | + | | proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}.</tex> МТ для <tex>\mathrm{B}</tex> не может хранить ввод, так как работает на <tex> O(\log n) </tex> памяти. Будем поэтому хранить только позицию головки, и на каждом шаге вычислять соответствующий бит с помощью функции <tex>f</tex>. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению. |
}} | }} | ||