Hardly realizable Boolean functions and hardly computable real numbersстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 3 мая 2017 г.
Аннотация:Для любой функции L(ε)L(ε), удовлетворяющей некоторым естественным условиям, доказано существование a∈Ra∈R, сложность εε-приближения которого схемами в базисе {x±y,xy,x/y,1}{x±y,xy,x/y,1} по порядку равна L(ε)L(ε), а при некоторых дополнительных ограничениях на L(ε)L(ε) справедливо асимптотическое равенство. Установлена связь между сложнореализуемыми в некотором специальном базисе булевыми функциями и трудновычислимыми действительными константами, при которой этим функциям соответствуют нелиувиллевские трансцендентные числа.