Всякая ли задача может решаться с помощью некоторого алгоритма? Иначе говоря, всякая ли проблема алгоритмически разрешима? Ответить на этот вопрос можно лишь в случае, когда оговаривается, что понимается под алгоритмом. Как мы знаем, алгоритм и связанное с ним понятие вычислимой функции - это интуитивные понятия. Поэтому для того, чтобы заявить, что какая-то проблема алгоритмически неразрешима, необходимо уточнить, о каком определении алгоритма при этом идет речь.

В силу тезиса Тьюринга можно считать, что под алгоритмом понимается машина Тьюринга-Поста, а на основании тезиса Чёрча следует говорить, что для алгоритмической разрешимости необходимо, чтобы решение задачи находилось с помощью частично рекурсивной функции. Отсюда вытекает, что если доказать, что решение задачи дается функцией, не являющейся частично рекурсивной, то такую задачу имеет смысл объявить алгоритмически неразрешимой.

Существуют ли алгоритмически неразрешимые проблемы (в указанном выше смысле)? Да, такие проблемы математикам известны. Таковыми является, например, проблема доказательства общезначимости формулы в исчислении предикатов (теорема Чёрча), проблема самоприменимости машин Тьюринга и проблема останова машины Тьюринга [34]. Большой список алгоритмически неразрешимых проблем дан в книге [39].

Глава 5

Сложность алгоритмов

5.1. Понятие о сложности алгоритмов

Сложность - это способ сравнения алгоритмов. Их сравнивают по количеству необходимых для выполнения алгоритма шагов {временная сложность) и по объему памяти, необходимой для работы алгоритма {ёмкостная сложность).

Для машины Тьюринга Т, вычисляющей (аюварную) функцию /(ж), временная аюжность - это функция равная числу ша-

гов машины, совершенных при вычислении /(ж), если /(ж) определено (в противном случае tr£{x) считается неопределенным).

Пусть S!£{x) равно числу ячеек на ленте машины Тьюринга, задействованных при вычислении функции /(ж) (если /(ж) определено; в противном случае неопределенным считается и sr£{x)). Функция в1(ж) называется емкостной (ленточной) сложностью.

Тогда [34, C.77]:

st{x) < \х\ -\-tt{x),

t) < д4(ж)ЛГ5:(»),

где ж -длина слова ж, Q, \А\ - мощности внутренней и внешней памяти (алфавита).

Можно ввести функцию сложности (по худшему случаю)

tij-(n) = max tt£{x),

x, \х\=п

которая характеризует временные затраты машины на вычисления слов длины п.

5.2. Классы задач Р и NP

Сложность задачи оценивают, как правило, с точки зрения затраты времени, необходимого машине Тьюринга-Поста рт того, чтобы вычислить функцию, посредством которой находится решение рассматриваемой задачи.

5.2.1. Класс задач Р

Рассмотрим массовую задачу, под которой в действительности имеют в виду Ю1асс П однотипных задач, состоящий из бесконечного числа индивидуальных конкретных задач и описываемый совокупностью параметров. Каждой конкретной задаче Z G Л отвечает свой набор параметров. Относительно каждой задачи ставится вопрос, ответ на который имеет вид «ДА» или «НЕТ». Например, нас интересует, обладают ли частично рекурсивные функции свойством X.

Полагается, что решение задачи П сводится к вычислению на машине Тьюринга-Поста некоторой функции.

Предполагаем, что с классом П связана система кодирования а, которм каждой задаче Z ставит в соответствие CJЮB0 a{Z) в некотором алфавите. Размер задачи Z - это fljmna слова \a{Z)\. Пусть машина Тьюринга Т решает задачи Ю1асса П и

tcr(n) = max tcT-(a(Z))

Z, a(Z)=7i

- соответствующее временнЕш CJЮжнocть (по худшему случаю).

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

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

для некоторого полинома р(п). В противном случае говорят, что задача решается за экспоненциальное время}

К экспоненциальным относят, например, оценки вида 0(n°S2