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

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

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

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

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

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

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

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

Структура данных поддерживает операцию, такую что последовательность из n вызовов этой операции занимает время \Тета(nlogn) в худшем случае. Какова ам ...
0
голосов
0
ответов
244 показа

Дана строка $%s$% в алфавите $%\Sigma_1$% и строка $%t$% в алфавите $%\Sigma_2$%, требуется найти инъективную функцию $%f{:}\,\Sigma_1\rightarrow\Sigm ...
1
голос
1
ответ
206 показов

Есть несколько примеров, которые очень хотелось бы понять.Первый пример, нужно найти Theta или O.Довольно логично что это Но совсем не знаю как доказа ...
0
голосов
0
ответов
212 показов

Здравствуйте, почитав math.hashcode.ru/questions/35138#35141 и наконец разобравшись в проблеме NP и P задач меня заинтересовало: существуют ли более с ...
0
голосов
1
ответ
323 показа

$%PP$% определяется как класс языков, для которых существует вероятностная МТ, такая что она выдает 1 с вероятностью большей 0.5 на словах из языка, и ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru