Лекция 13. Сложность вычислений

 

Мало того, что есть алгоритмически неразрешимые задачи

и их бесконечно больше, чем задач алгоритмически разрешимых.

С практической точки зрения нам не легче, если решение

разрешимой задачи мы сможем получим через миллион лет.

Раньше не закончить расчеты... Это трудно-решаемые задачи.

Для нас (простых смертных) такие задачи не отличаются от

задач алгоритмически неразрешимых.

 

А ситуация с такими задачами еще более туманная, чем с

алгоритмической разрешимостью. Пока единственный,

фактически, "железный" аргумент нашей беспомощности, что

задача относится к трудно-решаемым, что никто пока не нашел

для нее легкого решения! Даже американские политики.

 

Ненормальность такой ситуации усугубится, если учесть,

что теоретики рассматривают только конечные дискретные

задачи (задачи либо на поиск оптимума, либо распознавания

[да-нет]), любая из которых (теоретически) может быть решена

хотя бы (за неимением лучшего) простым перебором. Но от

этого не легче, если вспомнить легенду об изобретателе

шахмат, который попросил в награду за первую клеточку

шахматной доски одно зернышко, за вторую два... за 64-ю

клеточку - 2 в 64-ой степени зернышек. Что превышает

зерновые ресурсы Земного шара.

 

Одна из книг по сложности вычислений начиналась с

цитаты из украинского философа Георгия Сковороды:" Спасибо

тебе Господи, что ты создал все нужное нетрудным, а все

трудное - ненужным." Но кажется, что здесь более точной

будет другая мысль из Сковороды, а именно, эпитафия на его

могиле: "Мир ловил меня, но не поймал"... И еще одна мысль

более конкретная мысль уже от современных математиков:

"Сложность становится проблемой века".

 

Из-за огромного количества несущественных особенностей

различных способов (методов, парадигм) вычисления признаки,

которые следовало бы учитывать при определении сложности

вычислений слишком многочисленны и противоречивы. Но в

конечном счете большинство сходится к тому, что все можно

свести к времени (числу элементарных шагов) вычисления и

объему памяти. Более того, многие так и видят при этом в

качестве наилучших моделей - машины Тьюринга.

 

Проблему быстро свели к двум словам и их сочетанию.

Эти слова Polinomial - полиномиальный и

Nondeterministic - недетерминированный.

 

Возьмем большой мешок камней и решим задачу поиска

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

сравнивая с самым большим на данный момент. Исчерпав мешок

мы оставим в руках самый большой камень. Если число камней

мы увеличим в 2 раза, то сложность решения задачи тоже

увеличится (примерно) в два раза. Если возьмем мешок с "n"

то и трудность решения будет пропорциональна "n". Говорят,

что такую задачу можно решить за полиномиальное время. Если

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

нагруженном графе, то это тоже задача полиномиальной

сложности, исходя из формулы для полного графа,

увеличивающая сложность с ростом числа вершин по закону

роста числа ребер, пропорциональному "n квадрат".

 

Однако, есть задачки (для тех же графов), для которых

не найдено простых (полиномиальных) решений. Вторым из

классических примеров таких задач (первый оставим для

финала) служит задача о коммивояжере: Каков минимальный цикл

в нагруженном графе, что при обходе его в каждую вершину

заходим однажды. Для этой задачи есть только "трудные

решения", сложность которых растет по экспоненте (как число

зернышек на шахматной доске).

Но проверить решение такой задачи можно за

полиномиальное время. Вся сложность в том, чтобы знать

"траекторию решения". А вот снять проблему выбора правильной

траектории позволяет недетерминированная машина Тьюринга,

которую можно представить как сколь угодно большое число

(обычных детерминированных) машин, каждая из которых делает

попытку добраться до решения задачи по одной из возможных

траекторий. У кого из читателей фантазия при этом

отказывает, могут просто представить себе бога (говорят -

"оракула"), который подсказывает правильный путь, чтобы не

