14. Класс NP. NP – полные языки. Свойства NP – полных языков.

В теории алгоритмов NP­полная задача — задача из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (т.е. при помощи операций, число

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

15. Теорема Кука.

Теорема Кука утверждает, что задача о выполнимости булевой формулы в КНФ является NP­полной.

16. Примеры NP – полных языков (КЛИКА, ВНУТРЕННЯЯ УСТОЙЧИВОСТЬ, ВЕРШИННОЕ ПОКРЫТИЕ РЕБЕР, ГАМИЛЬТОНОВ ЦИКЛ, ЗАДАЧА КОММИВОЯЖЕРА, ЦИКЛОРАЗРЕЗАЮЩЕЕ МНОЖЕСТВО ВЕРШИН, ПОКРЫТИЕ МНОЖЕСТВАМИ).

КЛИКА

Задача о клике относится к классу NP­полных задач в области теории графов.

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

ЗАДАЧА КОММИВОЯЖЕРА

Задача коммивояжёра заключается в отыскании самого выгодного маршрута, проходящего через указанные города по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного.

ВЕРШИННОЕ ПОКРЫТИЕ РЕБЕР

Вершинное покрытие для неориентированного графа G = (V, E) это множество его вершин S, такое что, у каждого ребра графа хотя бы один из концов входит в S.

Задача о вершинном покрытии требует указать минимально возможный размер k вершинного покрытия для заданного графа.

ГАМИЛЬТОНОВ ЦИКЛ

Гамильтонов граф — это граф, содержащий гамильтонов цикл.

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

ПОКРЫТИЕ МНОЖЕСТВАМИ

Исходными данными задачи о покрытии множества является конечное множество и семейство его подмножеств. Покрытием называют семейство наименьшей мощности, объединением которых является . В случае постановки вопроса о разрешении на вход подаётся пара и целое число ; вопросом является существование покрывающего множества мощности (или менее).

Пример: В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого­то задания необходим некий набор навыков. Так же, есть группа людей, владеющих некоторыми из этих навыков. Необходимо сформировать минимальную группу

для выполнения задания, включающую в себя носителей всех необходимых навыков.

17. Связь между сложностью дискретных оптимизационных задач и сложностью распознавания языков.

18. Методы установления NP – сложности задач.

Сужение задачи один из трех общих методов доказательства, которые часто встречаются и могут подсказать путь к доказательству полноты новой задачи. Другие два ­ это Метод локальной замены и Метод построения компонент. Доказательство методом сужения полноты фиксированной задачи Q принадлежит заключается просто напросто в установлении того, что задача Q включает в качестве частного случая известную полную задачу Q’ . Суть состоит в том, чтобы указать дополнительные ограничения, которые требуется наложить на индивидуальные задачи из Q, чтобы получившаяся в результате сужения задача была бы эквивалентна Q’ . При этом не требуется, чтобы возникающая в результате сужения задача была точной копией известной полной задачи, необходимо только, чтобы между задачами имелось "очевидное" взаимно однозначное соответствие, сохраняющее ответы "да" или "нет". Взаимно однозначное соответствие, которое дает сведение Q’ к Q, обычно настолько очевидно, что его даже не требуется указывать явно.

Метод локальной замены.

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