Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит
(Отметьте один правильный вариант ответа.)
Варианты ответа
в классе NCP
в классе N
в классе P(Верный ответ)
Алгоритмы и модели вычислений
Похожие вопросы
Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP
Если существует NP-полная задача П1, которая сводится по Тьюрингу к задаче П2, то задача П2 является
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
В каком классе лежит задача линейного программирования?
Сложность функции в классе P, вычисляемой некоторой машиной Тьюринга, зависит
На пересечении классов NP и co-NP лежит
Если классы P и NP равны, то любую задачу из класса NP можно будет решить
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют
Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то