Эффективные алгоритмы — вопросы

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

Вероятностные «zero-error»-алгоритмы:

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

Если алгоритму из темы про полиномиальный в среднем алгоритм упаковки подать на вход единичную матрицу инцидентности, он, если считать от длины входа, затратит время …

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.

Цикл, проходящий через все ребра графа по одному разу, называется