Нижние оценки сложности булевых функций

Список литературы, электронные версии

На этой странице приведен список литературы, относящейся к теме сайта; имеются электронные версии некоторых статей в формате ps.gz или djvu. О том, как прочитать файлы этих форматов, рассказано здесь.

Общие вопросы

Асимптотические оценки

Схемы из функциональных элементов:

нелинейные оценки (подходы)

в базисе P₂, ограниченной глубины

в базисе B₂

в базисах U₂, B₀

в базисе L, ограниченной глубины

Контактные схемы

Формулы:

в произвольном базисе

в OM-базисах

в базисе B₀

в неполных базисах

сравнение базисов

Общие вопросы

Нигматуллин Р. Г. Сложность булевых функций. - М.: Наука, 1991. - 240 с.
- глава 8, С. 130-183 (djvu)
- глава 9, С. 184-219 (djvu)
Джон Э. Сэвидж. Сложность вычислений. - М.: Из-во "Факториал", 1998. - 368 с.
Ingo Wegener. The complexity of Boolean functions. - Teubner, Wiley, 1987. ("Blue book", ps.gz - источник)
Stasys Jukna. Boolean Function Complexity. Advances and Frontiers. - Vilnius, Frankfurt, 2009. - 301 p.
Черухин Д. Ю. Нижние оценки сложности булевых функций. - М.: График Без Границ, 2005. - 72 c.

Асимптотические оценки

Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ, 1963.
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Из-во МГУ, 1984. - 138 с.
Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6. - М.: Наука. Физматлит, 1996. - С. 189-214.

Схемы из функциональных элементов

нелинейные оценки (подходы)

Pippenger N., Valiant L. G. Shifting graphs and their applications // J. ACM. - 1976. - V. 23, N. 3. - P. 423-432. (для (n,n)-сетей, в которых для каждого циклического сдвига входы можно связать с соответствующими выходами непересекающимися путями, получена нижняя оценка сложности n log n; djvu)
Valiant L. G. Graph-theoretic arguments in low-level complexity // Lecture Notes in Computer Science, V. 53. - 1977. - P. 162-176. (обзор идей: сдвиговые графы, суперконцентраторы, одновременная оценка сложности и глубины; djvu)
Valiant L. G. Negation is powerless for Boolean slice functions // SIAM J. on Computing. - 1986. - V. 15, N. 2. - P. 531-535. [Вальянт Л. Дж. Отрицание малоэффективно для булевых слой-функций // Киб. сборник. Новая серия. Вып. 27. - М.: Мир, 1990. - С. 97-103.] (сведение сложности слой-функции к её сложности в монотонном базисе; djvu (перевод))
Pudlak P., Rodl V., Sgall J. Boolean circuits, tensor ranks and communication complexity // SIAM J. on Computing 26/3 (1997), pp.605-633. (контрпримеры, связанные с некоторыми подходами; методы для схем глубины 2; ps.gz)

суперконцентраторы

Valiant L. Graph-theoretic properties in computational complexity // J. of Computer and System Sciences. - 1976. - V. 13. - P. 278-285. (построен С. сложности O(N))
Pippenger N. Superconcentrators // SIAM J. on Computing. - 1977. - N 2. - P. 298-304. (построен С. сложности O(N) и глубины O(log N); черновик перевода на русский: djvu)
Gabber O., Galil Z. Explicit construction of linear-based superconcentrators // Proc. FOCS. - 1979. - P.364-370. (явная конструкция С. сложности O(N))
Lev G., Valiant L. G. Size bounds for superconcentrators // Theor. Comp. Sci.. - 1983. - V. 22. - P. 233-251. (нижняя линейная оценка сложности С.)
Alon N., Capalbo M. Smaller Explicit Superconcentrators // ?. - 2002. (явная конструкция С. меньшей сложности; ps.gz)

в базисе P₂, ограниченной глубины

