База ответов ИНТУИТ

Алгоритмы и модели вычислений

<<- Назад к вопросам

Пересекаются ли классы P и NPC?

(Отметьте один правильный вариант ответа.)

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