0
голосов
0
ответов
29 показов
Верно ли, что $%\emptyset \le_m A$%
Верны ли эти утверждения?Для всех $%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 показов
Как доказать существование подмножества, которое в сумме равняется числу t.
Дано множество положительных целых чисел S и целое число t. Спрашивается, существует ли подмножество T $%\subseteq$% S, такое что сумма чисел в T равн ...
1
голос
1
ответ
86 показов
Задача на нахождение алгоритма
Дано натуральное число N. Придумать алгоритм нахождения минимально возможного набора чисел такого, чтобы с помощью суммирования каких-то элементов из ...
0
голосов
0
ответов
68 показов
Доказать NP-полноту или привести полиномиальный алгоритм
Пусть задано конечное множество $% S $% и конечный набор его подмножеств $%S_1, S_2, \dots, S_k $%. Для каждого множества $%S_i $% заданы два числа $% ...
0
голосов
0
ответов
93 показа
Доказать, что задача NP-полная или привести полиномиальный алгоритм
Дано: ориентированный граф $% G = (V, E) $%, две вершины $%v, w \in V $% и список пар вершин этого графа $$P = (v_1, w_1), \cdots, (v_k, w_k). $$ Спра ...
1
голос
0
ответов
165 показов
Доказательство NP-полноты
Дано: неориентированный граф $% G = (V, E) $% и две вершины $%s, t \in V $%. Спрашивается, содержит ли граф $% G $% гамильтонов путь из $% s $% в $% t ...
0
голосов
0
ответов
79 показов
Замкнутость класса NP относительно пересечения
докажите, что класс NP замкнут относительно пересечения
0
голосов
0
ответов
55 показов
Как представить грамматику типа 0 или 1 в виде графа?
Как это сделать? Типа 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 и NP
Предположим, что P = N P . Докажите, что в этом случае существует полиномиальный алгоритм, который по всякой формуле логики высказываний A либо говори ...
0
голосов
0
ответов
92 показа
Класс NP алгоритмы
Рассмотрим сложностной класс coNP = {L | L ∈ NP}. Докажите, что если NP ⊂ coNP, то NP = coNP
207 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.