Сложнореализуемые булевы функции и трудновычислимые действительные числа

Автор: Гашков С.Б.
Журнал: Дискретная математика
Том: 3
Номер: 1
Год издания: 1991
Издательство: ФГБУ "Издательство "Наука"
Местоположение издательства: Москва
Первая страница: 48
Последняя страница: 60
Аннотация: Для любой функции L(ε), удовлетворяющей некоторым естественным условиям, доказано существование a∈R, сложность ε-приближения которого схемами в базисе {x±y,xy,x/y,1} по порядку равна L(ε), а при некоторых дополнительных ограничениях на L(ε) справедливо асимптотическое равенство. Установлена связь между сложнореализуемыми в некотором специальном базисе булевыми функциями и трудновычислимыми действительными константами, при которой этим функциям соответствуют нелиувиллевские трансцендентные числа.
Добавил в систему: Гашков Сергей Борисович

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

ИСТИНА