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

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

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



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






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


Дискрет. матем., 2012, том 24, выпуск 2, страницы 46–74 (Mi dm1183)  

О соотношении тупиковых и минимальных комплексов граней в единичном кубе

И. П. Чухров


Аннотация: Рассматривается задача о соотношении тупиковых и минимальных дизъюнктивных нормальных форм или комплексов граней булевой функции, которая была поставлена С. В. Яблонским в связи с оцениванием сложности алгоритмов минимизации булевых функций. В работе исследуются комплексы граней, минимальные относительно класса мер сложности, для которых сложность комплекса уменьшается при удалении грани и не изменяется при замене некоторых граней на грани изоморфные относительно перестановки координат.
Для отношения числа тупиковых и минимальных комплексов граней функции для любой меры сложности из такого класса получена нижняя оценка логарифма вида $cn2^n$, где $c>1,355\cdot2^{-7}$. При этом логарифм числа тупиковых комплексов может быть порядка $n2^n$ при единственном минимальном комплексе граней, если мера сложности удовлетворяет дополнительному условию: сложность комплекса уменьшается при уменьшении ранга любой грани.
Получены нижние оценки мощности классов функций, по порядку логарифма сравнимые с числом всех функций, для которых отношение числа тупиковых и минимальных комплексов, в том числе при условии единственного минимального комплекса, имеют порядок роста логарифма, равный $n2^n$.

DOI: https://doi.org/10.4213/dm1183

Полный текст: PDF файл (919 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2012, 22:3, 273–306

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

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

Образец цитирования: И. П. Чухров, “О соотношении тупиковых и минимальных комплексов граней в единичном кубе”, Дискрет. матем., 24:2 (2012), 46–74; Discrete Math. Appl., 22:3 (2012), 273–306

Цитирование в формате AMSBIB
\RBibitem{Chu12}
\by И.~П.~Чухров
\paper О соотношении тупиковых и минимальных комплексов граней в~единичном кубе
\jour Дискрет. матем.
\yr 2012
\vol 24
\issue 2
\pages 46--74
\mathnet{http://mi.mathnet.ru/dm1183}
\crossref{https://doi.org/10.4213/dm1183}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3050555}
\elib{http://elibrary.ru/item.asp?id=20730424}
\transl
\jour Discrete Math. Appl.
\yr 2012
\vol 22
\issue 3
\pages 273--306
\crossref{https://doi.org/10.1515/dma-2012-019}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84870861360}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1183
  • https://doi.org/10.4213/dm1183
  • http://mi.mathnet.ru/rus/dm/v24/i2/p46

    ОТПРАВИТЬ: 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
  • Дискретная математика
    Просмотров:
    Эта страница:234
    Полный текст:80
    Литература:34
    Первая стр.:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020