0
голосов
0
ответов
34 показа

Рассмотрим вариант задачи о вершинном покрытии:Дано: Неориентированный граф.Вопрос: Найдутся ли такие k вершин графа, что любое ребро графа инцидентно ...
0
голосов
0
ответов
25 показов

Приведите полиномиальный алгоритм сведения задачи о существовании гамильтонова пути в неориентированном графе к следующей задаче о целочисленном решен ...
0
голосов
1
ответ
48 показов

Опишите полиномиальный алгоритм, получающий на вход булеву формулу φ, использующий оракул для языка SAT и вычисляющий выполняющее означивание для φ, е ...
0
голосов
0
ответов
87 показов

Замкнут ли класс NP относительно дополнения?
0
голосов
0
ответов
200 показов

Здравствуйте! Прошу помочь в решении задач (хотя бы некоторых). Заранее большое спасибо всем, кто хоть немного поможет!!!Рассмотрим следующее доказате ...
0
голосов
0
ответов
97 показов

Решить уравнение:$%T(n)=nT(\tfrac{n}{2})+O(n)$%
0
голосов
0
ответов
265 показов

Какова сложность вычисления дизъюнкции $$\bigvee_{i = 1, ...,n} x_{i}$$ в модели разрешающих деревьев?
0
голосов
0
ответов
99 показов

Классифицируйте как можно точнее в полиномиальной иерархии язык A = {(F, G, H) | для любойраскраски F в красный и зелёный цвета найдётся либо красный ...
0
голосов
0
ответов
121 показ

Придумайте NP-трудные языки А и В, такие что А /\ В является coNP-полным.
0
голосов
0
ответов
230 показов

Пусть мы умеем находить ответ на вопрос: "существует ли в произвольном графе Гамильтонов цикл" за полиномиальное время. Другими словами пусть NP=P.Пус ...
0
голосов
0
ответов
136 показов
0
голосов
0
ответов
163 показа
0
голосов
0
ответов
170 показов
0
голосов
0
ответов
323 показа

Структура данных поддерживает операцию, такую что последовательность из n вызовов этой операции занимает время \Тета(nlogn) в худшем случае. Какова ам ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru