== NL-полная задача ==
Опять же{{ Определение|definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе.}} {{ Теорема| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-[[Участник:SkudarnovYaroslav/Теормин к зачёту Сведение относительно класса функций. Сведение по теории сложности#Видимо, это про NP-Карпу. Трудные и полные задачи|тутполна относительно <tex>\mathrm{\widetilde{L}}</tex>-сведения]].}}
== Класс P/poly ==