Pippenger N. Superconcentrators of depth 2 // J. of Computer and System Sciences. - 1982. - V. 24. - P. 82-90. (оценки сложности С. глубины 2; нижняя - W(n log n))
Dolev D., Dwork C., Pippenger N., Wigderson A. Superconcentrators, generalizers and generalized connectors with limited depth // Proc. 15th ACM STOC. - 1983. - P. 42-51. (порядок сложности С. глубины d для чётных d>=4; pdf.gz)
Pudlak P., Savicky P. On shifting networks // Theoretical Comput. Sci. - 1993. - V. 116. - P. 415-419. (нижняя оценка W(n log n) для оператора сдвига в клессе схем для глубины 2; pdf.gz)
Pudlak P. Communication in bounded depth circuits // Combinatorica. - 1994. - V. 14(2). - P.203-216. (порядок сложности С. глубины d для нечётных d>=5, оценки для оператора сдвига и верхнетреугольной матрицы; ps.gz)
Alon N., Pudlak P. Superconcentrators of depth 2 and 3; odd levels help (rarely) // J. of Computer and System Sciences. - 1994. - V. 48. - P. 194-202. (порядок сложности С. глубины 3 - W(n log log n); усиление нижней оценки для глубины 2 - W(n log^1.5 n); pdf.gz)
Pudlak P., Rodl V., Sgall J. Boolean circuits, tensor ranks and communication complexity // SIAM J. on Computing 26/3 (1997), pp.605-633. (нижняя оценка W(n log^1.5 n) для оператора сдвига в классе схем глубины 2; ps.gz)
Radhakrishnan J., Ta-Shma A. Tight bounds for depth-two superconcentrators // Proc. 38-th FOCS. - 1997. - P. 585-594. [Radhakrishnan J., Ta-Shma A. Bounds for dispersers, extractors, and depth-two superconcentrators // SIAM J. of Discrete Mathematics. - 2000. - V. 13(1). - P. 2-24.] (порядок сложности С. глубины 2; ps.gz)
Raz R., Shpilka A. Lower bounds for matrix product, in bounded depth circuits with arbitrary gates // SIAM J. Comput. - 2003. - V. 32, No 2. - P. 488-513. (нижние оценки для умножения матриц; для глубины 2 - W(n log n); ps.gz)
Черухин Д. Ю. Нижняя оценка сложности в классе схем глубины 2 без ограничений на базис // Вестник МГУ. Сер. 1. Математика. Механика. - 2005. - № 4. - С. 54-56. (нижняя оценка W(n^1.5) для оператора циклической свёртки в классе схем глубины 2; ps.gz, tex.tgz)

суперконцентраторы ограниченной глубины

Meshulam R. A geometric construction of a superconcentrator of depth 2 // Theor. Comp. Sci. - 1984. - V. 32. - P. 215-219. (явная конструкция С. глубины 2)
Alon N. Expanders, sorting in rounds and superconcentrators of limited depth // Proc 17th ASM STOC (RI). - 1985. - P.98-102 (явная конструкция С. ограниченной глубины)

в базисе B₂

Stockmeyer L. J. On the combinational complexity of certain symmetric Boolean functions // Math. Syst. Theory. - 1976/77. - V. 10, No 4. - 323-336. [Кибернетический сборник. Новая серия. Вып. 16. - М.: Мир, 1979. - С. 45-61]
Paul W. J. 2.5n lower bound on the combinational complexity of Boolean functions // SIAM J. Comput. - 1977. - V. 6, No 3. - P. 427-443 [Кибернетический сборник. Новая серия. Вып. 16. - М.: Мир, 1979. - С. 23-44]
Schnorr C. P. A 3n-lower bound on the network complexity of Boolean functions // Theoret. Comput. Sci. - 1980. - V. 10, No 1. - P. 83-92. [Кибернетический сборник. Новая серия. Вып. 18. - М.: Мир, 1981] (специалисты насчитали только 2.75n - см. книгу Нигматуллина; djvu (перевод) - источник)
Blum N. A Boolean function requiring 3n network size // Theoret. Comput. Sci. - 1984. - V. 28, No 3. - P. 337-345. [Кибернетический сборник. Новая серия. Вып. 22. - М.: Мир, 1985. - С. 43-53]

в базисах U₂, B₀

Редькин Н. П. Доказательство минимальности некоторых схем из функциональных элементов // Проблемы кибернетики. Вып. 23. - М.: Наука, 1970. - С. 83-101. (djvu - источник)
Schnorr C. P. Zwei lineare untere Schranken fur die Komplexitat Boolescher Funktionen // Computing. - 1974. - V. 13, No 2. - P. 155-171.
Zwick U. A 4n lower bound on the combinatorial complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions // SIAM Journal on Computing. - 1991. - V. 20. - P. 499-505. (нижняя оценка ~4n для некоторых периодических симметрических функций (mod>=3) в базисе U₂; ps.gz - источник)
Lachish O., Raz R. Explicit lower bound of 4.5n - o(n) for Boolean Circuits // Proceedings of the 33rd STOC. - 2001. - pp. 399-408. (нижние оценки ~4,5n в базисе U₂; ps.gz - источник)
Iwama K., Morizumi H. An Explicit Lower Bound of 5n – o(n) for Boolean Circuits // Lecture Noter in Computer Science. V. 2420. Proceedings of 27th MFSC. - 2002. - P. 353-364. (нижние оценки ~5n в базисе U₂; pdf, Abstract)

