Самый эффективный способ преобразовать цепь

РЕДАКТИРОВАТЬ (22 августа 2011 г.):

Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу за частичный ответ на первоначальный вопрос!)

Фон:

Учитывая цепь AC ⁰ с глубиной k и размером S, существует другая схема AC ⁰ , вычисляющая ту же функцию с глубиной k и размером $O(S^k)$ , так что новая схема имеет разветвление = 1 для всех затворов. Другими словами, схема выглядит как дерево (за исключением входов, поскольку входы могут разветвляться на более чем один вентиль). Один из способов сделать это - продублировать все ворота с разветвлением> 1, пока все ворота не разветвятся = 1.

Но это самый эффективный способ для преобразования переменного тока ⁰ цепей к сети переменного тока ⁰ цепей с 1 разветвления? Я прочитал следующее в лекции 14 заметок курса Райана О'Доннелла :

Означает ли это, что есть способ взять любую глубину k AC ⁰ цепь размера S и преобразовать ее в AC ⁰ цепь с разветвлением 1, глубиной k и размером $(2kS)^2$ ? Если да, то как это делается и является ли этот метод самым известным?

Оригинальный вопрос:

Учитывая цепь AC ⁰ с глубиной k и размером S, каков наиболее известный метод (с точки зрения минимизации размера схемы результирующей схемы) для преобразования этого в схему AC ⁰ глубины k и разветвления затвора 1? Есть ли какие-либо нижние границы, известные для этого?

Более новый, более простой вопрос:

Этот вопрос является ослаблением первоначального, где я не настаиваю на том, чтобы результирующая схема имела постоянную глубину. Как объяснено выше, существует способ преобразовать цепь AC ⁰ с глубиной k, размер S, в схему с размером , чтобы новая цепь имела разветвление = 1 для всех затворов. Есть ли лучшая конструкция?$O(S^k)$

Учитывая цепь AC ⁰ с глубиной k и размером S, каков наиболее известный метод (с точки зрения минимизации размера схемы результирующей цепи) для преобразования этого в схему любой глубины с разветвлением затвора 1?

Я постараюсь обобщить мои предыдущие комментарии.

Давайте сначала проигнорируем тот факт, что ваша исходная схема имеет (постоянную) глубину ; просто предположим , что имеет размер S . Пусть A будет наименьшим числом, таким образом, что любой неограниченный размер цепи вентилятора в S может быть преобразован в неограниченную формулу вентилятора в размере F размера O ( S A ) . Я утверждаю, что лучшее, что мы можем сделать до сих пор, это достичь A = O ( S / log 2 S ) . Скажем, даже неизвестно, существует ли какая-либо (фанин-2) схема размера S = O ( n $k$$S$$A$$S$$F$$O(S^A)$$A=O(S/\log^2 S)$$S=O(n)$можно смоделировать по формуле с размером меньше чем .$\exp(n/\log n)$

Чтобы показать это утверждение, мы преобразуем формулу в формулу Фанина-2 F ′ размера M = O ( S 2 A ) . Хорошо известно, что глубина D каждой формулы F ′ может быть сделана логарифмической по своему размеру, то есть D = O ( log M ) = O ( A log S ) . [Это было впервые показано Храпченко в 1968 году, а затем константа при большой-O была улучшена до D ≤ 1,73 log 2$F$$F′$$M=O(S^{2A})$$D$$F′$$D=O(\log M)=O(A\log S)$$D\leq 1.73\log_2M$несколькими авторами.] С другой стороны, самый известный результат для цепей fanin-2 [Paterson and Valiant, TCS 2 (3), 397-400] говорит, что . Таким образом, имитация с A, намного меньшим, чем S / log 2 S , улучшит наиболее известное моделирование размера-глубины для цепей.$Depth=O(Size/\log Size)$$A$$S/\log^2 S$

Это, однако, только «слово предостережения» - оно не отвечает на ваш вопрос, потому что вы предполагаете, что ваша исходная схема имеет постоянную глубину , подразумевая, что в этом случае мы можем просто взять A = k (или A = k - 1 если у нас есть один выходной вентиль). Сила симуляции Патерсона-Валианта заключается в том, что она применима к произвольным, даже очень несбалансированным цепям, глубина которых составляет почти весь размер! Но в вашей настройке ограниченной глубины даже случай k = 3 неясен: может ли каждая схема глубины 3 размера S быть преобразована в формулу глубины 3 размера, намного меньшего, чем S $k$$A=k$$A=k−1$$k=3$$S$$S^2$? Я думаю, что ответ должен быть «нет» (может быть интересным упражнением для студентов). Формула глубины 3 - это просто ИЛИ КНФ. Вопрос состоит в том, чтобы найти ИЛИ CNF, которые имеют много общих положений, но в остальном «сильно отличаются», чтобы получить формулу большой глубины-3.

Проблема в том, что мы хотим получить формулу (схема разветвления-1). Как было указано выше, использование вентилей fanout-2 упрощает симуляцию: Гувер, Клаве и Пиппенгер [JACM 31 (1), 1980] показывают, что любая схема fanin-2 размера и глубины D имеет эквивалентный fanin-2 и fanout -2 схема размер 3 S - 2 л и глубиной 2 D . Таким образом, если fanin не ограничен, то результирующая схема будет иметь размер O ( S 2 ) и глубину O ( D log S ) .$S$$D$$3S−2n$$2D$$O(S^2)$$O(D\log S)$

Есть еще один результат, как-то связанный с вашим вопросом. Ложкин (1981) доказал, что если булева функция может быть вычислена по формуле A C 0 глубины k и размера S , то f может быть вычислена по формуле fanin-2 глубины D ≤ k - 1 + ⌈ log 2 S ⌉ (это следует из теоремы 6.2 в моей книге). Обратите внимание, что тривиальная верхняя граница была бы только D ≤ k log S (если бы мы моделировали каждый отдельный вентиль с помощью дерева глубины log S ).$f$$AC^0$ $k$$S$$f$$D\leq k-1+\lceil\log_2S\rceil$$D\leq k\log S$$\log S$