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

18

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

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

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

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

Итак, если е(м)грамм(N)NО(1) , свойство кажется неестественным (оно нарушает условие крупности). Ясно, что мы не можем использовать диагонализацию, потому что мы не находимся в единой обстановке.

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

AntonioFa
источник

Ответы:

31

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

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

Мы знаем это:

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

Предположим, что ненулевое на NgN входах. Позвоните такие входы . Мы можем рассмотреть для каждого i функцию g i ( x ), которая является индикаторной функцией множества { x 1 , , x i } ; таким образом, g 0 = 0 и g N = g .x1,,xNigi(x){x1,,xi}g0=0gN=g

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

Лука Тревизан
источник
3
Как доказывается, что существуют функции, вычисляемые схемами размера а не схемами размера f ( n ) - O ( 1 ) ? f(n)f(n)O(1)
Уильям Хоза
28

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

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

Рассел Импальяццо
источник
6
Нет прямой причины, но все известные подходы (реализации подсчета аргументов) требуют, чтобы мы в конечном итоге проверили, что таблица истинности данной функции имеет высокую сложность схемы. NE алгоритм для этой проблемы был бы определить -Природных имуществ от P / р ö л у (которое, в соответствии с одной из работ Стивена Рудича, является маловероятным). Конечно, решение этой проблемы выглядит ненужным ...NP/polyP/poly
Райан Уильямс