|
Эта публикация цитируется в 1 научной статье (всего в 2 статье)
Принципиальное расхождение между глубиной и задержкой
В. М. Храпченко
Аннотация:
Ранее было показано, что даже у минимальной схемы задержка $T$ может быть значительно меньше глубины $D$. А именно, была построена бесконечная последовательность минимальных схем, у которых $T<\log_2D+6$, причем $D\to\infty$. Этот результат был бы убедительнее, если бы неравенство выполнялось и для всех эквивалентных минимальных схем. В настоящей работе построена бесконечная последовательность булевых функций $F_k$, $k=1,2,\dots$, такая, что всякая минимальная схема для любой функции $F_k$ имеет задержку и глубину, удовлетворяющие неравенству $T<\log_2D+14$.
Работа выполнена при поддержке Программы фундаментальных исследований ОПМ РАН “Алгебраические и комбинаторные методы математической кибернетики”, проект “Синтез и сложность управляющих систем”.
Статья поступила: 02.07.2006
Образец цитирования:
В. М. Храпченко, “Принципиальное расхождение между глубиной и задержкой”, Дискрет. матем., 20:3 (2008), 51–72; Discrete Math. Appl., 18:4 (2008), 391–412
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1013https://doi.org/10.4213/dm1013 https://www.mathnet.ru/rus/dm/v20/i3/p51
|
Статистика просмотров: |
Страница аннотации: | 504 | PDF полного текста: | 216 | Список литературы: | 61 | Первая страница: | 11 |
|