Распознавание слов языка является формальным способом представле-
ния задачи (проблемы), а решение задачи – это представление того, что делает компьютер. Машина Тьюринга является формальной моделью компьютера. Легко понять, почему существуют задачи, не решаемые компьютером. Множество языков над различными алфавитами несчетно, с другой стороны, программы, будучи конечными цепочками в конечном алфавите, допускают нумерацию натуральными числами, т.е. образуют счетное множество. Таким образом проблем больше, чем программ.
В математической логике уточняются понятия разрешимых и неразрешимых проблем и методы их сводимости друг к другу, чтобы через неразрешимость одной проблемы доказывать неразрешимость той, к которой сводится данная неразрешимая проблема. Однако даже среди разрешимых проблем выделяются так называемые труднорешаемые задачи. В вычислительной практике более существенна как раз эта сторона алгоритмических проблем – их внутренняя сложность и сложность реализующих их вычислительных моделей.
Известны три способа определения сложности вычислений:
- Первый базируется на поиске оценок сложности, не зависящих от выбора вычислительной модели, т.е. на внутренней сложности алгоритма.
- На втором пути исследуются параметры вычислительных моделей,
например, число лент многоленточных машин Тьюринга или мощности их языков.
- Третий путь аксиоматический, здесь Блюмом были предложены аксиомы меры сложности. Из доказанных в этой теории теорем следует, что существуют вычислимые функции, не имеющие “наилучшей ” программы вычислений, а в классе примитивно рекурсивных функций есть подкласс элементарных функций, которые можно получить простой итерацией операций обычной арифметики.
Практически разрешимые проблемы входят в сложностной класс P, полиномиально разрешимых задач, а имеющие более чем полиномиальную сложность, принадлежат классу NP. В классе NP, в свою очередь, выделяется подкласс NP – полных проблем, называемых труднорешаемыми. Для доказательства принадлежности проблемы к классу NP исполь- зуется известный в логике метод сведения новой проблемы P2 к известной труднорешаемой проблеме P1 из NP. Однако методы сведения, используемые в логике и в теории сложности различаются как принципа- ми, на которых они базируются, так и ограничениями на сводящий алгоритм. Доказательство неразрешимости проблем основано на общих математических принципах: понятии алгоритма и формальной системы. Утверждение о труднорешаемости проблемы базируется на недоказанном принципе, что P ¹ NP и факте, что для всех труднорешаемых проблем не известно ни одной детерминированной машины Тьюринга, решающей эту проблему за полиномиальное время. Что касается сводящего алгоритма, то для доказательства труднорешаемости задачи уже недостаточно просто наличия сводящего алгоритма, но сам сводящий алгоритм должен уже иметь полиномиальную сложность, чтобы не переносить свою труднорешаемость на проблему, к которой с его помощью сводится известная труднорешаемая проблема.
В качестве вычислительной модели используется машина Тьюринга или адресная РАМ-машина [1]. Наиболее употребимые меры сложности
- время работы машины M (число шагов, переходов) на входе w до окончания работы, обозначается tM (n), где n – длина слова w;
- емкость, обозначается SM (n), т.е. максимальная длина используемого участка ленты на всех рабочих лентах, по всем моментам вычисления. Время вычисления большинства интересных функций на базе известных алгоритмов имеет полиномиальную сложность. Если вычисление не заканчивается, время и емкость считаются бесконечными.
Сложностной класс P определим как класс, содержащий те и только те функции от длины входа, которые вычислимы за полиномиальное время на детерминированной машине Тьюринга. Наряду с обычными детерминированными алгоритмами применяются вероятностные (рандо- мизированные) алгоритмы, программа которых предуссматривает специальную команду “обратись к жребию”. От результата обращения к жребию зависит, какая команда будет выполняться на следующем шаге. Сам жребий можно представить себе как генератор псевдослучайной последовательности (независимых и равновероятных) символов, чаще всего двубуквенного алфавита. На вероятностных машинах можно вычислять те и только те функции, которые вычислимы на детерминированных машинах. Теория показывает, что переход от детерминированной машины к вероятностной для некоторых важных функций дает значительную экономию вычислительных ресурсов (времени, емкости). Остается неизвестным, есть ли такие нетривиальные функции, где такой экономии получить нельзя.
Оценки сложности вычислений как для вероятностных, так и для детерминированных машин, носят асимптотический характер. Выигрыш в сложности, достигаемый при переходе от “худших” алгоритмов к “луч -шим”, также оценивается асимптотически. К сожалению, эти оценки действуют с мультипликативными константами “с” и, начиная с некоторого “n 0”. Константы могут быть столь велики, что для входов реальной длины асимптотически худший вариант может работать лучше асимптотически лучшего.
Второй сложностной класс NP есть класс множеств, распознаваемых за полиномиальное время на недетерминированной машине Тьюринга. Предположение, что P¹ NP, может быть подтверждено тем, что ни для одной проблемы из класса NP до сих пор не найден алгоритм полиномиальной сложности. В противном случае, используя полиномиальную сводимость проблем из класса NP, можно было бы доказать равенство классов P и NP. Наиболее труднорешаемые задачи в классе NP - это класс NP-полных проблем.
Вопросы сложности вычислений лежат в основе криптографических методов. Надежность шифров базируется на уверенности, что дешифрование является труднорешаемой задачей, т.е. отсутствует полиномиальный алгоритм, который решает задачу, стоящую перед противником. Но здесь возникает серьезное препятствие в невозможности найти нижние оценки сложности для конкретных задач данного класса.
Так безопасность шифров, основанных на RSA-схеме, гарантируется невозможностью разложить целое, равное произведению двух больших простых чисел, за полиномиальное время. Проблема принадлежит классу NP. Некоторой гарантией безопасности было бы принадлежность языка простых чисел или языка составных чисел к NP-полным классам, но равенство NP=co-NP сомнительно. Более того, доказано, что язык простых чисел принадлежит классу RP, так что NP-полнота языка простых чисел приводила бы к равенству RP=NP, что тоже маловероятно.
Что касается вопроса о достаточности предположения P ¹ NP при выборе NP- полной задачи для построения на ее основе криптографической схемы, то возникает уже упоминавшаяся проблема асимптотического характера оценки сложности. Любая NP - полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входов. Иными словами, в определении класса NP заложена мера сложности в “худшем случае”. Для стойкости же криптографической схемы необходимо, чтобы задача противника была сложной “почти всюду”.
