Сложность вычислений

Конкретизация понятия алгоритма

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

1. l-нотация.

2. Рекурсивные функции.

3. Машины Тьюринга.

4. Нормальные алгорифмы Маркова.

В связи с этим задача переформулируется следующим образом:

Задача алгоритмически разрешима, если для нее можно построить l-нотацию (рекурсивную функцию, машину Тьюринга, нормальный алгорифм Маркова). И наоборот, если невозможно построить l-нотацию и т.п., то задача алгоритмически неразрешима. Важно, что все конкретизации алгоритма равнообъемны, то есть одновременно могут или не могут быть построены для исследуемых задач.

В качестве небольшого, но важного отступления отметим в данном разделе, что

алгоритмическая разрешимость еще не означает, что задача может быть реально решена.

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

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

Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие «абстрактному» объему исходных данных (n)

Три строки соответствуют различным «функциям сложности вычислений». В таблице приведены времена вычислений в зависимости от объема данных и сложности вычислений (F).

n F
n	10^-5cек	30*10^-6 cек.	30*10^-6 cек.	30*10^-6 cек.
n⁵	0.1 cек.	24.3 cек.	5.2 мин.	13 мин.
2ⁿ	10^-3 cек.	17.9 мин.	35.7 лет	366 столетий

Бросается в глаза быстрый рост сложности вычислений в последней строке.

Действительно, с точки зрения теории сложности вычислений, между последним и двумя первыми типами задач пропасть. Первые две задачи относятся к классу задач с полиномиальной сложностью. А последняя – к задачам с экспоненциальной сложностью. Такие задачи называются трудноразрешимыми. Класс этих задач формируется эмпирически и носит название класса NP - полных задач.

Есть какая-то аналогия между проблемами алгоритмической разрешимости и трудноразрешимости. Как из-за невозможности определить понятие алгоритма проблема алгоритмической разрешимости сводится к возможности построения конкретизации, так и трудноразрешимость устанавливается сведением исследуемой задачи к одной из «эталонных» NP - полныхзадач.