Теория -сложности.
В 1980 г. (США) появилась первая монография о результатах работы по теории сложности, проводимой в … университете.
Первоначально теорию называли: теория аналитической сложности, затем -сложности, наконец, теорией информационной сложности. Далее будем использовать термин «-сложность», чтобы существовало отличие от теории информационной сложности.
Отличие от вычислительной сложности(оперируют с точной, полной и бесплатной информацией) в следующем:
-сложность: изучают сложность задач, решаемых на основе неполной, неточной или платной информации, центральную роль играют понятия «информация», «реализуемый алгоритм». Точные нижние оценки погрешности решения в данной теории определяют без введения нормы, используя радиусы или диаметры информации, которые формируются различно для задач с полной или приближённой информацией и для класса реализуемых алгоритмов.
Применяя теорию -сложности, можно ответить на следующие вопросы:
можно ли решить данную задачу с точностью ;
сколько это будет стоить или какова сложность задачи;
Рассмотрим основные понятия этой теории.
Пусть имеются два множества F={f} и G={g}, в которых f - элемент задачи, g - элемент решения.
Класс всех подмножеств множества G обозначим 2G и введём оператор решения S
Оператор решения S должен обладать следующими свойствами:
а) для всех fF
б) при h1 h2 (19)
Пусть задано 0, характеризующее допустимую погрешность решения. Элемент gG, удовлетворяющий условию будем называть -приближённым. Для поиска -приближённого произвольного неизвестного пока f необходимо ввести информационный оператор
, где H - образ множества F, N(f) - располагаемая информация об элементе f.
Информационный оператор N называют полным, если он содержит всю информацию об f , и неполным в противном случае.
Рассмотрим множество
где V(N,f) - множество всех элементов f, неотличимых с помощью информации N(f) от некоторых фиксированных .
Т.к. множество А должно удовлетворять условию типа (19), то существует оценка
, которую называют локальным радиусом информации.
Глобальный радиус информации в теории -сложности
Очевидно, что если заданная допустимая погрешность , то получить решение с заданной точностью невозможно.
Для введения понятия «сложность» необходимо задать множество P простейших операций: арифметические операции, операции сравнения, операции определения максимума из n чисел и т.п. Пусть N0 - приближённый информационный оператор. Его называют допустимым, если для всех fF существует программа вычисления N0(f) , состоящая из конечного числа простейших операций. Если такими операциями являются p1, p2, …, pl, то сложностью оператора N0(f) называют сумму
Аналогично вводят определение сложности алгоритма . Эту сложность comp() называют комбинаторной, и в ней не учтены информационный оператор и заданная погрешность решения.
Пусть R(N0) - класс реализуемых алгоритмов, для которых радиус информации r(R(N0),N0) не превосходит заданную погрешность.
Сложность алгоритма
а -сложность
и характеризует минимальный по сложности алгоритм , способный решать данную задачу с необходимой точностью.
В теории -сложности в качестве простейших операций выбирают пока 4 арифметические операции над вещественными числами и полагают, что сложность каждой из них равна 1. Это затрудняет использование данной теории даже в традиционных разделах математического программирования.
Число практических приложений -сложности невелико.
