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

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

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



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






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


Матем. заметки, 1985, том 37, выпуск 6, страницы 887–900 (Mi mz5393)  

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

Нижние оценки монотонной сложности логического перманента

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


Аннотация: Логическим перманентом $f_m$ булевой матрицы $m\times m$ называется монотонная булева функция $\bigvee_{\sigma\in S_m}&_{i=1}^mx_{i\sigma(i)}$. Монотонной сложностью $L_f^+$ монотонной булевой функции $f$ называется наименьшее число функциональных элементов И, ИЛИ, необходимое для ее реализации в виде функциональной схемы. Доказана нижняя оценка $L_{f_m}^+\ge m^{(C\log m)}$ ($C>0$). Библиогр. 7 назв.

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

Англоязычная версия:
Mathematical Notes, 1985, 37:6, 485–493

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

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

Образец цитирования: А. А. Разборов, “Нижние оценки монотонной сложности логического перманента”, Матем. заметки, 37:6 (1985), 887–900; Math. Notes, 37:6 (1985), 485–493

Цитирование в формате AMSBIB
\RBibitem{Raz85}
\by А.~А.~Разборов
\paper Нижние оценки монотонной сложности логического перманента
\jour Матем. заметки
\yr 1985
\vol 37
\issue 6
\pages 887--900
\mathnet{http://mi.mathnet.ru/mz5393}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=802432}
\zmath{https://zbmath.org/?q=an:0584.94026}
\transl
\jour Math. Notes
\yr 1985
\vol 37
\issue 6
\pages 485--493
\crossref{https://doi.org/10.1007/BF01157687}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1985AYE1900031}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz5393
  • http://mi.mathnet.ru/rus/mz/v37/i6/p887

    ОТПРАВИТЬ: 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. А. А. Разборов, “Нижние оценки размера схем ограниченной глубины в базисе $\{&,\vee,\oplus\}$”, УМН, 41:4(250) (1986), 219–220  mathnet  mathscinet  zmath  adsnasa; A. A. Razborov, “Lower estimates of the dimension of schemes of bounded depth in the basis $\{&,\vee,\oplus\}$”, Russian Math. Surveys, 41:4 (1986), 181–182  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. А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803  crossref  isi  elib
    5. В. Б. Кудрявцев, А. Е. Андреев, “О сложности алгоритмов”, Фундамент. и прикл. матем., 15:3 (2009), 135–181  mathnet  mathscinet; V. B. Kudryavtsev, A. E. Andreev, “On algorithm complexity”, J. Math. Sci., 168:1 (2010), 89–122  crossref  elib
    6. А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165  crossref  isi  elib
    7. А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. 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
    8. С. Б. Гашков, И. С. Сергеев, “Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены”, Матем. сб., 203:10 (2012), 33–70  mathnet  crossref  mathscinet  zmath  elib; S. B. Gashkov, I. S. Sergeev, “A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials”, Sb. Math., 203:10 (2012), 1411–1447  crossref  isi
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:471
    Полный текст:163
    Первая стр.:4

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