Необходимые и достаточные условия разделения структур алгоритмов на непересекающиеся множества: полиномиальные и переборные алгоритмы

Полный текст

Введение Проблема , или проблема С. Кука [1; 2], как ее называют, сейчас стоит первой в топ-листе проблем миллениума. Настоящая статья продолжает проект двенадцатилетней давности, сообщение о котором было сделано автором на Международном математическом конгрессе в Хайдарабаде [3]. Отношения между классами и рассматриваются в теории вычислительной сложности (раздел теории вычислений), изучающей ресурсы, необходимые для решения некоторой задачи. Начиная с 1971 г. попыткам ее решения посвящало свое время и усилия множество топологов, создателей алгоритмов и других ученых. Наиболее цитируемым автором по этой теме является А. Разборов [4]. Существует также специальный сайт, посвященный данной проблеме[18]. На нем представлены ссылки на 116 статей, посвященных ее возможному решению. Остановимся лишь на тех статьях, что опубликованы в реферируемых журналах. Одна из первых - статья М. Яннакакиса [5]. В ней нет решения самой проблемы, а только доказывается, что некоторый частный подход к доказательству не работает. Ссылок, посвященных работам, доказывающим, что , несколько больше. В основном они посвящены удачным попыткам создать полиномиальные алгоритмы для некоторых частных случаев. Однако не следует забывать о том, что число массовых задач, которые мы не можем точно решить без применения переборных алгоритмов, ширится с каждым днем. Чуть меньше работ написано в доказательство, что . Практически невозможно тщательно просмотреть все работы (их больше пятидесяти). При этом часть из них базируется на том факте, что встречаются модели (конкретные частные случаи), для которых не могут быть найдены полиномиальные алгоритмы и, соответственно, делается заключение, что . В частности, это работа Р. Валиева [6]. Интересна статья А. Анилла [7], в которой он приходит к доказательству , применяя принцип возрастания энтропии для исследования вычислительной сложности. В работе В. Иванова доказательство основано на более точных оценках нижних границ временной сложности, которые справедливы для всех алгоритмов решения задачи [8]. Самая последняя работа тоже посвящена доказательству [9]; она выложена в интернете, но мнение математического сообщества еще не известно. В некотором числе статей найдены ошибки, в частности в доказательствах Ананда, Делиокара, Виана, Барбоса[19]. Следует отметить, что только доказательство того факта, что , ничего не даст нам для решения задач из практической области. Необходимо разделить задачи по некоторым структурным признакам. Это позволит уже на первом этапе понимать, какой сложности будет алгоритм решения практической задачи. Что самое главное мы знаем и не знаем о проблеме [2]? 1. Знаем: для массовых задач, принадлежащих области , мы можем создавать линейные или нелинейные алгоритмы и получать решения точные или практически точные. 2. Знаем: для массовых задач из области мы можем получить точные решения только с помощью переборных алгоритмов или получать приемлемые решения с помощью нелинейных или экспоненциальных алгоритмов. 3. Не знаем: как определить принадлежность задачи (алгоритма, который ее решает) той или иной области. Представляется, что можно подобраться к решению проблемы с другой стороны, с позиций необходимости решения практических задач. Это позволит применить достижения не только топологии, но также теории графов и теории алгоритмов. 1. Проблема вычислений Итак, в проблеме нас должна интересовать именно возможность вычислений, то есть создание алгоритмов и программ, решающих задачу. При этом не только желательно, но и необходимо, получать экономные алгоритмы и программы. С одной стороны, нужно сокращать временные ресурсы и ресурсы памяти на решения задач из области . С другой стороны, на создание и обслуживание мощных серверов, которые требуются для решения таких задач, уходит много энергетических ресурсов. Количество массовых задач из области множится с каждым годом. Это не только обязательные и жизненно важные задачи, но и развлекательные, такие как игры и социальные сети. Вычисления мы производим с помощью компьютеров. Известно, что компьютер обрабатывает данные или решает только те задачи, для которых можно создать алгоритмы или программы, соответствующие тезису Черча - Тьюринга [10; 11]. Это означает, что программы должны обладать свойством эффективной рекурсивности. Как добиться этого волшебного свойства? Оно предписано принципом нормализации Маркова: «алгоритм должен быть нормальным для того, чтобы его могла обрабатывать машина Тьюринга» [12]. В принципе, все алгоритмы нормализуемы, это подтверждается практикой разработки алгоритмов и программ [12]. Все известные алгоритмические схемы и их композиции (с точностью до эквивалентности) приводят к нормальным алгоритмам. Операторы в алгоритмах реализуются в определенном порядке или в порядке их нумерации. В свою очередь нумерация операторов может быть выполнена, если множество операторов рекурсивно. Однако ни одна из алгоритмических систем не имеет какого-либо наперед заданного способа нумерации операторов [12; 13]. Для создания у алгоритма или программы свойства рекурсивности необходимо расширить алфавит алгоритма, при этом достаточно добавить только одну букву [12]. Известно также, что алгоритмы могут быть визуализированы с помощью графов. Возникает следующий вопрос: как добавить эту букву? Как сделать алгоритм нормальным или обладающим свойством эффективной рекурсивности? Данная задача была решена в 1972 г. в докторской диссертации Л. Малинина, но опубликована только в 2009 г. в книге «Изоморфизм графов в теоремах и алгоритмах» [14]. 2. Расширение теории графов и связь с теорией алгоритмов Обратимся к теории графов. До публикации [14], посвященной решению задачи изоморфизма графов, в теории графов не было решения проблемы четкого определения возможной двойственности графов. Все знают, что реберный граф (граф-схема) всегда имеет двойственный ему вершинный граф (блок-схема). А вот реберный граф далеко не всегда имеет двойственный ему вершинный [15] (рис. 1). илиG(Q, Г) Рис. 1. Необязательность двойственности реберных и вершинных графов Расширение теории графов в [14], позволяет решать подобные задачи. В этой работе проведено широкое исследование двойственности графов и доказаны необходимые и достаточные условия того, чтобы матрица смежности одновременно была бы матрицей смежности как реберного, так и вершинного графа. Следует привести основные теоремы, которые ведут к понятиям двойственности графов и того, как добиться этой двойственности. В основной, или главной, теореме доказываются условия, которым должна отвечать матрица смежности, чтобы граф, соответствующий ей, обладал свойствами двойственности. Теорема 1. «Квазиканоническая матрица смежности»[20]. Теорема о квазиканонической матрице смежности устанавливает необходимые и достаточные условия того, чтобы матрица непосредственных путей имела двойственный характер, то есть могла быть одновременно матрицей смежности вершин графа и матрицей смежности дуг графа при условии, что цикломатические числа этих графов могут быть различны. Теорема была доказана для случая ориентированных графов[21]. Дано: множество и вида , а для графа (рис. 1). Тогда для графа только в том случае, если соблюдаются условия (1): порождает . Минор каждого порождает (1) где , , , , , . Для доказательства теоремы необходимо показать, что матрица , удовлетворяющая условиям (1) и рассматриваемая как матрица - смежности дуг графа , содержит всю информацию для однозначного составления матрицы - матрицы смежности вершин графа . Доказательство приведено в [14]. Цикломатические числа графов всегда удовлетворяют условию (2) Условие (2) отражает определенную вырожденность двойственности (квазидвойственность) квазиканонической матрицы смежности. Кроме того, это условие отражает возможность присутствия в графе сложных вершин. Теорема 1 определяет условия существования квазиканонической матрицы смежности, хотя в практических приложениях такие готовые матрицы могут встречаться лишь случайно. Становится актуальным найти способ преобразования к необходимой форме любой произвольной матрицы непосредственных путей, которая не удовлетворяет требованиям теоремы 1. Преобразование матрицы должно быть таким, чтобы система отношений между исходными элементами оставалась неизменной, то есть преобразование должно быть консервативным по отношению к системе бинарных отношений, заданной на множестве . Преобразование матрицы непосредственных путей к квазиканонической форме. Определения: 1. Под консервативным преобразованием бинарного отношения двух элементов и условимся понимать такое преобразование, которое позволяет вводить или исключать дополнительные элементы из множества , не меняя самого отношения между элементами (qi, qj). Таким может стать преобразование, основанное на свойстве транзитивности бинарного отношения. Например, исходная пара . Пусть элементы и связаны отношением . Примем два условия: и и преобразуем исходное выражение. Получим . Очевидно, что отношения и эквивалентны относительно исходной пары элементов. Поэтому введение элемента в отношение консервативно по отношению к этому отношению в исходной паре . 2. Под -преобразованием матрицы условимся понимать дополнение матрицы одним рядом (строкой и столбцом) при одновременной замене отношения парой бинарных отношений и . Очевидно, что -преобразование консервативно по отношению к бинарному отношению в исходной паре и не нарушает такого критерия структурного подобия, как система бинарных отношений. Теорема 2 «Квазинормализация матрицы бинарных отношений ». Любая матрица непосредственных путей может быть приведена к квазиканонической (квазинормальной) форме , где , если применить -преобразование к тем -элементам матрицы , которые не удовлетворяют требованиям теоремы 1. Доказана сходимость этого преобразования. Доказательство теоремы приведено в [14]. Если соотносить вышесказанное с теорией алгоритмов и тезисом Маркова, то доказанное преобразование автоматически добавляет к алфавиту произвольного алгоритма недостающую букву и делает его нормальным или рекурсивным. Доказано, что алгоритм преобразования (нормализации) является локальным, хотя с помощью некоторых ухищрений он может стать линейным. В частном случае, когда , матрица называется канонической или нормальной. Для случая строгой двойственности (цикломатические числа равны) была доказана теорема 4. Теорема 4 «Каноническая матрица смежности». Пусть исходный связный граф задан матрицей - смежности вершин, которой соответствует квазиканоническая матрица смежности дуг связного реберного графа . Для того чтобы цикломатическое число графа было равно цикломатическому числу исходного графа , необходимо и достаточно, чтобы все вершины полученного графа были простыми. Или, что то же самое, чтобы для всех соблюдались следующие условия: В результате нормализации графа и последующего упорядочения, получаем реберный граф в виде графа Кенига. В [14] доказано, что канонические графы без контуров, полученные в результате нормализации, обладают свойством рекурсивности, которое основано на разбиении канонических матриц смежности на взаимно непересекающиеся подматрицы. Это позволяет строить рекуррентные локальные алгоритмы их упорядочения. Такая возможность сообщает графам (алгоритмам и программам с такой структурой) свойство эффективной рекурсивности (нумерация осуществляется за один проход вдоль множества рядов матрицы). Получение упорядоченного графа Кенига - условие необходимое, но не достаточное. Теоретически мы получаем возможность создать нормальный алгоритм в виде упорядоченного графа Кенига. Однако возможное присутствие в исходном графе контуров и в полученном графе сложных вершин приводит к некоторым проблемам. Цикломатическое число некоторых графов при -преобразовании растет, то есть не совсем понятно, что происходит с графами, в которых есть контуры. Таким образом, возможность автоматизации процесса нормализации алгоритма не решает проблему доказательства . Перед нами встает еще одна проблема - как разделить массовые задачи на классы, чтобы по определенным признакам графа задачи сразу было понятно, к какому классу принадлежит задача: или . Здесь мы сталкиваемся с проблемой сложности графа. Характеристикой сложности графа является цикломатическое число ν. Поэтому следует обратиться к такой характеристике сложности графа, как цикломатическое число, и разобраться является ли оно инвариантом графа и, если является, то в каких случаях. 3. Цикломатическое число и изоморфизм Существует достаточное количество инвариантов, с помощью которых можно сравнивать графы между собой. Среди них есть такая характеристика, как цикломатическое число. Работы О. Оре [15], К. Бержа [16], А.А. Зыкова [17] и Ф. Харари [18-19] говорят о том, что цикломатическое число равно количеству независимых циклов в графе, поэтому оно является характеристикой сложности графа. Для понимания является ли цикломатическое число инвариантом, на который можно положиться, следует обратиться к изучению такого преобразования графов, как превращение вершинного графа в реберный граф, полученного реберного графа снова в вершинный граф и т. д. [14]. Назовем эту операцию конвертированием графов (рис. 2). Рис. 2. Схема преобразования графов Прямым конвертированием назовем операцию построения вершинного графа по реберному графу. Любой ориентированный граф может быть подвергнут операции прямого конвертирования любое число раз. Прямое конвертирование может быть каноническим или квазиканоническим . Обратным конвертированием назовем операцию построения реберного графа по заданному вершинному графу. Граф может быть подвергнут операции обратного конвертирования исключительно в том случае, если матрица смежности его вершин имеет каноническую или квазиканоническую форму. Обе операции конвертирования подробно рассмотрены в [14]. Следует привести только две теоремы. Теорема 9. Если граф в процессе его последовательного прямого конвертирования порождает только канонические графы , то числа вершин этих последовательно получаемых графов определяются линейной зависимостью от номера операции конвертирования , то есть . (4) Теорема 10. Если граф в процессе его последовательного прямого конвертирования порождает и канонические, и квазиканонические графы или только квазиканонические графы, то числа вершин этих последовательно получаемых графов определяются выражением где где . В свою очередь значения определяются структурой исходного графа . Таким образом, показано, что возрастание числа вершин графов, получаемых при последовательном прямом конвертировании, связано с цикломатическим числом и видом конвертирования (каноническое или квазиканоническое), а прирост цикломатического числа при таком конвертировании зависит от структуры графа. Доказанные теоремы [14] показывают, что все ориентированные графы могут быть разбиты на два класса: 1) графы, для которых цикломатическое число всегда является инвариантом прямого конвертирования; 2) графы, для которых цикломатическое число на части шагов или на всех шагах прямого конвертирования не является инвариантом конвертирования. В результате тщательного исследования операций конвертирования и определения свойств структур графов относительно сочетаний различного рода вершин и ребер между ними выявлены необходимые и достаточные признаки графов, которые дали возможность определить необходимые и достаточные признаки для характеристики каждого из классов графов. Доказанные теоремы приведены в [14]. Также рассмотрено более точно понятие пути и контура в ориентированном графе. Реальным процессам могут соответствовать только такие контуры, которые имеют по крайней мере один «вход» и один «выход». Понятие пути и контура уже введено много ранее [15; 16; 18], но в [14] добавлена функция, позволяющая различать пути в графе один от другого. Этот признак определялся с помощью функции сумм степеней вершин, через которые проходит путь. Оказалось, что эти функции можно разделить на два класса, которые описаны в [14]. Соответственно, пути также можно разделить на два класса. Доказанные теоремы приведены в [14]. Изучение различных путей в графах привело к изучению различных комбинаций интервалов между вершинами графа [14]. Вершины графов определялись как положительные (один вход и много выходов) и отрицательные (много входов и один выход). Кроме того, вершины графа также разделялись на простейшие (один вход и один выход), простые (один/несколько входов и несколько/ один выходов) и сложные (несколько входов и несколько выходов). Особенное внимание было обращено на интервал типа , имеющий сложные вершины на обоих концах (рис. 3, а, б). Рис. 3. Преобразование интервала в сложную вершину и появление независимых циклов Главной особенностью этого интервала является наличие отрицательной вершины на входе, а положительной вершины на выходе (рис. 3, б). Такой интервал на первом шаге последовательного конвертирования превращается в сложную вершину (рис. 3, в). Затем, на следующем шаге конвертирования, эта сложная вершина (одна) преобразуется в четыре независимых цикла (рис. 3, г). Появление новых циклов вызывает увеличение цикломатического числа. Увеличение цикломатического числа влечет рост и сложности графа и, соответственно, алгоритма или программы, структура которых определяется структурой графа. В результате дальнейшего исследования оказалось, что ориентированные графы разбиваются на три непересекающихся класса: 1. Голономные графы. Для них цикломатическое число является регулярным инвариантом конвертирования, независимо от числа шагов последовательного конвертирования. Благодаря этому число вершин графов, полученных из исходного графа в результате его последовательного конвертирования, линейно зависит от числа шагов конвертирования. Эти графы не должны содержать контуры и интервалы типа [14]. 2. Ограниченно-гетерономные графы. Такие графы имеют границу гетерономности по числу шагов последовательного конвертирования. До достижения этой границы цикломатическое число не является регулярным инвариантом конвертирования. После достижения этой границы в результате очередного шага конвертирования порождается голономный граф и цикломатическое число становится регулярным инвариантом конвертирования независимо от числа шагов дальнейшего последовательного конвертирования. Структура подобных графов может содержать интервалы типа , но не должна иметь контуры. 3. Прогрессивно-гетерономные графы не имеют границы гетерономности по числу шагов последовательного конвертирования. В результате цикломатическое число прогрессивно-гетерономного графа не становится регулярным инвариантом последовательного конвертирования ни при каком, сколь угодно большом, числе шагов конвертирования. В структуре таких графов присутствуют как контуры, так и интервалы типа . В [14, глава 4] исследовано и представлено в виде таблицы 1 соответствие структур графов и различных блок-схем и граф-схем различных алгоритмов (таблица). Сопоставление графов и алгоритмических схем Вид исходного графа Упорядоченный граф № в табл. 1 [14] Полное наименование алгоритмической схемы Гамильтонов граф при 6 Нормальная одноканальная двухадресная алгоритмическая блок-схема 7 Нормальная одноканальная двухадресная алгоритмическая граф-схема Калужнина 8 Нормальная обыкновенная одноканальная двухадресная алгоритмическая граф-схема 9 Обобщенная нормальная одноканальная двухадресная алгоритмическая граф-схема 10 Нормальная операторная одноканальная двухадресная алгоритмическая граф-схема Произвольный граф при 16 Двухадресная алгоритмическая блок-схема с произвольным числом каналов 17 Нормальная двухадресная алгоритмическая граф-схема Калужнина с произвольным числом каналов 18 Нормальная обыкновенная двухадресная алгоритмическая граф-схема с произвольным числом каналов 19 Обобщенная нормальная двухадресная алгоритмическая граф-схема с произвольным числом каналов 20 Нормальная операторная двухадресная алгоритмическая граф-схема с произвольным числом каналов Произвольный граф 26 -адресная алгоритмическая блок-схема с произвольным числом каналов 27 Нормальная сопряженная -адресная алгоритмическая граф-схема с произвольным числом каналов 28 Нормальная обыкновенная -адресная алгоритмическая граф-схема с произвольным числом каналов 29 Обобщенная нормальная -адресная алгоритмическая граф-схема с произвольным числом каналов 30 Нормальная операторная -адресная алгоритмическая граф-схема с произвольным числом каналов Полный граф 36 Полная алгоритмическая блок-схема 37 Нормальная сопряженная полная алгоритмическая граф-схема 38 Нормальная обыкновенная полная алгоритмическая граф-схема 39 Нормальная обобщенная полная алгоритмическая граф-схема 40 Нормальная операторная полная алгоритмическая граф-схема 41 Нормальная алгоритмическая блок-схема (одноканальная двухадресная) Заключение Итак, множество всех алгоритмов разбивается на три класса (или на три непересекающихся множества) согласно приведенному выше разбиению множества ориентированных графов. После операции нормализации графы, а следовательно, и алгоритмы, имеющие подобную структуру, приобретают свойства рекурсивности. Для голономных графов цикломатическое число становится инвариантом. Алгоритмы, которые после операции нормализации будут иметь подобную структуру, автоматически получают свойство эффективной рекурсивности и будут относиться к области полиномиальных. Ограниченно-гетерономные графы должны быть подвергнуты некоторому (конечному) числу шагов прямого конвертирования, чтобы цикломатическое число стало инвариантом. Алгоритмы, имеющие такую структуру, можно назвать сводимыми к множеству полиномиальных алгоритмов. Прогрессивно-гетерономные графы никогда не будут иметь цикломатическое число инвариантом. Поэтому алгоритмы, имеющие подобную структуру, всегда будут принадлежать к области , хотя в частных случаях операция нормализации может уменьшить число вариантов перебора. И наконец, главное, что можно сказать в доказательство тезиса . Необходимое условие - это получение упорядоченного графа Кенига с помощью нормализации произвольного графа. Достаточное условие: поскольку произвольные графы разделяются на три непересекающихся класса соответственно их структурным характеристикам, то и алгоритмы, которые им соответствуют, также распадаются на три непересекающихся класса, и существует класс алгоритмов, которые не могут быть сведены к классу полиномиальных. Они всегда будут оставаться переборными, то есть -трудными. Все это подтверждает тезис о том, что .

Об авторах

Наталия Леонидовна Малинина

Московский авиационный институт (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: malinina806@gmail.com
ORCID iD: 0000-0003-0116-5889

кандидат физико-математических наук, доцент кафедры 604, аэрокосмический факультет

Российская Федерация, 125993, Москва, Волоколамское шоссе, д. 4

Список литературы