RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. заметки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. заметки, 1987, том 41, выпуск 4, страницы 598–607 (Mi mz4883)  

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

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

А. А. Разборов


Аннотация: Устанавливается экспоненциальная нижняя оценка сложности реализации функции голосования схемами в базисе $\{&,\oplus\}$ (или, что эквивалентно, в базисе $\{\vee,&,\oplus\}$) ограниченной глубины. Библиогр. 17 назв.

Полный текст: PDF файл (886 kB)

Англоязычная версия:
Mathematical Notes, 1987, 41:4, 333–338

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.85
Поступило: 29.04.1986

Образец цитирования: А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения”, Матем. заметки, 41:4 (1987), 598–607; Math. Notes, 41:4 (1987), 333–338

Цитирование в формате AMSBIB
\RBibitem{Raz87}
\by А.~А.~Разборов
\paper Нижние оценки размера схем ограниченной глубины в~полном базисе, содержащем функцию логического сложения
\jour Матем. заметки
\yr 1987
\vol 41
\issue 4
\pages 598--607
\mathnet{http://mi.mathnet.ru/mz4883}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=897705}
\zmath{https://zbmath.org/?q=an:0632.94030}
\transl
\jour Math. Notes
\yr 1987
\vol 41
\issue 4
\pages 333--338
\crossref{https://doi.org/10.1007/BF01137685}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1987L342500038}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz4883
  • http://mi.mathnet.ru/rus/mz/v41/i4/p598

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. Е. Шпарлинский, “О некоторых вопросах теории конечных полей”, УМН, 46:1(277) (1991), 165–200  mathnet  mathscinet  zmath  adsnasa; I. E. Shparlinski, “On some problems in the theory of finite fields”, Russian Math. Surveys, 46:1 (1991), 199–240  crossref  isi
    2. A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Изв. РАН. Сер. матем., 59:1 (1995), 201–224  mathnet  mathscinet  zmath; Izv. Math., 59:1 (1995), 205–227  crossref  isi
    3. А. Д. Коршунов, “Монотонные булевы функции”, УМН, 58:5(353) (2003), 89–162  mathnet  crossref  mathscinet  zmath  adsnasa; A. D. Korshunov, “Monotone Boolean functions”, Russian Math. Surveys, 58:5 (2003), 929–1001  crossref  isi  elib
    4. А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87  mathnet  mathscinet; A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46  crossref
    5. Alman J. Williams R., “Probabilistic Rank and Matrix Rigidity”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, ed. Hatami H. McKenzie P. King V., Assoc Computing Machinery, 2017, 641–652  crossref  isi
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:366
    Полный текст:111
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018