гонять кучу машин неведомыми тропами. Конечный эффект тот

же.

Таким образом, множество труднорешаемых задач (NP

задач) относится к задачам, решаемым недетерминированной

машиной за полиномиальное время. А проблему сложности

вычислений математики выразили в виде формулы, которую

все-таки приведу из-за ее краткости и "нетрудности" печати:

 

P = NP?

 

Интересно, говорят этой формулой математики, совпадают

ли множество задач, решаемых за полиномиальное время и

множество NP задач? Может просто толку пока не хватает найти

простые решения...

 

Как бы там ни было, а задачи, для которых простые

(полиномиальные) решения пока не найдены, существуют. И чем

дальше, тем больше математики упорствуют в этой

(недоказанной) уверенности. Более того, они коллекционируют

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

менее тысячи. Более того, утверждают, что одни

труднорешаемые задачи сводятся к другим труднорешаемым

задачам. Поэтому даже используется для таких задач термин

"NP-полные" задачи. И делается радикальное заявление: если

хоть для одной NP-полной задачи будет найдено простое

(полиномиальное) решение, тогда простое решение будет

найдено и для всех остальных NP-полных задач. Тогда будет

доказано P=NP и проблема сложности вычислений в этом ее виде

будет закрыта!

 

ПОСЛЕСЛОВИЕ

Самой первой NP-полной задачей стала задача нахождения

клик графа, то есть полных подграфов данного графа с

конкретным числом вершин...

Но в середине семидесятых годов были опубликованы так

называемые "алгоритмы Магу", которые исключили из числа

переборных не только задачи типа "восьми ферзей" (прежде

стандартный полигон для эвристических алгоритмов

"искусственного интеллекта"), но там и клики графа также

находятся с помощью несложных манипуляций на уровне алгебры

высказываний (преобразования выражения к ДНФ), что ни как не

выше полиномиальной сложности.

В хорошем учебнике Новикова Ф.А. "Дискретная математика

для программистов", 2000 года, в самом конце приводятся

рассуждения и алгоритмы для независимых множеств вершин

графа (множеств внутренней устойчивости) и доминирующих

множеств (множеств внешней устойчивости). Витееватые

алгоритмы 70-х годов "с возвратами" (NP сложности) говорят о

том, что автор учебника не знает про алгориртмы Магу,

которые имеют полиномиальную сложность (или не считает их

корректными и достойными упоминания).

Мало радости признаваться в собственной бестолковости и

некомпетентности, но проблема трудно решаемых задач для меня

существует в несколько извращенном виде.

 

 

