15. Классификация задач

1. P-класс – полиномиальный. Трудоёмкость по определению

2. NP-класс – non deterministic polynomial – недетерминированный полиномиальный. Нету алгоритмов быстрого решения – асимптотика .

3. Неполиномиальный -

4. Алгоритмически неразрешимые задачи (пример – «проблема останова»).

1. P-класс

Смотри книгу

2. NP-класс

Абстрактная задача – это произвольное бинарное отношение Q между множеством входных данных I (instanced) и выходных соотношений S (solution).

В теории NP-полноты рассматриваются только задачи разрешения. Это задачи, в которых требуется дать ответ либо «да», либо «нет» на некоторый вопрос. Например для коммивояжёра – является ли последовательность вершин обходом графа оптимальной.

Исходные данные могут быть представлены в различной кодировке в смысле системы счисления. Если существует полиномиальный алгоритм перевода из одной кодировки (представления) в другую, то эти представления эквивалентны.

Фиксировав представление абстрактной задачи говорят о её строковом представлении в виде битовой строки. Алгоритм решает строковую задачу за время если на входном данном битовой строки длины алгоритм работает за время .

Тогда сложностным классом P называется множество всех строковых задач разрешения, которые могут быть решены за полиномиальное время.

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

3. Формальные языки

См книжку

Алгоритм A допускает слово , если на входе алгоритм выдаёт результат 1, т.е.

но не обязан отвергать всякое слово , не принадлежащее (язык, или наша решаемая задача).

Если алгоритм допускает все слова из , а все остальные слова отвергает, то говорят что алгоритм А распознаёт язык L.

4. Сложностной класс np

Язык L принадлежит классу NP, Если существует такой полиномиальный алгоритм A с двумя аргументами, и такой многочлен p(x) с целыми коэффициентами, что

Т.е. алгоритм A проверяет язык L, если для любой строки x∈L (например, графа), найдётся сертификат Y (т.е. последовательность вершин обхода), с помощью которого алгоритм A может проверить принадлежность x (т.е. конкретного графа) множеству L – множеству графов, имеющих гамильтонов цикл, а для x не принадлежащего L (т.е. если граф не имеет вообще гамильтонова цикла), такого сертификата нет.

Проблема .

1. 

2. 

3. 

Самостоятельно.

5. Сводимость

Неформально: задача Q сводится к задаче Q’, если задачу Q можно решить для любого входа, считая известным решение задачи Q’ для какого-то любого другого входа, например: задача решения линейного уравнения сводится к задачи решения квадратного уравнения (если добавить фиктивный старший член).

Язык сводится за полиномиальное время к языку

Если существует такая функция , вычислимая за полиномиальное время

Что

( - тогда и только тогда)

Здесь функция f называется сводящая.

Заметим что если - полиномиальный язык, то полиноминален также.

6. NP-полнота

Запись можно интерпретировать так: сложность языка не более чем полиномиально превосходит сложность языка .

Определение. Язык называется NP-полным (NP Complete, NPC), если

1. 

2. 

Если язык обладает свойством 2, но не доказана его принадлежность к классу NP (т.е. не разработан проверяющий алгоритм сертификат), то такая задача принадлежит к классу NP-трудных задач (NP-Hard, NPH).

Основным свойством класса NPC является:

1. Если некоторая NP-полная задача имеет полиномиальный алгоритм решения, то для любой задачи NPC существует полиномиальный алгоритм решения и P=NP.

2. Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы.

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

Программисту необходимо знать о существовании класса NP для того, чтобы уметь её (задачу) распознать, доказать что она такова (принадлежит к классу NPC), а следовательно не имеет эффективного в смысле полиномиального алгоритма решения и сосредоточиться на поиске приближённого эвристического алгоритма.

7. Схема доказательства NP-полноты языка (задачи) L

1. Доказываем, что L принадлежит NP.

2. Выбираем какой-либо известный NP-полный язык L’.

3. Строим алгоритм, вычисляющий функцию , которая отображает входы задачи L’ во входы задачи L.

4. Доказываем, что функция f сводит L’ к L.

5. Доказываем, что функция f полиномиальна.