ГЛАВА 5. СЛОЖНОСТЬ И РАЗРЕШИМОСТЬ

В четвертой главе было представлено множество задач теории сетей Петри. Эти задачи касаются различных свойств структуры и поведения сетей Петри.

Были представлены и два метода решения: подход дерева достижимости и подход матричных уравнений. Эти методы позволяют определить свойства безопасности, ограниченности, сохранения и покрываемости для сетей Петри. Кроме того, установлены необходимые условия для достижимости. Однако эти методы анализа недостаточны для решения некоторых других задач, в частности активности, достижимости и эквивалентности. В этой главе мы изучим эти задачи с целью или найти их решения, или по крайней мере узнать больше о свойствах сетей Петри.

5.1. Сводимость задач анализа

Мы будем использовать фундаментальное понятие сводимости [146]. Решение задачи подразумевает сведение ее к другой задаче, способ решения которой уже известен. В предыдущей главе, например, задача определения того, является ли сеть Петри сохраняющей, сводилась к решению системы линейных уравнений. Задача решения системы линейных уравнений в свою очередь сводится к определенной последовательности арифметических операций (сложение, вычитание, умножение, деление и сравнение). Таким образом, поскольку арифметические операции выполнить можно, сохранение может быть определено.

Другой пример связан с задачей равенства и задачей подмножества для множеств достижимости.

Определение 5.1. Задача равенства. Выполняется ли для двух данных маркированных сетей Петри с маркировкой с маркировкой равенство

Определение 5.2. Задача подмножества. Выполняется ли для двух данных маркированных сетей Петри с маркировкой с маркировкой соотношение

Эти задачи могут оказаться очень важными для определения, является ли сеть Петри оптимизируемой или сравнимы ли сети двух систем. Заметим, что если можно найти решение задачи, подмножества, то задача равенства также решается. Если необходимо

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

При рассмотрении задач анализа и сводимости важно принимать во внимание следующие два соображения. Во-первых, пытаясь найти решение, необходимо учитывать возможность того, что задача не имеет метода решения, т. е. неразрешима. Во-вторых, если метод решения существует, мы должны оценить его стоимость: как много времени и памяти требуется для решения? Для того чтобы применение сетей Петри расширялось, задачи анализа должны решаться, а алгоритмы, осуществляющие решение, должны быть не слишком дороги в смысле времени и памяти ЭВМ.

Сводимость играет большую роль для обеих из указанных проблем. Сводимость задач обычно используется для того, чтобы показать, разрешима ли задача или неразрешима. Наш подход к теории разрешимости [69, 200] основан главным образом на работах Тьюринга и его модели вычислений — машине Тьюринга. Значение машины Тьюринга состоит в том, что она служит разумным представлением вычислительной машины, и можно показать, что не существует алгоритма, который бы решал определенные проблемы машины Тьюринга, в частности проблему остановки. На основе этого был найден ряд неразрешимых задач. И важность этой теории в том, что невозможно создать программу для ЭВМ, которая бы решала эти задачи. Следовательно, для целей практического анализа необходимо избежать этих неразрешимых задач, иначе вопросы анализа не получат ответа.

(Здесь важно подчеркнуть, что неразрешимые задачи порождают вопросы, на которые не просто нет ответа, но его и не может быть. Вопросы, на которые нет ответа, еще могут его получить; это значит, что ответ еще никто не нашел, но он существует. Известным примером является большая теорема Ферма: имеет ли решение уравнение для в классе целых чисел х, у, z? Этот вопрос не получил ответа, но он его имеет. Ответом служит либо "нет". Одним способом получения ответа на вопрос является поиск чисел удовлетворяющих условиям теоремы. Другим будет доказательство (логический вывод) того, что гаких не существует. Никто еще не сделал этого.

Однако предположим, что задача неразрешима. Тогда невозможно было бы определить, существуют ли решающие уравнение. Это означало бы, что мы не могли логически вывести их несуществование из аксиом математики и не могли получить х,у,

которые были бы решением уравнения. Но если мы не можем получить тогда они не должны существовать. Если же они существуют, мы можем найти их с помощью ЭВМ. Но если не существуют, ответом на вопрос будет «нет», и, следовательно, мы разрешили его. Это противоречит нашему предположению о том, что вопрос неразрешим, следовательно, он разрешим.)

Теперь допустим, что задача А сводима к задаче В: конкретную задачу А можно перевести в конкретную задачу В. Если задача В разрешима, то разрешима и задача а алгоритм решения задачи В можно применить к решению задачи А. Конкретную задачу А можно решить, преобразуя ее в конкретную задачу В и применяя к ней алгоритм решения задачи В. Таким образом, если задача А сводится к задаче В и задача В разрешима, то разрешима и задача

