Класс задач П называется полиномиально разрешимым, если существует машина Тьюринга Т, решающая задачи г G П за полиномиальное время.

Совокупность (юхассов) задач, разрешимых за полиномиальное время, называем классом задач Р.

5.2.2. Класс задач NP

Массовая задача П принадлежит классу NP, если в случае ответа «ДА» для Задачи Z существует слово c{Z) длины 0{p{\a{Z)\)) такое, что задача {Z,c{Z)) принадлежит классу Р. Слово c{Z) называется удостоверением, или догадкой, задачи Z. Его наличие позволяет проверить принадлежность задачи Z классу Р.

К примеру, выполнимость формулы A{Xi,...,Xn) проверяется, если кроме самой формулы дан конкретный набор переменных Xi,Xi - догадка, способствующая установлению выпсишимости формулы Л.

5.2.3. Недетерминированная машина Тьюринга

Определим класс NP в терминах недетерминированной машины Тьюринга [34].

Недетерминированная машина Тьюринга пТ - это машина Тьюринга с дополнительным угадывающим модулем (УМ), который способен записывать на ленту слова из внепшего алфавита А, к когорому добавлен знак раздела *.

Поскольку изучается массовая задача, то внутренний алфавит Q содержит буквы qy и qn, соответствующие ответам «ДА» и «НЕТ».

Машина осуществляет работу следующим образом:

• Стадия 1 (Угадывание). На ленте записано аюво a{Z) в алфавите А - код задачи Z, начиная с ячейки с номером 1 (и вправо). Левее, в ячейке О, записан знак раздела *. УМ, просматривая ячейку за ячейкой, идя влево после ячейки О, пишет произвольное слово c(Z). Если УМ останавливается, то происходит переход ко второй стадии работы машины. При этом имеем состояние машины

c{Z)*qia{Z). (5.1)

• Стадия 2 (Решение). На этой стадии машина работает как обычн£1я машина Тьюринга, стартуя с начального состояния (5.1). Если через конечное число шагов она придет к состоянию, содержащему qy, то говорят, что она принимает состояние (5.1). Недетерминированная машина Тьюринга принимает слово a{Z), если существует оюво c{Z) такое, что машиной принимается состояние (5.1).

Время работы недетерминированной машины Тьюринга пТ-это чиою

t{Z)=ti{Z)-\-t2{Z),

если принимается аюво a{Z). Здесь

ti{Z) - время работы на 1-й стадии, т.е. ti{Z) = \c{Z)\;

tiZ) - время работы на 2-й стадии, т.е. tiZ) = t!£{c{Z) * a{Z)).

Пусть

*птМ = ,,--=„*пТ()- (5-2)

Недетерминированная машина Тьюринга решает массовую задачу П за полиномиальное время, если

t<{n) = 0{р{п))

для некоторого полинома р(п).

Класс NP - это множество задач, для которых существует недетерминированно машина Тьюринга, принимающей за полиномиальное время те и только те аюва, которые соответствуют индивидуальным Задачам с ответом «ДА*.

Ясно, что

Р с NP.

Теорема 5.1. Если задача П G NP, то существует полином р{п) такой, что задача П может быть решена с помощью (детерминистского) алгоритма со сложностью 0(2""), п - размер задачи П.

Доказательство дано в [34].

5.3. О понятии сложности

5.3.1. Три типа сложности

Сложность задания (записи) обоекта - это кратчайшая длина программы, наименьшее число команд, которое должно быть введено в идеализированную машину для того, чтобы она могла решить любую задачу некоторого класса задач, т.е. предъявить объект, считающийся ее решением [1, с.50]. Как правило, в этот класс вю1ючак>т однотипные задачи, поэтому такой Ю1асс задач называют массовой задачей.

Однако может оказаться, что достаточно простая программа, с помощью которой решается некоторм массовм задача, может привести к большому объему вычислений. Следовательно, полезно ввести понятие сложность вычислений. К примеру, под сложностью алгоритмов теории чисел понимается ксишчество арифметических Операций (аюжений, вычитаний, умножений и делений без остатка), необходимых для выпошения всех действий, предписанных алгоритмом [48, с.91].

Таким образом, следует различать три типа понятия «сложность» [1, с.50]:

• Сложность задания (описания) обеекта.

• Сложность вычисления (функционирования).

• Конструктивно-энергетическая сложность.

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

5.3.2. Четыре категории чисел но Колмогорову

Обратим внимание на то, что в понятие сложности входит чиоювая характеристика (длина программы, число операций и т.д.). Изучая эту сторону понятия сложности, А.Н.Колмогоров пришел к представлению о наличии четырех категорий чисел: малых, средних, больших и сверхбольших [15]: