Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является

Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют

Связный граф, в котором n вершин и n-1 ребро, носит название

Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается

Если задача П₁ сводится по Тьюрингу к задаче П₂ из класса NP, то задача П₁ является

Если существует NP-полная задача П₁, которая сводится по Тьюрингу к задаче П₂, то задача П₂ является

Каковы общие затраты однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n?

Определите время, за которое можно сделать двусторонний список из одностороннего, имея процессоров, в logn раз меньше, чем n?

Если классы P и NP равны, то любую задачу из класса NP можно будет решить

Множество вершин S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название

Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP