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

10

Фон

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

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

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

[FSS81], [Ajt83]: .AC0


Вопросов:

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

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

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

  3. Имеет ли имеет практические последствия? Является ли A C 0 важным на практике?AC0AC0

  4. Почему важен для (теоретических) компьютерных ученых?AC0


Замечания:

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

Связанные с:

Кава
источник
NC0AC0
AC0
AC0
@ Аарон: Я тоже мало что помню, но думаю, что циклы были в основном для элементов памяти, таких как триггеры и последовательные системы. Я не думаю, что сложно связать сложность схем с логическими / цифровыми схемами, особенно с комбинаторными системами, вопрос в том, как соотнести такие понятия, как глубина и разветвленность, с электронными схемами, выполненными из транзисторов. Может быть, я должен спросить об этом на Physics.SE.
Каве
3
@ Tsuyoshi Ito: Спасибо. Я только что проверил это в Википедии, кажется, что можно легко реализовать неограниченные логические элементы И и ИЛИ, используя линейное число NMOS . Структура цепей проста и не меняется с количеством входов в затвор. С другой стороны, схема XOR , сделанная из NMOS-транзисторов, кажется более сложной, я не знаю, хорошо ли масштабируется с увеличением разветвления.
Каве

Ответы:

10

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

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

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

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

Герман Грубер
источник
Очень интересно на самом деле.
Антонио Э. Поррека
6

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

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

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

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

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

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

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

Дэвид
источник
2
спасибо за ответ, но большая часть вашего ответа - комментарии, адресованные Джону, а не моим вопросам. Я понимаю, что вы, вероятно, разместили это как ответ, потому что вы не можете комментировать, но я не хочу, чтобы этот вопрос превратился в дискуссию между вами, поэтому не могли бы вы переместить ту часть вашего ответа, которая направлена ​​на него, на соответствующий вопрос опубликовал его? (или к мета-дискуссии ) Заранее спасибо.
Каве
1

1.6223.822

s=abcin

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

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

nO(1)

AT2=Ω(n2)

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

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

2n/n

λ(3)=8

XYZ=X(YZ+YZ)+X(YZ+YZ)

μ(3)

X1X2Xn

4(n1)

Johne
источник
Танкс Джон за ответ, но сейчас мне немного не хватает времени, но я прочитаю ваш ответ более внимательно и посмотрю статьи, на которые вы ссылались, когда найду немного свободного времени. Я разговаривал с некоторыми друзьями из отдела EE и узнал несколько интересных вещей, которые я опубликую.
Каве