Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены

Авторы: Гашков С.Б., Сергеев И.С.
Журнал: Математический сборник
Том: 203
Номер: 10
Год издания: 2012
Издательство: МИАН
Местоположение издательства: Москва
Первая страница: 33
Последняя страница: 70
DOI: 10.4213/sm7904
Аннотация: В работе предлагается метод получения нижних оценок сложности многочленов с положительными действительными коэффициентами при реализации схемами из функциональных элементов над монотонным арифметическим базисом {x+y, x·y} U {ax | a є R_+}. Этот метод применяется к получению нескольких новых результатов. В частности, построены примеры многочленов степени m-1 по каждой из n переменных с коэффициентами 0 и 1, имеющих при m^n → ∞ аддитивную монотонную сложность m^{(1-o(1))n} и мультипликативную монотонную сложность m^{(1/2-o(1))n}. В таком виде эти нижние оценки неулучшаемы.
Добавил в систему: Сергеев Игорь Сергеевич

	ИСТИНА	Войти в систему Регистрация
	ИПМех РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА