Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные. - презентация

1

2 Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные P п (машины Тьюринга); К классу P относятся задачи, которые могут быть решены за время, п полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (машины Тьюринга); NP п недетерминированной вычислительной машины, а к классу NP задачи, которые могут быть решены за пполиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими.

3 История вопроса В начале 1960-х годов о границах практической применимости алгоритмов смысле ограничений на ее размерность Какие задачи за реальное время В начале 1960-х годов в связи с началом широкого использования вычислительной техники для решения практических задач возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), в которых были введены классы сложности задач. В начале 1960-х годов о границах практической применимости алгоритмов смысле ограничений на ее размерность Какие задачи за реальное время В начале 1960-х годов в связи с началом широкого использования вычислительной техники для решения практических задач возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), в которых были введены классы сложности задач.

4 Класс P (задачи с пполиномиальной сложностью) пполиномиальной (относится к классу P) Задача называется пполиномиальной (относится к классу P), если константа k алгоритм F a O k существуют константа k и алгоритм, решающий задачу с F a ( n ) = O ( n k ), где n - длина входа алгоритма. пполиномиальной (относится к классу P) Задача называется пполиномиальной (относится к классу P), если константа k алгоритм F a O k существуют константа k и алгоритм, решающий задачу с F a ( n ) = O ( n k ), где n - длина входа алгоритма.

5 интуитивно задачи, решаемые за реальное время. Задачи класса P – это интуитивно задачи, решаемые за реальное время. преимущества алгоритмов из этого класса: Отметим следующие преимущества алгоритмов из этого класса: k < 6 1. для большинства задач из класса P константа k < 6 ; 2. класс P инвариантен по модели вычислений (для широкого класса моделей); 3. класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином). задачи класса P «практически разрешимой» задачи. Таким образом, задачи класса P - уточнение определения «практически разрешимой» задачи. интуитивно задачи, решаемые за реальное время. Задачи класса P – это интуитивно задачи, решаемые за реальное время. преимущества алгоритмов из этого класса: Отметим следующие преимущества алгоритмов из этого класса: k < 6 1. для большинства задач из класса P константа k < 6 ; 2. класс P инвариантен по модели вычислений (для широкого класса моделей); 3. класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином). задачи класса P «практически разрешимой» задачи. Таким образом, задачи класса P - уточнение определения «практически разрешимой» задачи.

6 Класс NP (пполиномиально проверяемые задачи) Представим себе, что алгоритм получил решение задачи. Соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? задачу о сумме: Рассмотрим задачу о сумме: Можно ли V Можно ли представить число V в виде суммы каких- либо элементов массива А? nчисел А = (a1,…an) число V Дано n чисел – А = (a1,…an) и число V. X=(x1,…,xn)x i є{0,1} axV Найти X=(x1,…,xn), x i є{0,1}, чтобы a i x i = V. Представим себе, что алгоритм получил решение задачи. Соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? задачу о сумме: Рассмотрим задачу о сумме: Можно ли V Можно ли представить число V в виде суммы каких- либо элементов массива А? nчисел А = (a1,…an) число V Дано n чисел – А = (a1,…an) и число V. X=(x1,…,xn)x i є{0,1} axV Найти X=(x1,…,xn), x i є{0,1}, чтобы a i x i = V.

7 Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с пполиномиальной сложностью: a i x i = V не более Q (n) операций. проверка a i x i = V требует не более Q (n) операций. Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (пполиномиально) проверено. Класс NP (пполиномиально проверяемые задачи)

8 Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации пполиномиальной длины, данной нам свыше, мы можем проверить за пполиномиальное время. задача о коммивояжёре. В частности, к классу NP относятся все задачи, решение которых можно проверить за пполиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре. Класс NP (пполиномиально проверяемые задачи)

9 Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть пполиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пустое. Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть пполиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пустое.

10 Сложность задачи характеризуют сложностью наилучшего алгоритма, решающего задачу с самым трудным значением входа. Различают 3 основных класса сложности задач: 1) задачи, для которых известны алгоритмы пполиномиальной сложности; 2) задачи, для которых не известны алгоритмы пполиномиальной сложности, но для которых и не доказано несуществование таких алгоритмов. Второй класс задач является самым загадочным. Для большинства задач этого класса справедливо следующее: существование пполиномиального алгоритма для одной из них означает существование пполиномиального алгоритма для всех остальных. 3) задачи, для которых установлено, что они не могут быть решены алгоритмом пполиномиальной сложности. Задачи, которые не принадлежат к первому классу, называют труднорешаемыми. Сложность задачи и полиномиальная сводимость

11 Большим разнообразием в отношении сложности отличаются задачи дискретной математики. Алгоритмы решения многих из них имеют переборный характер, что часто приводит к труднорешаемости задачи. Нередки случаи, когда такая задача может быть решена только путем применения алгоритма полного перебора. В таком случае сложность задачи определяется тем, насколько быстро растет множество вариантов с увеличением размера входных данных.

12 Сводимость задач Говорят, что задача Z1 пполиномиально сводится к задаче Z2, если решение задачи Z1 можно получить из решения соответствующей задачи Z2 за пполиномиальное время. Отметим, что если задача Z2 имеет полиномиальную сложность и полиномиальная сводимость задачи Z1 к задаче Z2 доказана, то тем самым доказана полиномиальная сложность задачи Z1. Классы задач P и NP Класс P представляет собой множество задач, для каждой из которых существует детерминированный алгоритм с пполиномиальной функцией сложности. Класс NP определяется как множество задач, которые могут быть решены недетерминированным алгоритмом с пполиномиальной функцией сложности. Очевидно, что множество P принадлежит множеству NP.

13 NP-трудные и NP-полные задачи Задача называется NP-трудной, если любая задача из NP пполиномиально сводится к ней. Задача называется NP-полной, если она является NP-трудной и в то же время принадлежит к классу NP. Таким образом, имеют место следующие соотношения: {NP-полные} {NP-трудные} сложность(NP-полная) сложность(NP-трудная)

14 Примеры NP-трудных задач: -определить максимум клик в заданном графе (т.е. найти наибольшую клику в графе); - найти оптимальный маршрут в симметричной задаче коммивояжера (т.е. с симметричной матрицей стоимости). Примеры NP-полных задач: - задача о выполнимости булевого выражения, представленного в КНФ; - определить, содержит ли заданный граф полный подграф с k-вершинами; - определить, является ли заданный граф гамильтоновым. NP-трудные и NP-полные задачи