классы P и NP

Вещественная неотрицательная функция f (m), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином P (m) с вещественными коэффициентами такой, что f (m)≤ P (m) для всех m ∈ N +. Задачи, для которых существуют алгоритмы с "полиномиальным" временем работы принадлежат классу P (эти задачи в основном решаются быстро и без каких-либо проблем).

Формальное определение. Язык L принадлежит классу P, тогда и только тогда, когда существует детерминированная машина Тьюринга M, такая, что:

- при любых входных данных M заканчивает свою работу за полиномиальное время,
- для всех x ∈ L M выдает результат 1,
- для всех x, не принадлежащих L, M выдает результат 0.

Задачи класса NP - задачи, удовлетворяющие условию: если имеется ответ (возможное решение), то его легко верифицировать - проверить, является оно решением или нет.

Рассмотрим пример задачи из класса NP. Пусть дано множество целых чисел, например, {-7,-3, -2, 5, 8}. Требуется узнать, есть ли среди этих чисел 3 числа, которые в сумме дают 0. В данном случае ответ "да" (например, такой тройкой являются числа {-3,-2,5}. При возрастании размера множеств целых чисел количество подмножеств, состоящих из 3 элементов, экспоненциально возрастает. Между тем, если нам дают одно такое подмножество (его еще называют сертификатом), то мы легко можем проверить, равна ли 0 сумма его элементов.

Формальное определение:

Язык L принадлежит классу NP, тогда и только тогда, когда существуют такие полиномы p и q и детерминированная машина Тьюринга M, такие, что:

- для любых x, y машина M на входных данных (x, y) выполняется за время p (| x |),
- для любого x ∈ L существует строка y длины q (| x |), такая что M (x, y)=1,
- для любого x не из L и всех строк длины q (| x |) M (x, y)=0.

Полиномиальная сводимость или сводимость по Карпу. Функция f 1 сводится к функции f 2, если существует функция f ∈ P, такая, что для любого x f 1(x)= f 2(f (x)).

Задача T называется NP-полной, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула приняла значение " истина ".

Задача T называется NP-трудной, если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи R 1 к R 2 по Куку - это полиномиальный по времени алгоритм, решающий задачу R 1 при условии, что функция, находящая решение задачи R 2, ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.

Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP):

Вот еще 2 примера NP-полных задач.

Задача о рюкзаке. Даны объемы w 1,..., wn ∈ N и стоимости v 1,..., vn ∈ N набора из N предметов. Также даны общий объем W и число g. Необходимо найти множество предметов из набора, общий объем которых не превышает W, а общая стоимость не превышает g.

Задача о коммивояжере. Дано n вершин с номерами 1,..., n и все n (n −1)/2 попарных расстояний между ними, а также число b. Найти цикл, проходящий через все вершины ровно по одному разу и имеющий длину не более b, или же сообщить, что такого цикла нет. Другими словами, необходимо найти перестановку τ (1),..., τ (n) вершин такую, что dτ (1) +... + dτ (n)≤ b.

Для нахождения решений NP-трудных задач в худшем случае требуется осуществить полный перебор всех вариантов, при этом часто нужно генерировать все возможные перестановки и проверять их на удовлетворение некоторого свойства.
Время выполнения задач, решение которых связано с перестановками, быстро выходит из-под контроля потому, что число всех возможных перестановок сильно растет с возрастанием количества элементов перестановки. Например, для множества из 5 элементов можно сгенерировать 5!=5*4*3*2*1=120 перестановок, а для множества из 6 элементов перестановок сгенерируется уже в 6 раз больше, и т.д.

Во многих случаях для решения таких задач используются эвристические подходы, которые гарантируют не оптимальное, но рациональное решение.

Информационные источники:
O большое и o малое (википедия), Complexity and Big-O notations notes, Algorithmic Complexity, Об использовании символов o и O, Логарифм (википедия), Coursera course on Algorithms and Data structures, Part1 (презентация), Algolist. Оценки времени выполнения, форум RSDN, Алгоритмы для NP-трудных задач (презентация), P_(complexity) (wikipedia), NP_(complexity) (wikipedia), Полиномиальная сводимость, Задача выполнимости булевых формул (википедия), Сведение по Куку (википедия), Доклад "Переборные задачи", форум ixbt, Абрамов. Лекции о сложности алгоритмов

Автор: Natalia Smirnova на 17:46

Отправить по электронной почте

Дата добавления: 2015-07-11