Теорема об иерархии для размера цепи

Я думаю, что теорема об иерархии размеров для сложности схемы может быть главным прорывом в этой области.

Это интересный подход к разделению классов?

Мотивация вопроса заключается в том, что мы должны сказать

есть некоторая функция, которая не может быть вычислена схемами размера и может быть вычислена схемой размера , где . (и возможно что-то относительно глубины)g ( n ) f ( n ) < o ( g ( n ) $f(n)$$g(n)$$f(n)<o(g(n))$

Итак, если $f(m)g(n) \leq n^{O(1)}$ , свойство кажется неестественным (оно нарушает условие крупности). Ясно, что мы не можем использовать диагонализацию, потому что мы не находимся в единой обстановке.

Есть ли результат в этом направлении?

Фактически можно показать, что для каждого достаточно малого (менее 2 n / n ), существуют функции, вычисляемые схемами размера f ( n ), но не схемами размера f ( n ) - O ( 1 ) или даже f ( n ) - 1 , в зависимости от типа разрешенных ворот.$f$$2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Вот простой аргумент, который показывает, что существуют функции, вычисляемые с размером но не с размером f ( n ) - O ( n ) .$f(n)$$f(n)-O(n)$

Мы знаем это:

1. существует функция которая требует сложности схемы, по меньшей мере, 2 n / O ( n ) , и, в частности, сложности схемы больше, чем f ( n ) .$g$$2^n/O(n)$$f(n)$
2. функция такая, что z ( x ) = 0 для каждого входа x , вычисляется схемой постоянного размера.$z$$z(x)=0$$x$
3. если две функции и g 2 отличаются только на одном входе, то их сложность схемы отличается не более чем на O ( n $g_1$$g_2$$O(n)$

Предположим, что ненулевое на $g$$N$ входах. Позвоните такие входы . Мы можем рассмотреть для каждого i функцию g i ( x ), которая является индикаторной функцией множества { x 1 , … , x i } ; таким образом, g 0 = 0 и g N = g .$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Очевидно , что существует какой - то такое , что $i$ имеет сложность схемы больше, чемf(n),а g i имеет сложность схемы меньше, чемf(n). Но тогда g i имеет сложность схемы меньше, чемf(n),но больше, чемf(n)-O(n).$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Этот результат можно доказать, используя простой аргумент подсчета. Рассмотрим случайную функцию, примененную к первым битам ввода. Эта функция почти наверняка имеет сложность схемы ( 1 + o $k$ по счетному аргументу Риордана и Шеннона и соответствие верхним границам. Таким образом, подобрав k так, чтобы 2 g ( n ) < 2 k / k < f ( n ) / 2, мы можем различить размер$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ от размера f ( n ) . Обратите внимание, что рассматриваемые функции не обязательно будут даже вычислимыми, но мы можем поместить их в экспоненциальную временную иерархию стандартными методами (при условии, что мы можем вычислить правильное значение k ). Мы, конечно, не можем доказать любую оценку, превышающую 2 n / n , потому что это сложность схемы наихудшего случая для любой функции. $g(n)$$f(n)$$k$$2^n/n$

Естественные доказательства не применимы к этому типу аргумента, потому что рассматриваемое свойство «не имеет малой схемы», которое нелегко вычислить из таблицы истинности функции (предположительно). Не ясно, насколько низкими в классах сложности может идти этот тип подсчета. Есть ли какая-то причина, по которой мы не можем использовать счетный аргумент, чтобы доказать нижние оценки для ? Не то, что я знаю о. $NE$