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

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

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

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

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

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

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

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

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

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

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

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

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