Изменения

|definition='''Класс <tex>\mathrm{coNL}</tex>''' — множество языков, дополнение до которых принадлежит <tex>\mathrm{NL}</tex>.<br><tex>\mathrm{coNL} = \{L\bigm| \overline{L} \in \mathrm{NL}\}</tex>.}}

{{ Теорема| statement = <tex>\mathrm{coNLL} = \subseteq \mathrm{LNL} \subseteq \bigmmathrm{NP}.</tex>| overlineproof = #Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \in subseteq \mathrm{NL}</tex>.#Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)}= poly(n)</tex>, а, следовательно, если машина завершает свою работу, то она это делает за <tex>O(poly(n))</tex>времени. Следовательно, <tex>\mathrm{NL} \subseteq \mathrm{NP}.</tex>