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

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

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



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






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


Дискретн. анализ и исслед. опер., 1995, том 2, номер 1, страницы 7–20 (Mi da451)  

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

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

О. М. Касим-Заде

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет

Аннотация: Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе $AC$, состоящем из всевозможных антицепных булевых функций. Показано, что при $n\to\infty$ порядок роста сложности реализации линейной функции $n$ переменных схемами в базисе $AC$ не меньше $(n/\ln n)$. Установлено, что наибольшая сложность булевых функций $n$ переменных при реализации схемами в базисе $CA$ по порядку роста заключена между $(n/\ln n)$ и $n$.
Библиогр. 3

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

Реферативные базы данных:
УДК: 519.6
Статья поступила: 22.11.1994

Образец цитирования: О. М. Касим-Заде, “О сложности реализации булевых функций схемами в одном бесконечном базисе”, Дискретн. анализ и исслед. опер., 2:1 (1995), 7–20

Цитирование в формате AMSBIB
\RBibitem{Kas95}
\by О.~М.~Касим-Заде
\paper О~сложности реализации булевых функций схемами в~одном бесконечном базисе
\jour Дискретн. анализ и исслед. опер.
\yr 1995
\vol 2
\issue 1
\pages 7--20
\mathnet{http://mi.mathnet.ru/da451}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1340107}
\zmath{https://zbmath.org/?q=an:0861.94034|0851.94033}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da451
  • http://mi.mathnet.ru/rus/da/v2/i1/p7

    ОТПРАВИТЬ: 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. О. М. Касим-Заде, “Об одном методе получения оценок сложности схем над произвольным бесконечным базисом”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 11:2 (2004), 41–65  mathnet  mathscinet  zmath
    2. О. В. Подольская, “О нижних оценках сложности схем в базисе антицепных функций”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, № 2, 17–23  mathnet  mathscinet; O. V. Podolskaya, “Lower estimates of circuit complexity in the basis of antichain functions”, Moscow University Mathematics Bulletin, 68:2 (2013), 98–103  crossref
    3. О. М. Касим-Заде, “О порядках роста функций Шеннона сложности схем над бесконечными базисами”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, № 3, 55–57  mathnet  mathscinet; O. M. Kasim-zade, “Orders of growth of Shannon functions for circuit complexity over infinite bases”, Moscow University Mathematics Bulletin, 68:3 (2013), 170–172  crossref
    4. О. В. Подольская, “Сложность реализации симметрических булевых функций схемами в базисе антицепных функций”, Дискрет. матем., 27:3 (2015), 95–107  mathnet  crossref  mathscinet  elib; Olga V. Podolskaya, “Circuit complexity of symmetric Boolean functions in antichain basis”, Discrete Math. Appl., 26:1 (2016), 31–39  crossref  isi
    5. О. В. Подольская, “Сложность линейных функций и функции голосования в базисе антицепных функций”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2, 51–52  mathnet  mathscinet; O. V. Podolskaya, “Complexity of linear and majority functions in the basis of antichain functions”, Moscow University Mathematics Bulletin, 71:2 (2016), 82–83  crossref  isi
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:494
    Полный текст:124
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020