Теория -сложности.

В 1980 г. (США) появилась первая монография о результатах работы по теории сложности, проводимой в … университете.

Первоначально теорию называли: теория аналитической сложности, затем -сложности, наконец, теорией информационной сложности. Далее будем использовать термин «-сложность», чтобы существовало отличие от теории информационной сложности.

Отличие от вычислительной сложности(оперируют с точной, полной и бесплатной информацией) в следующем:

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

Применяя теорию -сложности, можно ответить на следующие вопросы:

можно ли решить данную задачу с точностью ;

сколько это будет стоить или какова сложность задачи;

Рассмотрим основные понятия этой теории.

Пусть имеются два множества F={f} и G={g}, в которых f - элемент задачи, g - элемент решения.

Класс всех подмножеств множества G обозначим 2^G и введём оператор решения S

Оператор решения S должен обладать следующими свойствами:

а) для всех fF

б) при h₁ h₂ (19)

Пусть задано 0, характеризующее допустимую погрешность решения. Элемент gG, удовлетворяющий условию будем называть -приближённым. Для поиска -приближённого произвольного неизвестного пока f необходимо ввести информационный оператор

, где H - образ множества F, N(f) - располагаемая информация об элементе f.

Информационный оператор N называют полным, если он содержит всю информацию об f , и неполным в противном случае.

Рассмотрим множество

где V(N,f) - множество всех элементов f, неотличимых с помощью информации N(f) от некоторых фиксированных .

Т.к. множество А должно удовлетворять условию типа (19), то существует оценка

, которую называют локальным радиусом информации.

Глобальный радиус информации в теории -сложности

Очевидно, что если заданная допустимая погрешность , то получить решение с заданной точностью невозможно.

Для введения понятия «сложность» необходимо задать множество P простейших операций: арифметические операции, операции сравнения, операции определения максимума из n чисел и т.п. Пусть N₀ - приближённый информационный оператор. Его называют допустимым, если для всех fF существует программа вычисления N₀(f) , состоящая из конечного числа простейших операций. Если такими операциями являются p₁, p₂, …, p_l, то сложностью оператора N₀(f) называют сумму

Аналогично вводят определение сложности алгоритма . Эту сложность comp() называют комбинаторной, и в ней не учтены информационный оператор и заданная погрешность решения.

Пусть R(N₀) - класс реализуемых алгоритмов, для которых радиус информации r(R(N₀),N₀) не превосходит заданную погрешность.

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

а -сложность

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

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

Число практических приложений -сложности невелико.