Граф является гамильтоновым тогда и только тогда, когда его замыкание представляет собой
Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является
Поток максимален тогда и только тогда, когда в остаточной сети нет
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет независимый набор размера
Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется
При любом входе машина Тьюринга должна
Определение факта, принадлежит ли данное слово языку, носит название
Если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, машина Тьюринга называется
Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
