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

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

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

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

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

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

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

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

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

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

$%PP$% определяется как класс языков, для которых существует вероятностная МТ, такая что она выдает 1 с вероятностью большей 0.5 на словах из языка, и ...
0
голосов
0
ответов
185 показов

Дана коробка и набор карт. Карту в коробку можно положить только двумя способами. В каждой карточке есть два столбца отверстий, некоторые из которых м ...
0
голосов
0
ответов
202 показа

Поле, разделенное на n грядок, каждая из которых разделенана m ячеек. Грядки отделены друг от друга стенами; между ячейками одной грядки стен нет. В н ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru