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

Верны ли эти утверждения?Для всех $%A\subseteq\mathbb N$%,$%\emptyset \le_m A$%$%\mathbb N \le_m A$%--Например, первое верно тогда и только тогда когд ...
0
голосов
0
ответов
45 показов

Какова идея построения программы $%\alpha$%, которая ведет себя так:для каждой программы $%x$%, если $%\phi_x()$% останавливается за $%n$% шагов, то $ ...
0
голосов
0
ответов
65 показов

Пусть$%A(G, k)$%— полиномиальный алгоритм, который для произвольных графа$%G$%и натурального числа$%k$%с вероятностью 1 возвращает 1, еслиGсодержит кл ...
0
голосов
0
ответов
76 показов

Дано множество положительных целых чисел S и целое число t. Спрашивается, существует ли подмножество T $%\subseteq$% S, такое что сумма чисел в T равн ...
1
голос
1
ответ
86 показов

Дано натуральное число N. Придумать алгоритм нахождения минимально возможного набора чисел такого, чтобы с помощью суммирования каких-то элементов из ...
0
голосов
0
ответов
68 показов

Пусть задано конечное множество $% S $% и конечный набор его подмножеств $%S_1, S_2, \dots, S_k $%. Для каждого множества $%S_i $% заданы два числа $% ...
0
голосов
0
ответов
93 показа

Дано: ориентированный граф $% G = (V, E) $%, две вершины $%v, w \in V $% и список пар вершин этого графа $$P = (v_1, w_1), \cdots, (v_k, w_k). $$ Спра ...
1
голос
0
ответов
165 показов

Дано: неориентированный граф $% G = (V, E) $% и две вершины $%s, t \in V $%. Спрашивается, содержит ли граф $% G $% гамильтонов путь из $% s $% в $% t ...
0
голосов
0
ответов
79 показов

докажите, что класс NP замкнут относительно пересечения
0
голосов
0
ответов
55 показов

Как это сделать? Типа 2 и 3 легко представляются в виде графа, где вершина - Нетерминал, а ребро - Терминал.Если нельзя - то какие есть другие способы ...
0
голосов
1
ответ
55 показов

Разрешимо ли множество кодов < M > таких машин Тьюринга M,что при всех n ∈ N на любом входе длины n машина M останавливается неболее чем за 100n ...
0
голосов
0
ответов
45 показов

Найти НОД полиномов f(x)=x^3-3x+2 и g(x)=x^3+3x^2-x+2 в кольце F11[x]. Можете подсказать как это сделать, вроде есть алгоритм Евклида но тут какое-то ...
0
голосов
0
ответов
106 показов

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

Предположим, что P = N P . Докажите, что в этом случае существует полиномиальный алгоритм, который по всякой формуле логики высказываний A либо говори ...
0
голосов
0
ответов
92 показа

Рассмотрим сложностной класс coNP = {L | L ∈ NP}. Докажите, что если NP ⊂ coNP, то NP = coNP
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru