RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1989, том 1, выпуск 4, страницы 3–11 (Mi dm935)

Эта публикация цитируется в 1 статье

О реализации систем конъюнкций контактными схемами

И. А. Вихлянцев


Аннотация: В работе исследуется вопрос о реализации системы $m$ элементарных конъюнкций $n$ переменных контактными $(1,m)$-полюсниками и реализации разделительных $(1,m)$-полюсников для $m$-элементных множеств булевых наборов. При весьма слабых ограничениях на рост $m$ получена асимптотически точная оценка сложности разделительных $(1,m)$-полюсников. Как следствие получена асимптотика сложности реализации систем $m$ элементарных конъюнкций при $m=2^{n-o(n)}$ где $n$ число переменных.

УДК: 519.7

Статья поступила: 20.12.1988



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


© МИАН, 2024