2. Класс np - полиномиально проверяемые задачи

_{Предположим, что некоторый алгоритм дает решение некоторой задачи. Соответствует ли полученный ответ поставленной задаче, насколько быстро мы можем проверить его правильность?}

_{Рассмотрим в качестве примера задачу о сумме. Дано целых чисел, содержащихся в массиве , и целое число . Найти массив , где , такой что . Содержательно: может ли быть представлено число в виде суммы каких-либо чисел из массива А? Если какой-то алгоритм выдает массив Х, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка того, что требует не более арифметических операций.}

_{Еще один пример – решение и проверка решения СЛАУ.}

_{Содержательно задача относится к классу NP – классу задач недетерминированной полиномиальной сложности, если ее решение, полученное некоторым алгоритмом, может быть полиномиально проверено. Класс NP был впервые введен в работах Эдмондса.}

_{Задачи, входящие в NP-класс, практически неразрешимы, мы не знаем алгоитмов, способных решить их за разумное время. Сложность всех известных детерминированных алгоритмов, решающих эти задачи, либо екпоненциальная, либо факториальная. Сложность некоторых из них равна , где - количество входных данных. В этом случае при добавлении к списку всего 1 элемента время работы алгоритма удваивается.}

_{Словосочетание «недетерминированные полиномиальные» объясняется следующим двухшаговым подходом к их решению. На первом шаге имеется недетерминированный алгоритм, генерирующий возможное решение такой задачи – что-то вроде попытки угадать решение; иногда такая попытка оказывается успешной, и мы получаем оптимальный или близкий к оптимальному ответ, иногда безуспешной (ответ далек от оптимального). На втором шаге проверяется, , действительно ли ответ, полученный на первом шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени, но мы не знаем, сколько раз нам придется повторить оба эти шага, чтобы получить искомое решение. Хотя оба шага и полиномиальны, число обращений к ним может оказаться экспоненциальным или факториальным.}

_{К классу относится задача о коммивояжере. Задан набор городов и «стоимость» путешествия между любыми двумя из них. Нужно определить такой порядок, в котором следует посетить все города по одному разу и вернуться в исходный город, чтобы общая стоимость путешествия оказалась минимальной. Восемь городов можно упорядочить возможными способами, а 10 – 3628800 способами. Поиск наилучшего пути требует перебора всех этих возможностей. Если предположить, что у нас есть алгоритм, способный посчитать стоимость путешествия через 15 городов в указанном порядке, и за секунду он обрабатывает 100 вариантов, то ему потребуется больше 4 веков, чтобы обработать все варианты и найти наилучший. Детерминированный алгоритм, сравнивающий все способы упорядлочения городов, работает очень долго.}

_{Задачу о коммивояжере можно решить при помощи описанной выше двухшаговой процедуры. На первом шаге случайным образом генерируется некоторое упорядочивание городов. Поскольку это недетерминированный процесс, каждый раз будет получаться новый порядок. Очевидно, что процесс генерации можно реализовать за полиномиальное время: мы можем хранить список городов, генерировать случайный номер, выбирать из списка город с этим именем и удалять его из списка, чтобы он не появился второй раз - операций. На втором шаге производится подсчет стоимости путешествия по городам в указанном порядке - операций. Оба шага полиномиальны, поэтому задача о коммивояжере лежит в классе . Времяемкой ее делает необходимое число итераций этой процедуры.}

_{Примером NP-задачи является хорошо известная задача о раскраске графа. Вершины неориентированного графа можно раскрасить в разные цвета, которые обычно обозначаются целыми числами. Нас интересуют такие раскраски, при которых концы каждого ребра окрашены разными цветами. Очевидно, что в графе с вершинами можно покрасить вершины в различных цветов, но можно ли обойтись меньшим количеством цветов? Задача может быть сформулирована следующими образами: найти минимальное количество цветов, необходимых для раскраски вершин графа, либо можно ли раскрасить вершины в С или менее цветов?}

_{У задачи о раскраске графа есть много практических приложений. Пусть каждая вершина графа обозначает читаемый в университете курс. Вершины соединяются ребром, если есть студент, слушающий оба курса. Если предположить, что каждый студент слушает 5 курсов, то на студента приходится 10 ребер (см.рис.). Предположим, что на 3500 студентов приходится 500 курсов. Тогда у получившегося графа будет 500 вершин и 35000 ребер. Если на экзамены отведено 20 дней, то вершины графа нужно раскрасить в 20 цветов, чтобы ни у одного студента не приходилось по два экзамена в день.}

_{Задача об упаковке рюкзака. Имеется набор объектов объемом стоимости .Задачи: а)необходимо упаковать рюкзак объемом К так, чтобы его стоимость была максимальной; б) можно ли добиться, чтобы суммарная стоимость упакованных объектов была хотя бы Ф. Такая задача возникает при выборе стратегии влажения денег. Объемом здесь является объем различных вложений, стоимостью – предполагаемая величина дохода, а объем рюкзака – размер планируемых капиталовложений.}

_{Следует отметить, что такую двухшаговую процедуру можно было применить к любой из рассматривавшихся ранее задач. Например, сортировку списка можно выполнять, генерируя произвольный порядок элементов исходного списка и проверяя, не является ли этот порядок возрастающим. Это рассуждение относит задачу сортировки к классу . Разница между классом и классом в том, что в первом случае у нас имеется детерминированный алгоритм, решающий задачу за полиномиальное время, а во втором мы такого алгоритма не знаем.}

_{Один из способов решения задач состоит в том, чтобы свести, или редуцировать, одну задачу к другой. Сводимость задач может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2 с помощью алгоритма решения задачи 1 (например, вместо того, чтобы непосредственно решать СЛАУ с симметричной и положительно определенной матрицей, минимизируется функционал энергии).}

_{Таким образом, если задача 1 задана множеством конкретных проблем , а задача 2 – множеством , и существует функция (алгоритм), сводящая конкретную постановку задачи 2 к конкретной постановке задачи 1, т.е. , то задача 2 сводима к задаче 1. Если при этом временная сложность алгоритма есть , т.е. алгоритм сведения принадлежит классу Р, то говорят, что задача 2 полиномиально сводится к задаче 1.}

_{Рассмотрим пример. Пусть первая задача состоит в том, чтобы вернуть значение «да» в случае, если одна из булевских переменных имеет значение «истина», и вернуть «нет» в противоположном случае. Вторая задача заключается в том, чтобы найти максимальное значение в списке целых чисел. Каждая из них допучкает простое ясное решение, но предположим, что мы знаем решение задачи о поиске максимума, а задачу про булевские переменные решать не умеем. Мы хотим свести задачу о булевских переменных к задаче о максимуме целых чисел. Напишем алгоритм преобразования набора значений булевских переменных в список целых чисел, котторый значению «ложь» сопоставляет число 0, а значению «истина» - число 1. Затем воспользуемся алгоритмом поиска максимального элемента в списке. По тому, как составлялся список, заключаем, что этот максимальный элемент может быть либо нулем, либо 1. Такой ответ можно преобразовать в ответ задачи о булевских переменных, возвращая «да», если максимальное значение равно 1, и «нет», если оно равно 0.}

_{Поиск максимального значения выполняется за линейное время ( операций), а редукция первой задачи ко второй тоже требует линейного времени, поэтому задачу о булевских переменных тоже можно решить за линейное время.}