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

21

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

Мы знаем, что каждая функция, вычисляемая схемой , может быть вычислена с помощью схемы глубины размера (с использованием логических элементов И, ИЛИ и НЕ, неограниченный размах) ) (для каждого есть и можно принять за ).NC12O(nϵ)d0<ϵddO(1/ϵ)

Вопрос в том:

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

Кава
источник
3
Если под субэкспоненциальным размером вы подразумеваете (а не 2 o ( n ) ), а под ограниченной глубиной вы подразумеваете постоянную глубину, то в четности нет схем ограниченной глубины субэкспоненциального размера без каких-либо допущений. 2no(1)2o(n)
MCH
Вы должны оставить свой комментарий в качестве ответа. Вы получите за это кредит, и при необходимости он может быть помечен как принятый ответ. Это также предотвратит автоматическое повторное размещение вопроса ботом Сообщества.
Суреш Венкат
@ МЧ, я обновил вопрос, чтобы уточнить, что я имею в виду под субэкспоненциальным размером.
Каве
3
В однородном случае, вы можете сказать что - то ( означает время нижние оценки SAT). Но в неоднородном случае мы не знаем сильных нижних границ для P / poly, и нет сильных нижних границ для вашего определения цепей постоянной глубины субэкспоненциального размера. Например, это все еще возможно E X P N PTIME(t)ΣO(d)TIME[n1/d]EXPNPможет быть смоделирован в любом из этих классов. Поэтому я не уверен, что вы могли бы сделать вывод. (Почему я сделал этот комментарий? Потому что это не совсем ответ ...)
Райан Уильямс,
2
Ну, считается маловероятным. Sipser (CCC»86) показали , что либо Р = Р Р или Т Я М Е ( т ) S Р С Е ( т 1 - ε ) для некоторого е > 0TIME(t)ATIME(t1ϵ)P=RPTIME(t)SPACE(t1ϵ)ϵ>0При определенных расширителе строительных гипотез , которые были позже показаны, являются истинным Саксом, Srinivasan и Zhou.This было принято в качестве доказательства того, что . Позже работа над твердостью против случайности сделала связь более точной. P=RP
Райан Уильямс

Ответы:

8

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

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

V Vinay
источник
Спасибо за интересные ссылки. В основном меня интересует вероятность существования такого моделирования (то есть предположения и гипотезы, которые подразумевали бы отрицательный или положительный ответ для и подобных классов, таких как N C, где ответ не известен безоговорочно.) знаете что-нибудь подобное? P/polyNC
Каве
К сожалению ничего. Я думал о некоторых старых бумагах Бермана / Гомера и других, но ничего такого не помню. Вернусь, если что-то появится.
V Vinay