48
правок
Изменения
Нет описания правки
=== Утверждение теоремы ===
'''[[NL]]''' = '''co-NL'''
=== Доказательство ===
Таким образом показано, что '''STNONCON''' ∈ '''NL'''.
Поскольку '''[[NL-полнота задачи о достижимости в графе|STCON]]''' ∈ '''[[NL-полнота|NLC]]''', то аналогичным образом '''STNONCON''' ∈ '''co-NLC''', то получаем.Получаем, что любую задачу из '''co-NL''' можно свести к задаче из '''NL''', а значит '''co-NL''' ⊂ '''NL'''.
Из соображений симметрии '''NL''' ⊂ '''co-NL''', а значит '''NL''' = '''co-NL'''.
