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

13

Учитывая алгоритм, работающий во время , мы можем преобразовать его в «тривиальное» однородное семейство цепей для той же самой задачи размера не более .t ( n ) log t ( n )t(n)t(n)logt(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 )DTIME(t(n))n2n(2n)t(n)nt(n)logt(n)2n{0,1}O(2n/n)

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

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

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

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

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

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

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

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

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

усул
источник
1,2,3,4: функция идентичности. 5. мне не ясно, что вы подразумеваете под «преобразованием алгоритмов в схемы», мы всегда можем преобразовать однородную схему в машину Тьюринга (с небольшими накладными расходами).
Каве
@Kaveh, re # 5: Хороший вопрос, но я думаю, что я имею в виду, что кто-то записывает явную конструкцию однородных цепей, которая не выглядит как «преобразование этой ТМ в схему». Кроме того, я думаю, что упомянутое вами преобразование может не означать, что схема «похожа» на алгоритм. Например, скажем, у нас есть схема размера , для генерации которой требуется времени. Мы можем превратить его во время n 3 TM, хорошо, но оно не очень похоже на схему, и наивное преобразование этой TM обратно в схему теперь имеет размер ~ n 3 . Я надеюсь, что это показывает, почему вопрос интересует меня. nn3n3n3
Усул
1
@Kaveh: Как функция идентичности отвечает 1-4?
Джошуа Грохов
@ Джошуа, мы можем напрямую описать однородную схему (проводного) размера O (n), которая лучше, чем преобразование машины Тьюринга для идентификации в цепь.
Каве
Я хочу сказать, что есть важные мелкие детали, о которых нам нужно позаботиться, чтобы сделать вопрос ответственным. Другой пример: BPP находится в P / poly, и преобразование вычислимо. Если генерация схемы выполняется эффективным алгоритмом, объединяющим его со значением схемы, то получается эффективная ТМ. Концептуально схема и TM вычисляют один и тот же алгоритм. Тот факт, что размер и время могут не соответствовать точно, является нормальным, они определены для разных вычислительных моделей, и мы знаем, что они не соответствуют. Возможно, время соответствует глубине, а не размеру.
Каве

Ответы:

8

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

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

(4) Да, для любых с е > 0 , но для глупой причине: Каждая функция вычисляется с помощью схемы размера ( 1 + O ( 1 ) ) 2 п / п . ( Шеннон доказал это с точностью до постоянной, а Лупанов получил оптимальную постоянную.) По теореме иерархии времени существует функция f с равномерной временной сложностью между Ωs(n)=(1+ε)2n/nε>0(1+o(1))2n/nf и O ( n 3 n ) . Это дает контрпример: F имеет схемы размера O ( 2 н / п ) (которые ядуматьвычислимы в 2 р ø л у ( п ) времени)но не является вычислимой в ~ O ( 2 н / п ) времени. Вы, вероятно, должны спросить s ( n ) = o (Ω(3n)O(n3n)fO(2n/n)2poly(n)O~(2n/n) .s(N)знак равноо(2N/N)

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

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