Вариант 216686316.
Какой из этих тестов на простоту не является рандомизированным:
Как называется задача оптимизации со следующей формулировкой:
Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?
Цикл, проходящий через все ребра графа по одному разу, называется
Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:
Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?
Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.
Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц ?
Вероятностные «zero-error»-алгоритмы:
Какова точность, гарантируемая алгоритмом Кристофидеса в метрической задаче коммивояжера?
Какой алгоритм используется только в лучшем из рассмотренных в теме FPTAS-алгоритмов для рюкзака?