Cтраница 1
Получение нижних оценок, линейных относительно п - числа аргументов функции ( или в общем случае относительно объема входной информации), обычно все-таки не вызывает больших трудностей. Получение более сильных нижних оценок - - значительно более сложная задача. Наиболее высокие нижние оценки, к-рые к настоящему времени ( 1984) удалось получить, имеют порядок и2, если не считать оценок, получающихся при очень сильных ограничениях на класс у. [1]
Получение нижних оценок сложности умножения целых чисел должно относиться к конкретной вычислительной модели. При очень разумных предположениях Патерсон, Фишер и Мей-ер [11] серьезно уменьшили разрыв между верхней и нижней оценками, показав следующее. [2]
Для получения нижней оценки подсчитаем число различных схем размера s и сравним его с количеством функций от и переменных. Для определенности считаем, что используется стандартный полный базис. [3]
Для получения нижней оценки достаточно заметить, что любой пучок А порождает класс операторных форм, состоящий из единственной формы. [4]
Для получения нижних оценок сложности существует один достаточно общий, хотя и малоэффективный в некотором смысле метод, основанный на мощностных соображениях. Именно таким методом установлена была, например, в [50] нижняя оценка функции L ( n) - сравнивалась мощность всех функций п переменных с мощностью всех схем из L элементов. [5]
Для получения более высокой нижней оценки необходимо так подобрать функционал, чтобы величина D была по возможности меньше, а величина max D ( Fi, F2) больше. [6]
В получении нижних оценок длин опровержений системы ( 1) - ( 3) основную роль будет играть следующая ниже лемма. Эта утверждение представляет и самостоятельный интерес. [7]
При получении нижних оценок сложности реализации различных классов функций схемами и формулами часто используются так называемые мощностные соображения. Примером может служить следующее утверждение. [8]
Среди методов получения нижних оценок для сложности 1в ( /) мы рассмотрим только такие, которые позволяют получать нелинейные нижние оценки. [9]
Теперь задача получения нижней оценки для функции Шеннона сводится к вычислению функции S ( n, & ()) и подбору возможно большей функции k ( n), удовлетворяющей приведенному выше неравенству. [10]
Важный метод получения нижних оценок сложности состоит в следующем. [11]
Предложен метод получения нелинейных нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами. [12]
Наиболее сложным является получение нижних оценок периода TY. К известным результатам подобного рода относятся оценки периода почленной суммы двух периодических последовательностей. [13]
Они предложили метод получения нижних оценок сложности для синхронных схем и применили его к ряду функций, наиболее интересная из которых - это определитель. [14]
Мы предлагаем метод получения нижних оценок сложности многочленов с алгебраическими коэффициентами, основанный на алгебраической геометрии. [15]