Есть ли у нас нетривиальные однородные схемы?

Учитывая алгоритм, работающий во время , мы можем преобразовать его в «тривиальное» однородное семейство цепей для той же самой задачи размера не более .≈ t ( n ) log t ( n $t(n)$$\approx t(n)\log t(n)$

С другой стороны, может случиться так, что у нас есть гораздо меньшие однородные схемы для этой проблемы, даже если является оптимальным временем работы. Цепи могут занять больше времени, чем для генерации, но они маленькие.т ( н $t(n)$$t(n)$

Но знаем ли мы на самом деле, как строить такие вещи? Я думаю, что первый вопрос, чтобы задать

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

Теперь я считаю, что если проблема находится в , то у нас есть алгоритм экспоненциального времени для поиска оптимальных схем с использованием исчерпывающего поиска: учитывая , мы записываем ответы на все входов (принимая время ); затем мы перечисляем все схемы на входах в возрастающем размере, пока не будет найдена одна, которая дает все правильные ответы. Поиск завершается либо с размером тривиального преобразования, , либо с таблицей истинности функции, если выходные данные равны . (Правка: Томас указывает, что граница равна O (2 ^ n / n) из-за Шеннона / Лупанова.) n 2 n ( 2 n ) t ( n ) n t ( n ) log t ( n ) 2 n { 0 , 1 } O ( 2 n / n $\mathsf{DTIME(t(n))}$$n$$2^n$$(2^n)t(n)$$n$$t(n) \log t(n)$$2^n$$\{0,1\}$$O(2^n/n)$

Таким образом, у нас есть неудовлетворительное «да» на вопрос (1): возьмите язык, который труден для любого времени выше , но все еще разрешим; вышеупомянутая процедура выводит таблицу истинности размером .$2^n$$2^n$

Поэтому мы должны уточнить вопрос (1). Я думаю, что два наиболее интересных случая

(2) Есть ли у нас конструктивные примеры нетривиальных однородных схем полиномиального размера ? (Даже если они генерируются очень медленными алгоритмами.)

(3) Есть ли у нас конструктивные примеры порождаемых полиномиальных нетривиальных однородных цепей полиномиального размера?

Это может быть слишком много, чтобы спросить. Как насчет более простого вопроса: знаем ли мы, что такое возможно? Возможно, нет никаких нетривиальных однородных схем?

(4) Известно ли следующее утверждение как ложное для любого ? (Правка: , спасибо Томасу.) "Если язык имеет однородные схемы размера , то он также имеет алгоритмы, работающие во времени . " (Если это так, то как насчет того, когда «униформа» заменяется на «полиномиально-равномерное время», «форма пространства журнала» и т. Д.?)$s(n) = o(2^n)$$o(2^n/n)$$L$$O(s(n))$$\tilde{O}(s(n))$

Наконец, если вышеуказанные вопросы слишком сложны,

(5) Есть ли у нас какие-либо конструкции из однородных семейств схем, которые не являются просто преобразованием алгоритмов в схемы (или записью таблицы истинности)?

Постскриптум. Эксперт, которого я спросил об упомянутом выше "О средней однородности и нижних границах цепей" ( pdf ), Santhanam и Williams 2013, что, возможно, является наиболее тесно связанной работой, но она доказывает нижние границы (что схемы, порожденные временем, не являются слишком мощный). Я был бы заинтересован в любой другой связанной работе!

Вот ответы на ваши последние два вопроса.

(5) Сортировочные сети - это однородные схемы, которые сортируют так же быстро, как и лучшие алгоритмы ОЗУ, но определенно являются не просто преобразованиями алгоритмов ОЗУ (например, быстрой сортировкой). [ AKS83 , G14 ]

(4) Да, для любых с е > 0 , но для глупой причине: Каждая функция вычисляется с помощью схемы размера ( 1 + O ( 1 ) ) ⋅ 2 п / п . ( Шеннон доказал это с точностью до постоянной, а Лупанов получил оптимальную постоянную.) По теореме иерархии времени существует функция f с равномерной временной сложностью между $s(n)=(1+\varepsilon) \cdot 2^n/n$$\varepsilon>0$$(1+o(1)) \cdot 2^n/n$$f$ и O ( n ⋅ 3 n ) . Это дает контрпример: F имеет схемы размера O ( 2 н / п ) (которые ядуматьвычислимы в 2 р ø л у ( п ) времени)но не является вычислимой в ~ O ( 2 н / п ) времени. Вы, вероятно, должны спросить s ( n ) = o $\Omega(3^n)$$O(n \cdot 3^n)$$f$$O(2^n/n)$$2^{\mathrm{poly}(n)}$$\tilde{O}(2^n/n)$ .$s(n) = o(2^n/n)$

Это интересный вопрос; Я надеюсь, что кто-то может ответить (1) - (3).