Cтраница 4
Введенные в § 2 и 3 понятия позволяют нам в заключительном параграфе определить предмет теории аналитической сложности. [46]
В своих - двух объемистых отчетах [77, 78] Трауб и Вожьняковский впервые объединили вместе оба направления теории аналитической сложности, заключив их в рамки единой абстрактной постановки и заметив, что принципиальное различие этих направлений состоит в том, что в одном случае используется общая информация, а в другом-итеративная. [47]
Современные методы точного или приближенного решения задач дискретного программирования не могут изучаться без знания основ теории сложности алгоритмов, в основе которой лежит описание задач из классов Р и NP. К классу NP относятся задачи, разрешаемые с экспоненциальной временной сложностью на ДМТ; вместо ДМТ в обоих случаях можно рассматривать программу, написанную на алгоритмическом языке высокого уровня. С практической точки зрения разница между полиномиальными алгоритмами ( для полиномов высокой степени) и экспоненциальными весьма условна, а смысл разницы - в возможности или невозможности избежать полного перебора при реальном решении задач. [48]
В заключение подчеркнем еще раз, что нашей главной целью в этой главе было просто проиллюстрировать теорию аналитической сложности на конкретных примерах. Мы ожидаем, что для многих практически важных операторов решения проблема нахождения оптимальных информационных операторов будет интенсивно разрабатываться. [49]
Это первый из ряда параграфов, в которых показывается, что для нахождения или оценки основных величин теории аналитической сложности могут оказаться полезными результаты теории аппроксимации. В данном параграфе мы устанавливаем взаимосвязи между п-ми минимальными диаметрами и - поперечниками по Гельфанду. [50]