Изменения

По определению <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{P}</tex>, то теорема доказана. Как было показано выше, <tex>\mathrm{CONN} \in \mathrm{NLC}</tex> - такой язык. <tex>\mathrm{CONN} \in \mathrm{P}</tex>, что очевидно следует из существования алгоритма DFS.