Лекция МАГИЧЕСКАЯ (добавленная) Долго не решался дополнить "Дискретную математику"лекцией по графам. Графы (от слова "графический") без формули рисунков - это уж совсем сюр. Но хотелось бы рассказать об"алгоритмах Магу" (Maghout K.), которые можно считатьреволюционными (или шарлатанством?) для теории графов. Рассмотрим далее алгоритмы Магу, позволяющие решатьзнаменитые задачи "о ферзях": - Сколько (и как) ферзей можно расставить на шахматнойдоске, чтобы ни один не был под боем? Интересны максимальныенаборы. (Множества внутренней устойчивости графа [из 64вершин]). - Сколько (и как) необходимо расставить ферзей, чтобывсе поля доски оказались под боем? Интересуют минимальныенаборы. (Множества внешней устойчивости графа [из 64вершин]). А также алгоритм решения задачи о нахождении кликиграфа, знаменитой, кроме прочего тем, что с нее начиналась"Теория труднорешаемых задач" - она была в числе первыхнескольких задач объявленных, NP-полными! Представим себе произвольный граф, состоящий измножества вершин и множества дуг (стрелок). соединяющихнекоторые вершины. Так в задаче о ферзях это будет граф из64 вершин, соответствующих клеточкам шахматной доски истрелок, которые из каждой клеточки направлены к темклеточкам, которые будут под боем, если в рассматриваемойклеточке стоит ферзь. (Не следует пугаться жуткой картинки -никто не собирается ее рисовать). Для вычислений на компьютере такой граф удобнопредставить в виде "матрицы смежности", где по вертикали игоризонтали перечислены все 64 клеточки, и если стрелка идетиз вершины А в вершину В, то на пересечении строки А состолбцом В ставится единичка. Для нахождения множества внутренней устойчивости (тоесть расстановки максимального количества ферзей), то естьмаксимального множества несмежных вершин (не имеющих междусобой стрелок), запишем "УСЛОВИЕ НЕСОВМЕСТИМОСТИ". Выпишемпарные дизъюнкции соответствующие единицам матрицы. Каждаяединица говорит о наличии стрелки из одной вершины в другую,а значит, либо вершина А, либо вершина В, либо обеодновременно не могут входить в множество несмежных вершин(логическое "ИЛИ"). Далее свяжем конъюнкцией все этидизъюнкции, поскольку все условия несовместимости должнывыполняться одновременно (логическое "И"). Приведем полученное выражение к ДНФ перемножениемпарных дизъюнкций (дистрибутивный закон) и выполнив всепоглощения. В результате получим минимальные конъюнкции,соответствующие несовместимым множествам вершин. Выписав длякаждой конъюнкции вершины из полного списка, получиммаксимальные множества несмежных между собой вершин. То есть "творческая" задача, считавшаяся сравнительнонедавно тестовой для систем искусственного интеллекта,решена (элементарно). Для решения второй задачи - минимального количествафигур, обеспечивающих контроль над всем полем, то есть длянахождения множества внешней устойчивости дадим егоопределение. Множество вершин графа называется внешнеустойчивым для графа если вершины в него входят, либо имеютстрелки в это множество. То есть, либо клеточка занятафигурой, либо она под боем от какой-то фигуры. Запишем "УСЛОВИЕ ВХОЖДЕНИЯ". Для каждой строки матрицынапишем дизъюнкцию вершин, включающую вершину,соответствующую строке и всем единичкам из этой строки. Тоесть, либо вершина, соответствующая этой строке должнавходить в это множество, либо должна входить хотя бы одна извершин, которые имеют стрелки от этой вершины (логическое"ИЛИ"). парные дизъюнкции соответствующие единицам матрицы. Каждаяединица говорит о наличии стрелки из одной вершины в другую,а значит, либо вершина А, либо вершина В, либо обеодновременно не могут входить в множество несмежных вершин(логическое "ИЛИ"). Далее свяжем конъюнкцией все этидизъюнкции, поскольку все условия несовместимости должнывыполняться одновременно (логическое "И"). Приведем полученное выражение к ДНФ перемножениемдизъюнкций (дистрибутивный закон) и выполним все поглощения.В результате получим максимальные конъюнкции,соответствующие множествам внутренне устойчивых вершин. Задачу о клике рассмотрим для неориентированного графа,то есть для графа, у которого вершины соединяются ребрами(линиями без стрелок). Полным называется граф, у которогокаждая вершина соединена ребрами со всеми остальными.Кликой называется максимальный полный подграф данного графа. Для исследуемого графа строим граф-дополнение. То естьграф с теми же вершинами, но ребрами, которых нет в исходномграфе. И вот для этого графа-дополнения находим максимальныемножества несмежных вершин (см. первый алгоритм Магу).Тонкость только в том, что для неориентированного графа вусловия несовместимости наряду с единичкой "А-В" попадет иединичка "В-А" (коль ребро в отличие от дуги-стрелки как бысоответствует двунаправленной стрелке). Получивмаксимальные множества внутренней устойчивости (множестванесмежных вершин графа-дополнения) вы тем самым получилмаксимальные множества смежных вершин исходного графа.Максимальный(ные) из них и есть клика. Задача решается элементарно. А ведь с нее, фактически)начиналась теория труднорешаемых (NP-полных) задач.