NP-трудные задачи
В тео́рии алгори́тмов — науке, изучающей общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления, классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания, решение которых при наличии некоторых дополнительных сведений можно «быстро», то есть за время, не превосходящее полинома от размера данных проверить на машине Тьюринга.
Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).
По задачам распознавания образов на факультете ВМК МГУ читается серьезный курс https://www.ccas.ru/frc/papers/mestetskii04course.pdf. Постановка задачи здесь такая. Будем считать, что все объекты или явления разбиты на конечное число классов. Для каждого класса известно и изучено конечное число объектов – прецедентов. Задача распознавания образов состоит в том, чтобы отнести новый распознаваемый объект к какому-либо классу.
Задача распознавания образов является основной в большинстве интеллектуальных систем. Рассмотрим примеры интеллектуальных компьютерных систем.
1. Машинное зрение. Это системы, назначение которых состоит в получении изображения через камеру и составление его описания в символьном виде (какие объекты присутствуют, в каком взаимном отношении находятся и т.д.).
2. Символьное распознавание – это распознавание букв или цифр.
a. Optical Character Recognition (OCR);
b. Ввод и хранение документов;
c. Pen Computer;
d. Обработка чеков в банках;
e. Обработка почты.
3. Диагностика в медицине.
a. Маммография, рентгенография;
b. Постановка диагноза по истории болезни;
c. Электрокардиограмма.
4. Геология.
5. Распознавание речи.
6. Распознавание в дактилоскопии (отпечатки пальцев), распознавание лица, подписи, жестов.
Понятно, что такие задачи хотелось бы решать быстро, а в ряде случаев их необходимо решать быстро.
Эквивалентно класс NP можно определить как класс, содержащий задачи, которые можно «быстро» решить на недетерминированной машине Тьюринга. Теперь попробуем разобраться, что означает «быстро» и п очему так много внимания этим вопросам?
Исследуя время, необходимое для решения тех или иных задач, обнаружили, что с ростом "входа" (размерности матрицы, длины текста, числа объектов и т.п.) время, потребное на решение (а также объем памяти и пр.) растет устрашающим образом. Практически важным оказалось как сокращение этого времени, так и оценка, насколько для данного алгоритма может оказаться велико время (и пр.), потребное для решения задачи. Оказалось, что с ростом "входа", время работы разных частей алгоритма растет по разному, и для больших "входов" имеет смысл исследовать только "главную часть". При малом объеме данных существенный вклад внесет, например, ввод данных, где затраты пропорциональны объему. Но с ростом объема данных, если есть часть алгоритма, время работы которой пропорционально квадрату "входа" и нет более быстро растущих зависимостей ‑ именно эта часть и определит время его работы.
Для определенности скажем, что вычисления выполняются на машине Тьюринга, хотя можно перенести логику рассуждения на любую воображаемую (Поста, Успенского, Маркова) или реальную машину. Зависимость времени работы от длины входа (также для определенности её измеряют длиной "входа" в битах) может быть задана функцией f(x). Она может быть полиномом N-ной степени, экспонентой ex, факториалом х! и т.п. При больших х факториал будет расти быстрее экспоненты, экспонента быстрее любого полинома, полином бОльшей степени - быстрее полинома меньшей. При малых х это, вообще говоря, не выполняется, но важность представляет именно поведение при больших х.
Классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных для детерминированной МТ). Полиномиальные алгоритмы – это алгоритмы, время работы которых оценивается как функция O(n), O(n log n), O(n2), O(n3), O(n1000), где n – это «размер входа».
Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, задачи сортировки данных, выяснение связности графов и другие. Итак, к классу P относятся задачи, решение которых может быть быстро (за полиномиальное время) найдено.
К классу NP принадлежат задачи, решаемые за полиномиальное время с помощью недетерминированной МТ. За «полиномиальное время» означает, что если входные данные, записанные на ленту МТ, занимают N ячеек, то машине для получения ответа надо совершить не более T(N) переходов, где T(N) –многочлен (какой-то степени).
Если задача экспоненциальна, то ее решение возможно только для очень малых значений входа. Поэтому большой интерес представляет нахождение полиномиальных алгоритмов ее решения или доказательство того, что для данной задачи таких нет в принципе. В попытках найти решение некоторых задач, было обнаружено, что, в определенном смысле, они все эквивалентны. Если существует полиномиальный алгоритм, решающий одну из них, то существует такой алгоритм для любой из них. При этом преобразование любой задачи из этого класса в решаемую требует полиномиального времени. В отличие от задач класса P, для которых найдется полиномиальный алгоритм (степень полинома произвольна - задача со сложностью N1000000 полиномиальна!), и задач класса Е, которые не решаемы менее чем за экспоненциальное время, задачи данного класса решаются "недетерминированными машинами Тьюринга" за полиномиальное время - неясно, правда, где НДМТ производятся! НДМТ не более чем полиномиальное число раз в процессе решения сталкиваются с необходимостью выбора - и решают его превращением одной машины в несколько, каждая из которых идёт по своему пути (говорят, в свое время так в США решали вопрос выбора способа получения урана для атомной бомбы - построили по заводу для каждого способа!). Понятно, что попытка это реализовать практически приведет к появление экспоненциального - но уже числа машин. Несколько более утешительна иная интерпретация - в момент выбора появляется "оракул", который объясняет нам, который путь правильный. Утешительна она потому, что если нам удастся придумать и алгоритмизовать способ выбора правильного пути, то мы получим полиномиальный алгоритм. Таким образом, удайся нам решение хоть одной NP-задачи, мы можем надеяться на решение их всех.
Практика часто довольствуется нахождением приближенного решения за разумное время.
В чем проблема?
«Hardware» vs. «Brainware»
Базовый алгоритм: время работы O(2n), на практике работает для n<=n0.
Аппаратный подход «hardware»
По закону Мура[1] каждые полтора года компьютеры удваивают производительность. Каким станет n0? Оказывается n0 -> n0 + 1.
Мозговой подход
Удалось придумать алгоритм, работающий за 1.41n и n0 -> 2n0.
Примеры NP-полных задач (не попадающих в класс P):
- Задача о выполнимости булевых формул. Экземпляром задачи является булева формула, состоящая только из имен переменных, скобок и операций
(И), 
(ИЛИ) и 
(HE). Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной. - Задача коммивояжёра. Одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
- Задача о рюкзаке. Вор проник в комнату, где лежит N предметов. Для каждого предмета известна его масса и стоимость. Требуется заполнить рюкзак, максимизируя суммарную стоимость предметов, при условии, что общая масса отобранных предметов не может превышать заданного P.
· Проблема Штейнера состоит в поиске минимального дерева Штейнера — кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (1796—1863). В 1941 году вышла монография Р. Куранта и Г. Роббинса «Что такое математика?», в которой авторы написали следующее:
«Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни 
, 
, 
системой дорог таким образом, чтобы их общая протяженность была минимальной.
Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, … поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной».
· Проблема раскраски графа. Определить минимальное число цветов (хроматическое число графа G — обозначается χ(G).), в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета.
· Задача о вершинном покрытии. Вершинное покрытие для неориентированного графа G = (V, E) это множество его вершин S, такое что, у каждого ребра графа хотя бы один из концов входит в S. Задача о вершинном покрытии требует указать минимально возможный размер 
вершинного покрытия для заданного графа.
Пример: Граф, изображённый справа, имеет вершинное покрытие 
размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера {2, 4, 5} и 
{1, 2, 4}. Размером (size) вершинного покрытия называется число входящих в него вершин.
- Задача о клике. Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. И
ными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера. На рисунке приведен граф с кликой размера 3.
Неформально: к классу NP относят задачи, которые могут быть решены перебором 2роly(n) вариантов.
Принадлежность классу NP — это положительная характеристика!
Пример: факторизация, или разложение числа на простые множители. Всякое составное число может быть единственным образом представлено в виде произведения простых множителей. Например, 48 = 2 · 2 · 2 · 2 · 3, 225 = 3 · 3 · 5 · 5, 1050 = 2 · 3 · 5 · 5 · 7.
В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей.
В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа — экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих параметров (то есть от длины самого числа в бинарном представлении).
Вторая группа — субэкспоненциальные алгоритмы. Рекомендую Д. Кнут Раздел 4.5.4. Разложение на простые множители // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — С. 425—468. — 832 с. — ISBN 0-201-89684-2
Предполагаемая большая вычислительная сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как RSA. Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел.
NP-полные задачи. Неформально, это наиболее трудные задачи внутри класса NP. Примеры были приведены.
NP-трудные задачи. Неформально, задача C называется NP-трудной, если для неё существует такая NP-полная задача, которая сводится к C за полиномиальное время (алгоритмическая сводимость по Куку). Например, проблема остановки является NP-трудной, т.к. её невозможно решить на МТ. С не обязательно принадлежит классу NP!
Проблема остановки
Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
Доказательство неразрешимости проблемы останова лаконично и остроумно. Вот оно.
Предположим, что МТ, решающая задачу останова, существует. Обозначим ее H(m, s). Эта машина анализирует закодированную машину m с содержимым ее ленты s. Если машина m заканчивает работу на ленте s[2], машина H переходит в состояние qyes; в противном случае будет произведен переход в состояние qno (обратите внимание, что машина H всегда заканчивает работу!) Теперь сконструируем другую машину T с состоянием ленты str. Алгоритм работы машины T такой:
Имитировать работу машины H(str, str);
if (машина H перешла в состояние qno) перейти в состояние qyes;
else выполнять бесконечный цикл;
Таким образом, машина T заканчивает работу, если переданная ей в виде строки машина str «зависает». В противном случае T переходит в бесконечный цикл сама.
«Зависает» ли машина T(t) (где t — закодированное представление машины Т)?
Предположим, что да. Это означает, что выполнение алгоритма пошло по ветви ИНАЧЕ, что, в свою очередь, возможно, если H(t, t) заканчивает работу в состоянии qyes. По определению машины Н это переводится как «машина t с лентой t не зависает». Получается, что машина Т не зависает! Мы пришли к противоречию.
Рассмотрим теперь вторую альтернативу: машина T(t) заканчивает работу. Это означает, что машина H(t, t) переходит в состояние qno, то есть «машина t с лентой t не заканчивает работу (зависает)». Противоречие!
Противоречия в рассуждениях возникли потому, что было предположено существование машины Н. Следовательно, машины, решающей задачу останова, не существует.
Методы для решения NP-полных задач
• Рекурсия
• Хитрый перебор
• Локальный поиск
• Случайный порядок действий
• Вероятностное сведение к простой задаче
• Случайное блуждание
• Разделяй и властвуй
Верификация программ
Формальная верификация — формальное доказательство соответствия или несоответствия формального предмета верификации его формальному описанию. Предметом выступают алгоритмы, программы и другие доказательства.
Из-за рутинности даже простой формальной верификации и теоретической возможности их полной автоматизации под формальной верификацией обычно подразумевают автоматическую верификацию с помощью программы.
Курс на ВМК МГУ https://www.youtube.com/watch?v=6cT4GkQCzc4
Тестирование программного обеспечения не может доказать, что система, алгоритм или программа не содержит никаких ошибок и дефектов и удовлетворяет определённому свойству. Это может сделать формальная верификация.
Формальные методы
«Использование математического аппарата, реализованного в языках, методах и средствах спецификации и верификации программ»
• Методы формальной спецификации
• Методы формальной верификации:
° Доказательство теорем
° Верификация на моделях
° И другое
Алгоритмы для поисковых систем, квантовые вычисления – к семинару
[1] Гордон Мур (Gordon Moore). День рождения: 03.01.1929 года. Место рождения: Калифорния, Сан-Франциско, США. Гражданство: США
Известный миллиардер и предприниматель. Популярным Гордон Мур стал еще в апреле 1965-го года, когда вышла в свет его печатная работа – «Закон Мура», затрагивающий область полупроводников. Гордон Мур, один из основателей компании Intel, в ходе наблюдений выявил закономерность, согласно которой количество транзисторов, размещаемых на кристалле интегральной схемы, удваивается приблизительно каждые два года. Как следствие, мощность вычислительных устройств возрастает экспоненциально. Правило, согласно которому полупроводниковая промышленность развивается уже почти 50 лет, получило название закона Мура.
В 1975 году он изменил временную составляющую закона и заявил об удвоении количества транзисторов каждые два года. В 2007 году Мур заявил, что закон, очевидно, скоро перестанет действовать из-за атомарной природы вещества и ограничения скорости света
[2] Разумеется, задача останова решается для некоторой МТ и тех или иных данных ее ленты. Одна и та же МТ может заканчивать работу или переходить в бесконечный цикл в зависимости от входных данных.