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

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

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

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

Является ли разрешимым множество натуральных чисел, не превосходящих :

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

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

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

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

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

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

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

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

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

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

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

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

Что верно для NP-полных и NP-трудных задач:

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

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

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

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

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

Пусть сводится по Карпу к . Выберите верное утверждение:

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

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

Что верно?

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

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

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

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

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

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делится на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

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

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

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

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

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

Задачи 3SAT и 2SAT:

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

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

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

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