Изменения

Перейти к: навигация, поиск

NL-полнота задачи о достижимости

125 байт добавлено, 16:21, 14 марта 2013
Нет описания правки
| proof = Необходимо доказать, что <tex>\forall \mathrm{B} \in \mathrm{NL}</tex> верно, что <tex>\mathrm{B} \in \mathrm{P}</tex>.
По определению <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>. Следовательно, если <tex>\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}</tex>, то <tex>\forall \mathrm{B}</tex>, сводимого к <tex>\mathrm{A}</tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}</tex>, следовательно, поскольку класс <tex>\mathrm{P}</tex> замкнут относительно <tex>\widetilde{\mathrm{P}}</tex>-сведения по Карпу, <tex>\mathrm{B} \in \mathrm{P}</tex>. Таким образом, если существует язык, принадлежащий <tex>\mathrm{NLC}</tex>, то теорема доказана. Как было показано выше, <tex>\mathrm{CONN} \in \mathrm{NLC}</tex> . <tex>\mathrm{CONN} \in \mathrm{---P}} такой язык</tex>, это очевидно следует из существования алгоритма DFS.
}}
editor
143
правки

Навигация