Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Какова точность, гарантируемая жадным алгоритмом в задаче о k-покрытии?

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

Рассмотрим две задачи разрешения, P1 и P2, такие что

• P1 сводится полиномиально по Карпу к 3SAT
• 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?

Какова наилучшая сложность алгоритма из темы про FPTAS-алгоритмы для рюкзака?

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I

Если L4 в P, то L2 в P

II

Если L1 или L3 в P, то L2 в P

III

L1 в P, тогда и только тогда, когда L3 в P

IV

Если L4 в P, то L1 в P и L3 в P.

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.

Найдите неверное утверждение:

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

Какой алгоритм используется в рассмотренных FPTAS-алгоритмах для рюкзака?

Выберите корректное утверждение:

Выберите не NP-полную задачу

Для чего применяется «метод условных вероятностей»:

Пусть X — задача из NP. Что верно?

Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:

Паросочетание, это подмножество...

Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:

Цикл, проходящий через все вершины графа, называется

Рассмотрим пару задач на графах.

P1

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.

P2

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

Задача 2SAT:

Какова точность, гарантируемая гибридным вероятностным алгоритмом из темы про вероятностное округление MAX-SAT?

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?