Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The fundamental symmetric functions are EX k n (equal to 1 if the sum of n input bits is exactly k), TH k n (the sum is at least k), and MOD m,r n (the sum is congruent to r modulo m). It is well known that all these functions and in fact any symmetric Boolean function have linear circuit size. Simple counting shows that the circuit complexity of computing n symmetric functions is Ω(n 2 - o(1)) for almost all tuples of n symmetric functions. It is well-known that all EX and TH functions (i.e., for all 0 ≤ k ≤ n) of n input bits can be computed by linear size circuits. In this short note, we investigate the circuit complexity of computing all MOD functions (for all 1 ≤ m ≤ n). We prove an O(n) upper bound for computing the set of functions {MOD 1,r n, MOD 2,r n,..., MOD n,r n} and an O(nloglogn) upper bound for {MOD 1,r1 n, MOD 2,r2 n,..., MOD n,rn n}, where r 1, r 2,..., r n are arbitrary integers.
Язык оригинала | английский |
---|---|
Название основной публикации | Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Proceedings |
Страницы | 81-88 |
Число страниц | 8 |
DOI | |
Состояние | Опубликовано - 4 сен 2012 |
Событие | 7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012 - Nizhny Novgorod, Российская Федерация Продолжительность: 3 июл 2012 → 7 июл 2012 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 7353 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012 |
---|---|
Страна/Tерритория | Российская Федерация |
Город | Nizhny Novgorod |
Период | 3/07/12 → 7/07/12 |
ID: 49825947