Обратное также верно: если задача А сводится к задаче В и задача А неразрешима, то неразрешима и задача если бы задача В была разрешима, то описанная выше процедура была бы методом решения задачи что противоречит ее неразрешимости. Эти два факта положены в основу большинства методов определения разрешимости. Для того чтобы показать, что задача разрешима, сводят ее к задаче, известной как разрешимая; а для того чтобы показать, что задача неразрешима, сводят к ней задачу, которая известна как неразрешимая.

Мы также будем широко использовать этот подход для сокращения объема работы, которую нам необходимо выполнить. Например, вследствие того, что задача равенства для множеств достижимости сводится к задаче подмножества, мы хотим найти либо 1) процедуру решения задачи подмножества, либо 2) доказательство того, что задача равенства неразрешима. Если мы сможем выполнить 1), то будем иметь метод решения обеих задач, если выполним 2), будем знать, что обе задачи неразрешимы.

В некоторых случаях мы сможем достичь даже большего. Две задачи называются эквивалентными, если они взаимно сводимы. Другими словами, задача А эквивалентна задаче В, если задача А сводится к задаче В, а задача В сводится к задаче А. В этом случае или обе задачи разрешимы, или обе неразрешимы, и мы можем рассматривать любую из них. (Заметим, что в общем случае это неверно. Например, если бы мы показали, что задача подмножества для множеств достижимости неразрешима, это не сказало бы нам ничего о разрешимости или неразрешимости задачи равенства.)

Второе соображение по исследованию задач анализа заключается в том, что если метод решения существует, то он должен быть разумноэффективным. Это означает, что количества времени и памяти, требуемые алгоритмом для решения конкретной задачи, не должны быть чрезмерными. Исследование стоимости выполнения алгоритма — это часть теории сложности. Теория сложности имеет дело

с количествами времени и памяти, необходимыми для решения задачи. Очевидно, что количества времени и памяти не постоянны, а изменяются в зависимости от размерности решаемой задачи. Для сетей Петри временные и емкостные затраты будут, по-видимому, функцией от числа позиций и переходов. Другими факторами, влияющими на время и память, будут число фишек в начальной маркировке и число входов и выходов для каждого перехода и позиции (число дуг в графе).

Требуемые время и память будут изменяться от одной задачи к другой. Поэтому оценки сложности алгоритма могут быть даны для наилучшего случая (нижняя граница) или наихудшего случая (верхняя граница). Поскольку не известно, относится данный пример задачи к наилучшему или наихудшему случаю, обычно принимается наихудший случай, и сложность алгоритма — это временные и емкостные затраты в худшем случае как функция от размерности задачи.

Анализ сложности касается главным образом сложности задачи, а не конкретных деталей реализации какого-либо частного алгоритма. Поэтому в теории сложности игнорируются константы. Сложность задачи размерности определяют порядком или или допуская меньшие члены и постоянные сомножители. Особенно важны два общих класса алгоритмов: имеющих полиномиальную сложность ) и имеющих неполиномиальную сложность (в частности, экспоненциальную, и факториальную,

Анализ сложности обычно применяют к конкретным алгоритмам, но его можно применить также и к общим задачам. В этом случае определяется нижняя оценка сложности из всех алгоритмов, решающих задачу. Это обеспечивает значение сложности, не зависящее от алгоритма, и, кроме того, может оказаться полезным в доказательстве того, что данный алгоритм оптимален (с точностью до константы), и в определении случаев, когда дальнейшая работа может привести к лучшему алгоритму решения задачи. Например, хорошо известно, что сортировка чисел имеет сложность Следовательно, алгоритмы сложности нельзя значительно улучшить (в асимптотически худшем случае).

При определении сложности может быть полезно сведение одной задачи к другой. Если задачу А можно свести к задаче имеет сложность то сложность А — это, самое большее, сложность В плюс стоимость преобразования из (помня, что в результате перевода размерность задачи может измениться.) Сложность преобразования является, как правило, константой или линейной функцией и поэтому часто игнорируется. Следовательно, сведение задачи А к задаче В дает или верхнюю границу сложности А (если известна сложность В), или нижнюю границу сложности В (если известна сложность А). Используя снова в качестве примера задачи равенства и подмножества, получаем, что объем

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

Эти два свойства задач анализа сетей Петри — разрешимость и сложность — имеют первостепенную важность для использования сетей Петри. В этой главе представляются некоторые известные результаты. Один из используемых методов — сведение одной задачи анализа Петри к другой.