5.6. Сложность задачи достижимости

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

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

В 1977 г. на Симпозиуме ACM по теории вычислений было представлено «доказательство» разрешимости задачи достижимости [264]. Однако это «доказательство» имело несколько серьезных огрехов, а попытки устранить их, чтобы получить корректное доказательство, не дали положительных результатов. И все же превалирует ощущение, что задача достижимости разрешима, что алгоритм ее решения существует, и со временем он будет найден.

Если предположить, что алгоритм решения задачи достижимости существует, то можно утверждать, что он очень сложный. Уместен вопрос: какова сложность алгоритма решения задачи достижимости? Некоторые оценки его сложности можно получить, не ссылаясь на конкретный алгоритм.

Липтон показал, что любой алгоритм, решающий задачу достижимости, потребует по крайней мере экспоненциального объема памяти и экспоненциального времени решения. Экспонента от это мера размерности задачи, и случай Липтона отражает число позиций и их взаимосвязи с переходами.

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

Доказательство Липтона основано на возможности построения сети, пересчитывающей до фишек только в позициях. Для проверки позиции на нуль необходимо наложить на сеть некоторые ограничения. Можно предложить, разумеется, сети Петри, для которых непосредственная проверка нуля невозможна. Тем не менее для осуществления возможности проверки нуля используется общий метод, заключающийся в использовании таких двух позиций что является константой. Если мы знаем, что тогда можно проверить, является ли нулем, проверяя, имеет ли фишек; если имеет фишек, то имеет нуль фишек, и наоборот. То, что маркировка позиции не нулевая, можно проверить с помощью петли. Заметим, что для поддержания способности проверки позиции на нуль необходимо поддерживать свойство постоянности т. е. сеть должна быть сохраняющей по крайней мере по отношению к этим двум позициям.

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

Эти простые сети позволили Липтону построить сеть, которая для данного может порождать точно фишек в позиции с нулем фишек в и в которой можно проверить на равенство нулю. Число используемых позиций равно произведению константы на Существование сети Петри, подобной этой, показывает, что задача достижимости требует по крайней мере экспоненциальных времени и памяти, и, следовательно, затраты на вычисление ее решения слишком велики.

Рис. 5.15. Проверка маркировки ограниченной позиции на совпадение с 0, 1 или 2. Все переходы должны поддерживать сумму маркировки.

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

Рис. 5.16. Вид сетей Петри, используемых Липтоном для построения больших сетей, допускающих проверку боль ше-го счетчика на нуль.

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

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

Последний результат Мэйра [183] показал, что задачи подмножества и равенства для множеств достижимости ограниченных сетей Петри имеют сложность непримитивной рекурсии. Это означает, что некоторые задачи для сетей Петри, несмотря на разрешимость, требуют на вычисление значительных затрат.

Упражнения

(см. скан)

5.7. Замечания к литературе

Теория вычислимости — начало теории вычислений — была развита из работ Тьюринга, Клини, Гёделя и Чёрча. Девис [69] и Минский [200] предлагают хорошие введения в нее. Карп [146] показал, как сводимость можно использовать для получения результатов по разрешимости и сложности.

Задача достижимости впервые поставлена в [148], как исследовательский вопрос она ставилась в [213]. Предварительные результаты сообщены в [299, 129], но они не обобщены.

Большинство результатов, изложенных в этой главе, взяты из работ Хэка [111, 113, 114, 116]. Хзк - один из основных исследователей по задачам разрешимости в сетях Петри. В числе других работ по свойствам разрешимости [13, 183]. Результаты по сложности получены Липтоном [176], Ракоффом [233] и Джоунсом и др. [144]. Некоторые работы [47, 48] косвенно связаны с сетями Петри.

5.8. Темы для дальнейшего изучения

I. Сеть Петри называется обратимой, если для каждого перехода найдется переход такой, что

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

обратном порядке их дополнительных переходов. Установлено [129], что для обратимых сетей Петри задачи достижимости и покрываемости разрешимы. Этот результат основан на работах по коммутативным полугруппам [47]. Установите на основе взаимосвязи между обратимыми сетями Петри и коммутативными полугруппами разрешимость достижимости и эквивалентности для обратимых сетей Петри. Для развития теории обратимых сетей Петри рассмотрите также задачу активности, вопросы сложности и языки обратимых сетей Петри.

2. Представляется весьма полезной связь сетей Петри с арифметикой Пресбюргера. Арифметика Пресбюргера — это арифметическая теория, использующая сложение и вычитание целых чисел. Показано, что можно установить истинность или ложность всех высказываний, образованных из кванторов первого порядка, равенства, операций сложения и вычитания и целых чисел. Первоначальное доказательство было представлено в [252] и использовалось в качестве основы для автоматического доказательства теорем [68, 55]. Связь арифметики Пресбюргера с полулинейными множествами упоминалась в [99, 101], а взаимосвязь полулинейных множеств с достижимостью — в [299, 61, 161, 129, 137]. Предположительно арифметику Пресбюргера можно использовать для решения задач анализа сетей Петри. Исследуйте этот вопрос.