в базисе L, ограниченной глубины

Alon N., Karchmer M, Wigderson A. Linear circuits over GF(2) // SIAM J. Comput. - 1990. - V. 19, No 6. - P. 1064-1067. (нелинейныек нижние оценки для линейных схем любой конечной глубины; для схем глубины 2, вычисляющих матрицу Адамара - W(n log n); pdf)

Контактные схемы

Cardot C. Quelques resultats sur l'application de l'algebre de Boole a la synthese des circuits a relais // Ann. Telecomm. - 1952. - V. 7, No 2. - P. 75-84. (точное значение 4n-4 сложности линейной функции)
Лупанов О. Б. О сравнении сложности реализации монотонных функций контактными схемами, содержащими лишь замыкающие контакты, и произвольными контактными схемами // ДАН СССР. - 1962. - Т. 144, № 6. - С. 1245-1248. (нижняя оценка W(nlog n / log log n) в монотонных схемах для симметрической функции; djvu)

Формулы

в произвольном базисе

Нечипорук Э. И. Об одной булевской функции // ДАН СССР. - 1966. - Т. 169, № 4. - C. 765-766.
Hodes L., Specker E. Lengths of formulas and elimination of quantifiers // Contributions to mathematical logic. - Amsterdam: North-Holland, 1968. - P. 175-188. [Кибернетический сборник. Новая серия. Вып. 10. - М.: Мир, 1973. - С. 99-113] (нелинейные нижние оценки для симметрических функций в произвольном базисе)
Fischer M. J., Meyer A. R., Paterson M. S. W(nlog n) lower bounds on length of Boolean formulas // SIAM J. Comput. - 1982. - V. 11, No 3. - P. 416-427. [Кибернетический сборник. Новая серия. Вып. 21. - М.: Мир, 1984. - С. 3-54.]
Pudlak P. Bounds for Hodes-Specker theorem // Lecture Notes in Computer Science. V. 171. - Berlin, Springer, 1984. - P. 421-445. (нижние оценки W(nlog log n) для симметрических функций в произвольном базисе)
Paterson M., Zwick U. Shallow circuits and concise formulae for multiple addition and multiplication // Computational complexity. - 1993. - V. 3. - P. 262-291. (ps.gz - источник)
Черухин Д. Ю. Нижние оценки формульной сложности симметрических булевых функций // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 3. - С. 86-98. (ps.gz (черновик))

в OM-базисах

Мучник Б. А. Оценка сложности реализации линейной функции в некоторых базисах // Кибернетика. - 1970. - № 4. - С. 29-38. (djvu)
Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах // Дискретная математика и информатика. Вып. 2. - Иркутск: Изд-во Иркут. ун-та, 1995. [см. тж. Дискретная математика. - 2000. - Т. 12, вып.1. - С. 135-144]
Черухин Д. Ю. Сверхквадратичные нижние оценки сложности формул в некоторых базисах // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 2. - С. 86-95. (djvu)
Черухин Д. Ю. О реализации линейной функции формулами в различных базисах // Вестник Моск. ун-та. Сер 1. Математика. Механика. - 2001. - N 6. - С. 15-19.
Chockler H., Zwick U. Which bases admit non-trivial shrinkage of formulae? // Computational complexity. - 2001. - V. 10, No 1. - P. 28-40. (нижние оценки W(n^1+с) для линейной функции и W(n^2+с-o(n)) для функции Андреева, константа c для базиса U₃ - 1/3, в общем случае - прежняя: 1/(3k-4), где k - наибольшее число аргументов у функций из базиса; ps.gz - источник)

в базисе B₀

