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

Является ли конкатенация двух разрешимых языков перечислимой?

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

Предположим, разумеется, что Тогда что будет верно?

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

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.

• (1) Задача A — в P
• (2) Задача A — в NP
• (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

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

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

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

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

Гамильтонов цикл в графе:

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

Вероятностный алгоритм A, который, получая

• вход I
• вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

Пересечение двух каких классов окажется пустым, если окажется, что ?

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

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

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

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

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

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

P1

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

P2

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

Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?

Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?

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

Какой алгоритм используется в алгоритме Кристофидеса?

Вероятностные «zero-error»-алгоритмы:

Какой из этих тестов на простоту не является рандомизированным:

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

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

Какое утверждение неверно?

Является ли пустое множество разрешимым?

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

У языков 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.

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