Cтраница 3
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [31]
Таким образом, меры сложности л, п и Ф мимео-инвариантными не являются. Пример, приведенный в замечании 1 из § 2 работы [ 1 [, показывает, что мимео-инвариантной не является и мера Я. С другой стороны, ясно, что даже класс асимптотически мимеоинвариантных мер сложности очень широк. [32]
Оказывается, что три специфические меры сложности, обсуждавшиеся в этой статье, имеют рекурсивно перечислимые классы сложности. Мы покажем, что это имеет место для любых мер сложности, если классы сложности ( их границы) достаточно велики. С другой стороны, мы покажем также, что существуют меры сложности, для которых классы сложности не могут быть рекурсивно перечислимыми. Это довольно удивительно, так как отсюда следует, что не существует эффективного способа описания того, какие функции лежат в этих классах. Это означает, что такие меры сложности являются весьма патологическими и что на меры сложности надо налагать дополнительные ограничения, чтобы устранить такие случаи. [33]
В этом разделе мы изучаем две взаимосвязанные проблемы, Первая возникает естественным образом, когда мы рассматриваем некоторые хорошо известные подклассы рекурсивных функций, вроде примитивно рекурсивных функций, и пытаемся локализовать их среди классов сложности при заданной мере. Обычно эти подклассы рекурсивных функций определяются через структуру своих алгоритмов, и это вполне убеждает в том, что они должны естественным образом располагаться среди классов сложности. Мы покажем на самом деле, в качестве приложения теоремы об объединении, что для многих мер сложности Ф существует рекурсивная функция /, такая, что Cf является в точности классом примитивно рекурсивных функций. [34]
Внимание исследователей привлекают и методы оценки сложности выводов. Сюда относятся такие проблемы, как отыскание сравнительно коротких формул, необходимо имеющих сложные доказательства, или формул, из которых уже сравнительно несложно можно получить большое количество результатов. Рассматриваются естественные меры сложности вывода: длина доказательства; время, требуемое для поиска вывода; сложность формул, фигурирующих в выводе, и др. В этой области методы теории доказательств смыкаются с методами теоретической кибернетики. [35]
Предполагается, что выполнена выборка задач по определенному классу из генеральной совокупности. Выборочная совокупность задач записывается на алгоритмическом языке и подвергается испытаниям. По каждой из задач создается характеристический вектор и определяется приведенное количество операций. Одномерный ряд мер сложности вычислений по выборочной совокупности задач обрабатывается программой Статистический анализ с целью получения его характеристик. [36]
Фактически большинство других естественных мер сложности, с которыми приходится иметь дело, действительно удовлетворяют этому определению. Если дано некоторое множество сигнализирующих функций, то можно применить произвольную рекурсивную функцию f ( n) п ( или произвольную рекурсивную неограниченную монотонную функцию) к каждой сигнализирующей функции, чтобы получить новое множество сигнализирующих функций. Тем не менее будет показано, что определение мер сложности вычисления является достаточно ограничительным, чтобы исключить из множества сигнализирующих функций те функции, которые не имеют реального смысла меры сложности вычисления. Здесь поучительно рассмотреть несколько примеров, которые не являются мерами сложности. [37]
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [38]
Оказывается, что три специфические меры сложности, обсуждавшиеся в этой статье, имеют рекурсивно перечислимые классы сложности. Мы покажем, что это имеет место для любых мер сложности, если классы сложности ( их границы) достаточно велики. С другой стороны, мы покажем также, что существуют меры сложности, для которых классы сложности не могут быть рекурсивно перечислимыми. Это довольно удивительно, так как отсюда следует, что не существует эффективного способа описания того, какие функции лежат в этих классах. Это означает, что такие меры сложности являются весьма патологическими и что на меры сложности надо налагать дополнительные ограничения, чтобы устранить такие случаи. [39]
Каноническая форма I представляет интерес в связи с вопросом о параметрической сложности. Последняя может быть получена одним из следующих двух способов. Эту меру сложности обозначим через I. Эту меру сложности обозначим через II. В обоих случаях определенные выше меры параметрической сложности лишь косвенно связаны с вычислительной сложностью оценивания коэффициентов системы. Например, много легче оценить параметры системы AR, чем параметры системы ARMA, несмотря на то, что число уравнений в первом случае может оказаться большим, чем в последнем. [40]
Оказывается, что три специфические меры сложности, обсуждавшиеся в этой статье, имеют рекурсивно перечислимые классы сложности. Мы покажем, что это имеет место для любых мер сложности, если классы сложности ( их границы) достаточно велики. С другой стороны, мы покажем также, что существуют меры сложности, для которых классы сложности не могут быть рекурсивно перечислимыми. Это довольно удивительно, так как отсюда следует, что не существует эффективного способа описания того, какие функции лежат в этих классах. Это означает, что такие меры сложности являются весьма патологическими и что на меры сложности надо налагать дополнительные ограничения, чтобы устранить такие случаи. [41]
Таким образом, мы не всегда можем получить более широкие классы сложности, применяя рекурсивную функцию к старой границе сложности. Этот результат имеет еще такое интересное следствие. Когда мы рассматриваем универсальную вычислительную машину, то не важно, как сильно мы увеличиваем - скорость вычисления и как много новых операций добавляем; все равно существует бесконечно много рекурсивных границ сложности, для которых старая и новая машины будут вычислять в точности те же самые функции. То есть в пределах бесконечного числа границ сложности нельзя получить никакого преимущества новой машины над старой, увеличивая скорость и вычислительную мощь машины. За обсуждением этого результата следует другой удивительный результат, который показывает, что аксиомы сложности допускают меры сложности с классами сложности, которые могут не быть рекурсивно перечислимыми. К счастью, для широких классов сложности эта ситуация не может иметь места. Показано, что для любой меры все достаточно широкие классы сложности являются рекурсивно перечислимыми. [42]
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [43]