Новый ум короля: О компьютерах, мышлении и законах физики

Конечно, число «шагов» зависит от типа вычислительной машины, на которой применяется алгоритм. Если эта машина принадлежит классу машин Тьюринга, описанному в главе 2, у которых есть только одна лента — что довольно неэффективно — то число N может расти еще быстрее (или, эквивалентно, машина будет работать медленнее), чем в случае с двумя и более лентами. Чтобы избежать этих неопределенностей, вводится широкая классификация всех возможных зависимостей N( n), так что, независимо от типа используемой машины Тьюринга, величина темпов роста N будет всегда попадать в одну и ту же категорию. Одна из таких категорий, известная как Р(от названия «полиномиальное время»), включает все темпы роста, которые являются фиксированными кратными n или n², n³, n⁴, n⁵…. [91]. Это означает, что для любой задачи, попадающей в эту категорию Р(под «задачей» здесь фактически понимается семейство задач, решаемых с помощью единого алгоритма), будет справедлива оценка

N≤ K x n^r

где К и r— константы, не зависящие от n. То есть N не может быть больше, чем число, кратное n в некоторой фиксированной степени.

Простой, пример задачи, безусловно относящейся к Р, — перемножение двух чисел. Чтобы объяснить это, я должен сначала описать, как число n характеризует размер двух чисел, которые надо перемножить. Мы можем принять, что оба числа представлены в двоичной записи и что n/ 2— это просто количество бинарных разрядов в каждом из чисел, так что общее число цифр(то есть битов) у обоих равно n. (Если одно из чисел длиннее другого, то мы можем записать более короткое, начав с дополнительной последовательности нулей, тем самым выровняв их по длине.) Например, если n= 14, мы бы могли рассмотреть произведение

1011010 x 0011011,

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

учитывая, что в двоичной системе 0x0=0, 0x1=0, 1x0=0, 1x1=1, 0+0=0, 0+1=1, 1+0=1, 1 + 1 = 10. Число отдельных двоичных перемножений равно (n/2) х (n/2) = n ²/4, а число отдельных двоичных сложений может доходить до n ²/4 — n/2 (включая перенос). Это дает n ²/2 — n/2 отдельных арифметических операций — и мы должны еще учесть несколько дополнительных логических шагов, которые задействованы в операциях переноса. Тогда общее число шагов, игнорируя члены более низкого порядка, равно по существу N= п²/2, что, очевидно, является полиномом [92].

В общем случае, мы полагаем «размер»  n задачи из некоторого класса равным полному количеству двоичных цифр (или битов), необходимых для задания свободных входных данных в задаче указанного размера. Другими словами, для произвольного размера n задача может иметь до 2 ⁿ различных вариантов (ибо для каждой из цифр имеется две возможности — 0 или 1, — а общее количество цифр равно n), и все они должны одинаково обрабатываться алгоритмом не более, чем за N шагов.

Существует масса примеров (классов) задач, которые не «принадлежат» множеству Р. Например, чтобы вычислить  ₂ 2 ^r для заданного натурального r, нам только для записи конечного ответа потребуется около 2ⁿ шагов (где n— число цифр в двоичной записи r), не говоря даже о самом вычислении. Операция по вычислению  потребует уже  ₂ 2 ⁿ шагов для записи и так далее. Значения этих выражений намного превосходят те, которые дают полиномы для тех же n, и, следовательно, не могут принадлежать Р.

Больший интерес представляют задачи, в которых ответ может быть записан и даже проверен на верность за «полиномиальное» время. Есть очень важная категория (алгоритмически решаемых классов) проблем, обладающих таким свойством. Их называют NP- задачами(классом задач). Точнее, если некоторая задача из класса NP имеет решение, то алгоритм позволит получить это решение, которое затем может быть проверено за «полиномиальное» время. Если же задача не имеет решения, то алгоритм сообщит об этом, но при этом не оговаривается необходимость проверки этого факта за «полиномиальное» или какое бы то ни было время [93].