Структуры данных и модели вычислений
и интересным для практики является
Важным и интересным для практики является вопрос о верхних и нижних оценочных функциях для времени работы конкретных алгоритмов.
Заметим, что получение нижних нетривиальных оценок каждый раз представляет собой сложную математическую задачу. Известно, например, что временная сложность задачи распознавания симметрии слова тьюринговыми программами оценивается снизу функцией , где — длина слова, а — некоторая константа.
Для многих интересных с практической точки зрения задач известные верхние оценки носят экспоненциальный характер, что часто свидетельствует о больших затратах времени при выполнении соответствующих алгоритмов на вычислительных установках.
Если для задачи имеется полиномиальная от
верхняя оценочная функция, то говорят, что разрешима в полиномиальное время.
Для многих задач не удается установить существование верхних полиномиальных оценочных функций. Однако при этом распознавание на паре слов , , является ли слово решением задачи на входе , решается за полиномиальное от длины слова время и, кроме того, для каждого существует ответ , длина которого ограничена некоторым полиномом от длины . Это так называемые задачи с проверяемым за полиномиальное время ответом. Такой задачей является, например, задача о выполнимости булевых формул, которая заключается в следующем. По заданной булевой формуле найти набор значений переменных, при которых соответствующая формуле булева функция принимает значение 1. Имея минимальный программистский опыт, легко убедиться в возможности проверки ответа к этой задаче за полиномиальное время.
Задачи с проверяемым за полиномиальное время ответом называются переборными с гарантированным экспоненциальным перебором. Действительно, пусть такая задача и длина возможного ответа
ограничена полиномом от длины входа , то есть . Пусть, далее — полином, являющийся верхней оценкой времени работы программы, проверяющей ответ, тогда, перебирая всевозможные
слов длины и затрачивая на проверку каждого не более тактов времени, получим алгоритм с верхней оценкой .
