О соотношении сложностей двух видов плоских схем из функциональных элементов

В работе рассматриваются два способа размещения схем из функциональных элементов на плоской прямоугольной решетке. Первый способ допускает расположение входных процессоров в любой клетке решетки. Второй способ требует, чтобы входные процессоры были расположены по границе решетки. Рассматривается конкретная последовательность булевых функций $g_n(x_1,\dots,x_n)$ которые в случае первого способа размещения занимают $gn$ клеток решетки, а во втором случае для их размещения необходимо использовать по крайней мере $c_2n^{3/2}$ клеток решетки. Приведен конструктивный метод вынесения входных процессоров на границу решетки, позволяющий показать, что для размещения функции $g_n$ вторым способом достаточно $c_1n^{3/2}$ клеток.