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

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

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

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

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

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

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

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

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

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

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

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