|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ФИЦ ПХФ и МХ РАН |
||
On a Modification of Lupanov's Method with More Uniform Distribution of Fan-outстатья Электронная публикация
- Авторы: Lozhkin Sergei A., Shiganov Alexander E.
- Журнал: Electronic Colloquium on Computational Complexity (ECCC)
- Год издания: 2011
- Первая страница: 1
- Последняя страница: 13
- Аннотация: In this paper we suggest a modification of classical Lupanov's method [Lupanov1958] that allows building circuits over the basis & for Boolean functions of n variables with size at most $$\frac{2^n}{n} \left(1 + \frac{3 \log n + O(1)}{n} \right)$$ and with more uniform distribution of outgoing arcs by circuit gates. For almost all Boolean functions of n variables in the circuits for these functions, which are built using our method, the fraction of gates with fan-out 2 is asymptotically at least 1/32. This fact disproves upper bound [Yamamoto2011] on the number of circuits with exact number of gates with fan-out at least 2.
- Добавил в систему: Ложкин Сергей Андреевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | TR11-130.pdf | 708,3 КБ | 4 декабря 2012 [LozhkinSA] |