Меры - сложность
Cтраница 1
Меры сложности /, [ л и Ъ являются асимптотически мимеоинвариантными; мера d является мимеоинвариантной. [1]
 |
Иерархия грамматик, языков и канонических систем. [2] |
Меры сложности будут использоваться для сравнения формул или языков. Возможными мерами являются длина доказательства, длина строки или высота ( длина самого длинного пути, состоящего из ветвей) древовидной диаграммы вывода. [3]
 |
Фрагмент представления причинных взаимосвязей в базе знаний. [4] |
Определенные выше меры сложности и важности позволяют приспосабливать объяснения к нуждам конкретного пользователя. [5]
Одной из мер сложности функции является время, необходимое для вычисления этой функции на машине Тьюринга. Так как конкретная модель машины Тьюринга может существенно повлиять на время вычисления, то часто различают вычисления с записью на ленте и со входом. Коротко говоря, при вычислении с записью на ленте все ( конечное) слово входных символов должно быть написано на одной из машинных лент до начала вычисления, в то время как при вычислении со входом символы входного слова поступают в машину последовательно. Некоторые аспекты машин с записью на ленте обсуждались в предыдущей работе [1]; настоящая же работа касается лишь машин со входом. [6]
Другими словами, меры сложности depth и logfsize отличаются не более чем в константу раз. [7]
Таким образом, меры сложности л, п и Ф мимео-инвариантными не являются. Пример, приведенный в замечании 1 из § 2 работы [ 1 [, показывает, что мимео-инвариантной не является и мера Я. С другой стороны, ясно, что даже класс асимптотически мимеоинвариантных мер сложности очень широк. [8]
Оказывается, что три специфические меры сложности, обсуждавшиеся в этой статье, имеют рекурсивно перечислимые классы сложности. Мы покажем, что это имеет место для любых мер сложности, если классы сложности ( их границы) достаточно велики. С другой стороны, мы покажем также, что существуют меры сложности, для которых классы сложности не могут быть рекурсивно перечислимыми. Это довольно удивительно, так как отсюда следует, что не существует эффективного способа описания того, какие функции лежат в этих классах. Это означает, что такие меры сложности являются весьма патологическими и что на меры сложности надо налагать дополнительные ограничения, чтобы устранить такие случаи. [9]
Следует заметить, что эти меры сложности ассоциируются с алгоритмами, а не прямо с теми функциями, которые вычисляются алгоритмами. Основанием для этого служит то, что при вычислениях мы обычно имеем дело с алгоритмами, определяющими функции, и для каждой вычислимой функции существует бесконечно много алгоритмов, которые ее вычисляют. [10]
Следующий результат показывает, что существуют меры сложности, для которых малые классы сложности могут не быть рекурсивно перечислимыми. [11]
Во втором разделе статьи дается мотивировка определения мер сложности вычислений и приводится несколько примеров. Затем выводятся некоторые основные свойства, которые выполняются для всех мер сложности. Показывается, например, что для каждой меры сложности существуют сколь угодно сложные функции, принимающие только значения О, 1, и что не существует рекурсивного отношения между величиной функции и ее сложностью. С другой стороны, показано, что любые две меры сложности рекурсивно ограничивают друг друга. Позднее будет показано, что это верно не для всякой рекурсивной функции. Наше доказательство основано на прямой диагональной процедуре и не опирается на теорему о рекурсии, которая использовалась в первоначальном доказательстве. Для этой меры сложности трудность доказательства значительно уменьшается по сравнению с первоначальными трудностями. Теорема об ускорении имеет странное следствие: какие бы две универсальные машины мы ни взяли ( неважно, насколько более быстрой и мощной является одна из них), существуют такие функции, которые нельзя вычислить быстрее на более мощной машине. Эго следует из того, что для любого алгоритма, который мы используем для вычисления такой функции на более мощной машине, существует другой алгоритм, настолько быстрый, что даже на медленной машине он выполняется быстрее, чем первый алгоритм на быстрой машине. [12]
Как мы уже видели, классическая теория структурного синтеза изучает статические меры сложности объектов: число элементов в схеме, число бит в таблице, число букв в формуле. [13]
Любопытной особенностью языков вида Ьь является то, что они годятся для любых строго мимеоинвариантных мер сложности. [14]
Эта работа является продолжением работы [1], в которой мы ставили себе целью описание широкого класса достаточно естественных мер сложности вывода, позволяющих классифицировать бесконтекстные грамматики. Как было показано, в качестве такого класса может быть выбран класс так называемых линейно-инвариантных мер. Теперь нам предстоит решить более сложную задачу: среди линейно-инвариантных мер указать такие, которые позволяют классифицировать бесконтекстные языки. Эти преобразования в целом сохраняют топологию деревьев и являются обобщениями гомеоморфизмов графов. Таким образом, в работе указывается одно из возможных решений поставленных в [1] задач В и С. [15]
Страницы: 1 2 3