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

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

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



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






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


Дискретн. анализ и исслед. опер., 1995, том 2, номер 4, страницы 54–73 (Mi da473)  

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

О сравнении сложностей бинарных $k$-программ

Е. А. Окольнишникова

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Сравниваются сложности реализации булевых функций бинарными $k$-npoграммами при различных значениях $k$. Показано, что для любого натурального $k,k\ge 2$, существуют натуральное $s_k$ (не превосходящее $k^2$) и последовательность булевых функций такие, что сложность реализации каждой функции из этой последовательности в классе бинарных $k$-программ в экспоненциальное число раз (по числу переменных булевой функции) превосходит сложность реализации той же функции в классе бинарных $s_k$-программ.
Ил. 2, табл. 1, библиогр. 13

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

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

Образец цитирования: Е. А. Окольнишникова, “О сравнении сложностей бинарных $k$-программ”, Дискретн. анализ и исслед. опер., 2:4 (1995), 54–73

Цитирование в формате AMSBIB
\RBibitem{Oko95}
\by Е.~А.~Окольнишникова
\paper О~сравнении сложностей бинарных $k$-программ
\jour Дискретн. анализ и исслед. опер.
\yr 1995
\vol 2
\issue 4
\pages 54--73
\mathnet{http://mi.mathnet.ru/da473}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1386285}
\zmath{https://zbmath.org/?q=an:0863.68093}


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

    ОТПРАВИТЬ: 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. Okol'nishnikova E.A., “On the hierarchy of nondeterministic branching k-programs”, Fundamentals of Computation Theory, Proceedings, Lecture Notes in Computer Science, 1279, 1997, 376–387  crossref  mathscinet  isi
    2. Okol'nishnikova E.A., “Comparing the sizes of nondeterministic branching read-k-times programs”, Discrete Appl Math, 135:1–3 (2004), 205–222  crossref  mathscinet  isi
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:132
    Полный текст:56
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020