Cтраница 2
Данные могут обладать своей собственной мерой сложности и поэтому соответствующие сложностные показатели алгоритмов часто задают в зависимости от меры сложности исходных данных. [16]
Заметим, что сигнализирующие любой меры сложности образуют измеримое множество и, кроме того, свойство быть измеримым множеством не зависит от меры сложности. [17]
Фактически большинство других естественных мер сложности, с которыми приходится иметь дело, действительно удовлетворяют этому определению. Если дано некоторое множество сигнализирующих функций, то можно применить произвольную рекурсивную функцию f ( n) п ( или произвольную рекурсивную неограниченную монотонную функцию) к каждой сигнализирующей функции, чтобы получить новое множество сигнализирующих функций. Тем не менее будет показано, что определение мер сложности вычисления является достаточно ограничительным, чтобы исключить из множества сигнализирующих функций те функции, которые не имеют реального смысла меры сложности вычисления. Здесь поучительно рассмотреть несколько примеров, которые не являются мерами сложности. [18]
Чтобы изучить зависимость этой меры сложности от устройства машины, рассмотрим четыре модели машин, определенные в [1], а именно: двустороннюю и одностороннюю машины Тьюринга, двустороннюю и одностороннюю магазинные машины. Так как мы изучаем ленточные функции с точки зрения скорости роста, мы ограничимся монотонными неубывающими ленточными функциями. [19]
Статья касается прежде всего изучения мер сложности вычислений, определенных для всех вычислимых частичных функций. [20]
Очевидно, что эти предложенные меры не вполне согласуются друг с другом: они определяют очень разные упорядочения формул языка и различных языков. В случае транслирующих систем мы можем рассматривать меры сложности эквивалентных формул в различных языках; мы могли бы, например, задаться вопросом, сохраняет ли заданный алгоритм трансляции упорядочение сложностей, определяемое заданной мерой. [21]
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [22]
Подобно теореме ускорения ( S-253 speedup theorem) она может быть сформулирована в терминах абстрактных мер сложности ( см. В. [23]
Во-первых, мы доказываем теорему об объединении, которая утверждает, что объединение любой рекурсивно перечислимой последовательности возрастающих классов сложности снова является классом сложности. Отсюда следует, что многие изучавшиеся ранее подклассы рекурсивных функций естественным образом подходят под многие меры сложности. Например, существует рекурсивная граница L ( n) емкости ленты, такая, что класс функций, вычислимых на машинах Тьюринга, у которых длина ленты ограничена функцией L ( n), состоит точно из примитивно рекурсивных функций. Второй главный результат этой части - теорема об именовании - несколько ослабляет остроту теоремы о пробелах, показывая, что для любой меры существует ( измеримое) множестэе функций, которые именуют все классы сложности, не оставляя сколь угодно широкие пробелы вверх. К сожалению, оказывается, что именование классов сложности может иметь сколь угодно широкие пробелы вниз. [24]
Но, прежде чем перейти к обсуждению, следует подробно рассмотреть используемую модель вычислений и меры сложности алгоритмов. [25]
Мы не утверждаем, что мы - первые, кому пришла мысль о применении этого метода. Напротив, мы уверены, что почти всякий, кто занимается нижними оценками для какой-либо меры сложности булевых функций, имеет этот метод в виду. [26]
Одна из главных целей теории автоматов состоит в том, чтобы достигнуть понимания вычислительного процесса для различных классов задач. Но теория должна идти дальше понятия вычислимости, она должна изучать, насколько сложно вычисление и как его сложность связана с устройством машины, производящей это вычисление. Две меры сложности особенно важны - это время и память. В этой работе мы получаем оценки сложности для ряда моделей машин вычислительного типа ( включающего и классическую машину Тьюринга), связанные с ограничениями на ленты. [27]
Как мы уже видели, классическая теория структурного синтеза изучает статические меры сложности объектов: число элементов в схеме, число бит в таблице, число букв в формуле. Иначе говоря, создание динамических мер сложности представляет интерес для задач проектирования на макроуровне и микроуровне. [28]
Применяя подход, основанный на МНР, можно измерят время, требуемое для вычисления каждого значения функций по конкретной программе в предположении, что каждый шар МНР совершается за единицу времени. Таким образом опре деленное время вычисления является примером меры вычисли тельной сложности, отражающей сложность или эффектив ность используемой программы. Позднее мы рассмотрим дру гие меры сложности. [29]
Мера сложности приписана значениям и правилам. В рассматриваемой редакции системы эти меры являются статическими. Ясно, что возможность динамической модификации мер сложности и важности повысила бы гибкость рассматриваемого подхода. Хотя указанные меры некоторым образом взаимосвязаны, но из значения одной значение другой прямо не следует. [30]