Практические последствия

Фон

Сложность схемы определяется как набор семейств схем (т. Е. Последовательности схем, по одной для каждого входного размера) ограниченной глубины и полиномиального размера, построенных с использованием неограниченного разветвления И, ИЛИ и НЕ.$AC^0$

Функция четности с n- битным входом равна XOR битов на входе.$\oplus$$n$

Одна из первых нижних границ схемы, доказанная в сложности схемы, является следующей:

[FSS81], [Ajt83]: .$\oplus \notin AC^0$

Вопросов:

Пусть будет классом функций, которые могут быть вычислены с использованием электронных схем ограниченной глубины и полиномиального размера с использованием электронных компонентов, таких как транзисторы. (Я придумал имя E C 0 , дайте мне знать, если вы знаете лучшее имя для этого).$EC^0$$EC^0$

1. Можно ли вычислить на практике , используя E C 0 схем?$\oplus$$EC^0$

2. А как насчет неограниченного фан-ин И / ИЛИ? Можем ли мы вычислить их в ?$EC^0$

3. Имеет ли имеет практические последствия? Является ли A C 0 важным на практике?$\oplus \notin AC^0$$AC^0$

4. Почему важен для (теоретических) компьютерных ученых?$\oplus \notin AC^0$

Замечания:

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

Связанные с:

• Паритет и $AC^0$

• Почему четность в важна? $AC^0$(Вычислительная сложность блог)

Я не инженер-электрик, но ищу онлайн-патенты в отношении коммутационных цепей для паритетных вентилей, и во всех предложениях (я нашел патенты только до конца 1970-х годов) обсуждается проблема размера-глубины. Все три патента, которые я рассмотрел, предлагают решения логарифмической глубины, основанные на затворах Фарин-2. Таким образом, ответ на ваш первый вопрос, возможно, «нет».

JJ Moyer: Схема коммутации контроля четности, патент США US3011073, 1961

А. Ф. Бульвер и др .: Реализация NAND Gate функции четности n-входа, патент США US 3718904, 1973 г.

PJ Baun, Jr .: Parity Circuits, патент США US 4251884, 1981

Джон, в чем твоя проблема? Вы пытаетесь спорить о вещах, на которые никто никогда не претендовал. Никто не сказал, что нижняя граница четности представляет собой некоторый фундаментальный предел для вычисления XOR с цепями, отличными от тех, к которым применяется теорема (то есть с цепями AC ^ 0). Здесь нет никаких скрытых предположений или скрытых последствий. В частности, мы все знаем, например, что можно вычислить XOR с NAND-схемами полиномиального размера логарифмической глубины, даже с постоянным разветвлением.

Цитата Шеннона тоже в значительной степени не имеет значения. Там нет никаких указаний на то, что он даже подозревал, что схемы И-ИЛИ постоянной глубины должны иметь экспоненциальный размер для вычисления четности. Конечно, он мог бы догадаться, так как легко догадаться, что это должно быть правдой после того, как какое-то время поигрался с проблемой, но что с того?

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

Тот факт, что результат кажется интуитивным, не делает его очевидным; если вы думаете, что это так, пожалуйста, предоставьте доказательство того, что четность не в AC ^ 0. Всем известно, что P тоже не равно NP, но ни у кого нет доказательств.

Ваши жалобы в других темах на ворота NAND также не имеют смысла. Эта нижняя граница одинаково хорошо подходит для цепей постоянной глубины, построенных из вентилей NAND, поскольку они в основном одинаковы. Решение указать результат с помощью И, ИЛИ, НЕ - это просто вопрос удобства. Таким образом, это может быть реальное приложение в терминах, которые вам нравятся: схемы постоянной глубины вычислительной четности вентилей NAND требуют экспоненциального размера. Это дает практическое ограничение, даже если это не самое главное. Это говорит о том, что небольшие схемы XOR для большого числа n входов должны иметь либо глубину, растущую с n, либо вентили, отличные от NAND. Почему вы не удовлетворены этим?

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

Кстати, сообщество CS хорошо знало теорию булевых схем EE и опиралось на это, вопреки тому, что вы утверждаете.

$1.62^2$$3.82^2$

• КМОП-технологии логических схем

$s = a \oplus b \oplus c_{in}$

• Высокая скорость, низкая мощность 8T Full Adder Cell

Хорошее место для поиска высокоскоростных, компактных вентилей XOR / XNOR - в полных сумматорах и цепях Хемминга ECC (которые обычно находятся на критическом пути).

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

$n$$O(1)$

$AT^2 = \Omega(n^2)$

• О сложности реализаций СБИС и графовых представлений булевых функций с применением к целочисленному умножению

Это из блога сложности вычислений:

Возникает вопрос: неужели некоторые люди в реальном мире действительно хотят построить полизированные контуры с неограниченной глубиной в виде цепей Fanin AND-OR-NOT для PARITY, и говорит ли этот результат, почему они не могут?

$2^n/n$

$\lambda(3) = 8$

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

$\mu(3)$

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

$4(n-1)$