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

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

N= Kx 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].