Cтраница 3
Пусть фиксирована модель машины Тьюринга и некоторая мера сложности программ. Одну и ту же функцию ( слово) могут вычислять разные машины Тьюринга. [31]
Может показаться, что с многообразными возможностями1 выбора меры сложности и разнообразными вопросами, которые могут возникать, теория сложности вычислений станет коллекцией изолированных результатов и не связанных друг с другом методов. [32]
Так как теорема об ускорении применима ко всем мерам сложности, то ее можно применять для ускорения программ вычислительных машин. Однако такие программы обычно используются для вычисления значений функции для некоторого конечного множества значений аргумента, а не для всевозможных значений. Уменьшение асимптотического времени работы программы почти всюду - это не совсем то, в чем заинтересован вычислитель-практик. Однако теорема говорит о том, что мы не можем классифицировать функции по сложности их вычисления, так как некоторые функции не имеют внутренней минимальной сложности. То, что мы будем делать вместо этого, - это определять классы сложности и изучать их в разд. [33]
Через С ( соответственно, С л) обозначается мера сложности С ( соответственно, СА), распространенная на - - схемы. [34]
Укажем нек-рые фундаментальные результаты, не зависящие от выбора меры сложности ( в том числе и от выбора конкретного уточнения понятия алгоритма) - лишь бы существовала, напр. Для простоты можно представить себе дело так, что речь идет о времени вычисления на машинах Тьюринга натураль-нозначыых функций натурального аргумента. Пусть Т и / t суть вычислимые натурально. [35]
Его значение состоит в том, что оно предлагает меру сложности для r - критических графов. [36]
Эта теорема иллюстрирует тот факт, что коразмерность служит мерой сложности критической точки. Симметрии, являющиеся плодом наших намерений или допущений, вообще говоря, увеличивают коразмерность. Пусть, например, f ( x, у) симметрична относительно поворотов на 90, как это часто бывает для идеальных систем. Если / не-морсовская в начале, то она имеет порядок 4 по ( х, у), поскольку квадратичная часть исчезает в неморсовском случае по симметрии, и кубическая тоже. Упрощение, даваемое тем, что мы анализируем идеальную систему, получается ценой много большего усложнения поведения системы, связанного с небольшими неизбежными несовершенствами, из-за которых функция немного изменяется. Этот факт становится особенно бросающимся в глаза, когда непрерывная симметрия ведет к бесконечной коразмерности, как, например, в случае плавучей платформы, рассмотренном в § 10 гл. [37]
Аналогичные результаты получены и для случая, когда в качестве меры сложности принималась величина р: процент остаточных ошибок увеличивался, а процент протестированных дуг уменьшался с увеличением сложности структур. [38]
Понятие звездной высоты sh ( R) используется в теории регулярных языков как мера сложности языка. Аналогично можно определить подстановочную звездную высоту для контекстно-свободных языков. [39]
Таким образом, не должно быть надежды на то, что индивидуальная функция может иметь единственную меру сложности, которая не зависит от класса машин. Остается возможность, которая и предлагается здесь вместо этого: аксиоматическая теория, теоремы которой не зависят от класса. [40]
Итак, в отличие от иерархий, основанных на сложности алгоритмов, иерархии, основанные на мере сложности вычислений, являются частично упорядоченными. Это усложняет их изучение, но вместе с тем позволяет, по-видимому, более тонко улавливать сущность того, что мы интуитивно понимаем под сложностью вычислений функции. [41]
Прежде чем рассматривать методы изучения линейных систем, желательно обсудить вопрос о необходимом количестве информации как мере сложности задачи. [42]
Некоторые, из авторов ранних работ задавались вопросом: что же на самом деле следует считать мерой сложности. [43]
Часто требуется рассмотрение отношения периметр / площадь области, которое является наиболее сжатой характеристикой формы, мерой сложности полигона. Наименьшее такое отношение из всех фигур имеет круг, в то время как вытянутые полигоны имеют большее значение этого отношения. [44]
В частности, пусть L обозначает меру сложности, учитывающую все операции с единичными весами, L2 - меру сложности, учитывающую лишь умножения и деления ( включая скалярные умножения) и не учитывающую сложений и вычитаний. [45]