Яблонский С. В. Реализация линейной функции в классе П-схем // ДАН СССР. - 1954. - Т. 94, № 5. - С. 805-806. (верхняя оценка сложности линейной функции)
Субботовская Б. А. О реализации линейных функций формулами в базисе V, &, - // ДАН СССР. - 1961. - Т. 136, № 3. - С. 784-787. (нижняя оценка W(n^{1. 5}); djvu)
Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. - 1963. - Т. 149, № 4. - C. 784-787. (нижние оценки W(nlog n) для степеней функций, бесповторно не выразимых в B₀; djvu)
Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Матем. заметки. - 1971. - Т. 9, № 1. - С. 35-40. (djvu)
Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Матем. заметки. - 1972. - Т. 10, № 1. - С. 83-92. (djvu)
Здобнов С. В. О сложности линейной функции в классе П-схем без нулевых цепей // Комбинаторно-алгебраические методы и их применения: Межвуз. тематич. сб. науч. тр. / Под. ред. Ал. А. Маркова. - Горький: Горьк. гос. ун-т, 1987. - 171 с. (точная оценка сложности; djvu)
Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности p-схем // Вестн. МГУ. Сер. 1. Математика. Механика. - 1987. - № 1. - C. 70-73. (нижняя оценка W(n^{2. 5-o(n)}))
Nisan N., Impagliazzo R. The effect of random restrictions on formulae size // Random Structures Algorithms. - 1993. - V. 4. - P. 121-133. (нижняя оценка W(n^{2.
55-o(n)}); ps.gz - источник)
Paterson M., Zwick U. Shrinkage of de Morgan formulae under restriction // Random Structures Algorithms. - 1993. - V. 4. - P. 135-150. (нижняя оценка W(n^{2. 63-o(n)}); ps.gz - источник)
Hastad J. The shrinkage exponent is 2 // Proc. 34th Annual Symp. on Foundations of Computer Science. - IEEE Computer Society Press, 1993. - P. 114-123. [Hastad J. The shrinkage exponent of de Morgan formulas is 2 // SIAM J. Comput. - 1998. - V. 27. - P. 48-64.] (нижняя оценка W(n^3-o(n)); ps.gz - источник)
Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сибирский журнал исследования операций. - 1994. - Т. 1, № 4. - С. 33-52. (нижние оценки n²+3 для нечётных n>=5, n²+2 для чётных, отличных от степеней двойки; djvu)
Lee T. The formula size of PARITY // ? (точная оценка сложности линейной функции, pdf, доказательство ошибочно) [Preliminary version: Lee T. A new rank technique for formula size lower bounds // Lecture Notes in Computer Science, vol. 4393: 145-156, 2007. (Proceedings of STACS-2007, pdf)]
Черухин Д. Ю. К вопросу о логическом представлении счётчика чётности // Неформальная наука. - 2009. - № 2. - С. 14-23. (компьютерное доказательство точной оценки 40 для n=6; статья)
Рычков К. Л. О нижних оценках формульной сложности линейной булевой функции // Сибирские электронные математические известия. - 2014. - Т. 11. - С. 165-184. (аналитическое доказательство точной оценки 40 для n=6; pdf)

в неполных базисах

Лупанов О. Б. О влиянии глубины формул на их сложность // Кибернетика. - 1970. - № 2. - С. 46-49. (степенные нижние оценки для монотонных формул ограниченной глубины; djvu)
Нечипорук Э. И. О реализации дизъюнкции и конъюнкции в некоторых монотонных базисах // Проблемы кибернетики. Вып. 23. - М.: Наука, 1970. - С. 291-293. (степенные нижние оценки)
Стеценко В. А. О сравнении булевых базисов // Изв. вузов. Математика. - 1988. - № 7. - С. 72-79. (степенные нижние оценки; djvu)

сравнение базисов

Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. - 1963. - Т. 149, № 4. - C. 784-787. (постановка задачи, критерий эквивалентности максимальному базису B₀; djvu)
Нечипорук Э. И. О реализации дизъюнкции и конъюнкции в некоторых монотонных базисах // Проблемы кибернетики. Вып. 23. - М.: Наука, 1970. - С. 291-293. (бесконечные семейства несравнимых базисов в некоторых монотонных классах)
Стеценко В. А. О сравнении булевых базисов // Изв. вузов. Математика. - 1988. - № 7. - С. 72-79. (бесконечно возрастающие цепочки базисов во всех сильных классах, отличных от P₂; djvu)
Стеценко В. А. О предплохих базисах в P₂ // Математические вопросы кибернетики. Вып. 4. - М.: Наука, 1992. - С. 139-177. (описание базисов, предшествующих B₀; djvu)
Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах // Дискретная математика и информатика. Вып. 2. - Иркутск: Изд-во Иркут. ун-та, 1995. [см. тж. Дискретная математика. - 2000. - Т. 12, вып.1. - С. 135-144] (бесконечно возрастающая цепь полных базисов)
Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики. Вып. 8. - М.: Наука, 1999. - С. 77-122. (критерий сравнения полных базисов; см. все работы)
Кириченко К. Д. Слабоповторные булевы функции в некоторых предэлементарных базисах // Дискретная математика и информатика. Вып. 13. - Иркутск: Изд-во Иркут. ун-та, 2000. - 60 c. (описание некоторых семейств базисов второго слоя)

Страница обновлена: T16.443