Есть ли в схемы глубины субэкспоненциального размера?

Есть ли вероятная гипотеза сложности / криптозащиты, которая исключает возможность того, что схемы полиномиального размера имеют субэкспоненциальный размер (т. Е. с ) ограниченной глубиной ( ) схемы? $2^{O(n^\epsilon)}$ $\epsilon<1$ $d = O(1)$

Мы знаем, что каждая функция, вычисляемая схемой , может быть вычислена с помощью схемы глубины размера (с использованием логических элементов И, ИЛИ и НЕ, неограниченный размах) ) (для каждого есть и можно принять за ). $\mathsf{NC^1}$ $2^{O(n^\epsilon)}$ $d$ $0 <\epsilon$ $d$ $d$ $O(1/\epsilon)$

Вопрос в том:

Есть ли причина, по которой существование таких схем для схем общего полиномиального размера маловероятно?

cc.complexity-theory circuit-complexity bounded-depth Кава
источник

Если под субэкспоненциальным размером вы подразумеваете

(а не

), а под ограниченной глубиной вы подразумеваете постоянную глубину, то в четности нет схем ограниченной глубины субэкспоненциального размера без каких-либо допущений.

2^{n^{o (1)}}

$2^{n^{o(1)}}$

2^{o (n)}

$2^{o(n)}$

MCH

Вы должны оставить свой комментарий в качестве ответа. Вы получите за это кредит, и при необходимости он может быть помечен как принятый ответ. Это также предотвратит автоматическое повторное размещение вопроса ботом Сообщества.

Суреш Венкат

@ МЧ, я обновил вопрос, чтобы уточнить, что я имею в виду под субэкспоненциальным размером.

Каве

В однородном случае, вы можете сказать что - то (

означает время нижние оценки SAT). Но в неоднородном случае мы не знаем сильных нижних границ для P / poly, и нет сильных нижних границ для вашего определения цепей постоянной глубины субэкспоненциального размера. Например, это все еще возможно

T I M E (t) \subseteq Σ_{O (d)} T I M E [n^{1 / d}]

$TIME(t) \subseteq \Sigma_{O(d)}TIME[n^{1/d}]$

E X P^{N P}

$EXP^{NP}$ может быть смоделирован в любом из этих классов. Поэтому я не уверен, что вы могли бы сделать вывод. (Почему я сделал этот комментарий? Потому что это не совсем ответ ...)

Райан Уильямс,

Ну,

считается маловероятным. Sipser (CCC»86) показали , что либо

или

для некоторого

T I M E (t) \subseteq A T I M E (t^{1 - ϵ})

$TIME(t) \subseteq ATIME(t^{1-\epsilon})$

P = R P

$P = RP$

T I M E (t) \subseteq S P A C E (t^{1 - ϵ})

$TIME(t) \subseteq SPACE(t^{1-\epsilon})$

ϵ > 0

$\epsilon > 0$ При определенных расширителе строительных гипотез , которые были позже показаны, являются истинным Саксом, Srinivasan и Zhou.This было принято в качестве доказательства того, что

. Позже работа над твердостью против случайности сделала связь более точной.

P = R P

$P = RP$

Райан Уильямс

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

Посмотрите на Виолу о возможностях вычисления малой глубины . Лучшее, что мы знаем, - это конструкция Valiant для логических цепей: логарифмические схемы глубины линейного размера для схем глубины 3 подэкспозиции. (Мы знаем лучше для арифметических схем .) Есть также некоторые результаты Beigel / Tarui о ACC, которые содержатся в ограниченных схемах глубины суперпольного размера. Я не помню, чтобы оно распространялось на все . $NC^1$

V Vinay
источник

Спасибо за интересные ссылки. В основном меня интересует вероятность существования такого моделирования (то есть предположения и гипотезы, которые подразумевали бы отрицательный или положительный ответ для

и подобных классов, таких как

где ответ не известен безоговорочно.) знаете что-нибудь подобное?

P / p o l y

$\mathsf{P/poly}$

N C

$\mathsf{NC}$

Каве

К сожалению ничего. Я думал о некоторых старых бумагах Бермана / Гомера и других, но ничего такого не помню. Вернусь, если что-то появится.

V Vinay

Есть ли в схемы глубины субэкспоненциального размера?

Ответы: