Пусть D - некоторое подмножество множества всех п-мерных двоичных наборов, состоящее не менее чем из n~2 наборов. Для частичных булевых функций, определенных в D, построены клеточные схемы, площадь которых по порядку совпадает с размером D, а глубина по порядку равна log_2 |D|. Показано, что для почти всех частичных функций площадь и глубина этих схем иеулучшаемы по порядку.
展开▼
机译：令D为所有n维二进制元组的集合的子集，至少由n〜2个元组组成。对于D中定义的部分布尔函数，构造了蜂窝电路，其面积与D的大小顺序一致，且深度顺序等于log_2 | D |。结果表明，对于几乎所有的部分功能，这些方案的面积和深度都没有按顺序改善。
展开▼
