Булева схема

В теории сложности вычислений и сложности схем булева схема — это математическая модель для комбинационных цифровых логических схем . Формальный язык может быть определен семейством булевых схем, по одной схеме для каждой возможной длины входа.

Булевы схемы определяются в терминах логических вентилей, которые они содержат. Например, схема может содержать двоичные вентили И и ИЛИ и унарные вентили НЕ или полностью описываться двоичными вентилями И-НЕ . Каждый вентиль соответствует некоторой булевой функции , которая принимает фиксированное количество битов на входе и выводит один бит.

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

Формальное определение

Давая формальное определение булевых схем, Фоллмер начинает с определения базиса как множества B булевых функций, соответствующих вентилям, допустимым в модели схемы. Булева схема над базисом B с n входами и m выходами затем определяется как конечный направленный ациклический граф . Каждая вершина соответствует либо базисной функции, либо одному из входов, и существует набор из ровно m узлов, которые помечены как выходы. ^[1]^{: 8} Ребра также должны иметь некоторый порядок, чтобы различать различные аргументы одной и той же булевой функции. ^[1]^{: 9}

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

Общей основой для булевых схем является набор { И , ИЛИ , НЕ }, который является функционально полным , т. е. из него могут быть построены все остальные булевы функции.

Сложность вычислений

Фон

Конкретная схема действует только на входы фиксированного размера. Однако формальные языки ( представления задач принятия решений на основе строк ) содержат строки разной длины, поэтому языки не могут быть полностью охвачены одной схемой (в отличие от модели машины Тьюринга, в которой язык полностью описывается одной машиной Тьюринга). Вместо этого язык представлен семейством схем . Семейство схем — это бесконечный список схем , где имеет входные переменные. Говорят, что семейство схем определяет язык , если для каждой строки , находится в языке тогда и только тогда, когда , где — длина . Другими словами, язык — это набор строк, которые при применении к схемам, соответствующим их длинам, оцениваются как 1. ^[2]^{: 354} $(C_{0},C_{1},C_{2},...)$ $C_{n}$ $n$ $L$ $w$ $w$ $L$ $C_{n}(w)=1$ $n$ $w$

Меры сложности

Несколько важных мер сложности могут быть определены для булевых схем, включая глубину схемы, размер схемы и количество чередований между вентилями И и ИЛИ. Например, сложность размера булевой схемы — это количество вентилей в схеме.

Существует естественная связь между сложностью размера схемы и временной сложностью . ^[2]^{: 355} Интуитивно, язык с небольшой временной сложностью (то есть требующий относительно небольшого количества последовательных операций на машине Тьюринга ), также имеет небольшую схемную сложность (то есть требующий относительно небольшого количества булевых операций). Формально можно показать, что если язык находится в , где — функция , то он имеет схемную сложность . ${\mathsf {ВРЕМЯ}}(t(n))$ $т$ $t:\mathbb {N} \to \mathbb {N}$ $O(t^{2}(n))$

Классы сложности

Несколько важных классов сложности определяются в терминах булевых схем. Наиболее общим из них является P/poly , набор языков, разрешимых семействами схем полиномиального размера. Это следует непосредственно из того факта, что языки в имеют сложность схемы , которая P P/poly. Другими словами, любая задача, которая может быть вычислена за полиномиальное время детерминированной машиной Тьюринга, также может быть вычислена семейством схем полиномиального размера. Кроме того, включение является правильным (т. е. P P/poly), поскольку существуют неразрешимые задачи, которые находятся в P/poly. Оказывается, P/poly обладает рядом свойств, которые делают его весьма полезным при изучении отношений между классами сложности. В частности, он полезен при исследовании проблем, связанных с P и NP . Например, если есть какой-либо язык в NP, который не находится в P/poly, то P NP. ^[3]^{: 286} P/poly также помогает исследовать свойства полиномиальной иерархии . Например, если NP ⊆ P/poly, то PH схлопывается до . Полное описание отношений между P/poly и другими классами сложности доступно в разделе « Важность P/poly ». P/poly также имеет интересную особенность, заключающуюся в том, что его можно эквивалентно определить как класс языков, распознаваемых полиномиальной машиной Тьюринга с полиномиально ограниченной функцией совета . ${\mathsf {ВРЕМЯ}}(t(n))$ $O(t^{2}(n))$ $\subseteq$ $\subsetneq$ $\neq$ $\Сигма _{2}^{\mathsf {P}}$

Два подкласса P/poly, которые сами по себе обладают интересными свойствами, — это NC и AC . Эти классы определяются не только с точки зрения размера схемы, но и с точки зрения глубины . Глубина схемы — это длина самого длинного направленного пути от входного узла до выходного узла. Класс NC — это набор языков, которые могут быть решены семействами схем, которые ограничены не только полиномиальным размером, но и полилогарифмической глубиной. Класс AC определяется аналогично NC, однако вентилям разрешено иметь неограниченное объединение по входу (то есть вентили AND и OR могут применяться более чем к двум битам). NC — важный класс, поскольку оказывается, что он представляет класс языков, которые имеют эффективные параллельные алгоритмы .

Оценка схемы

Задача о значении схемы — задача вычисления выходных данных заданной булевой схемы по заданной входной строке — является P-полной задачей принятия решений . ^[3]^{: 119} Поэтому эта задача считается «последовательной по своей сути» в том смысле, что, скорее всего, не существует эффективного, высокопараллельного алгоритма, решающего эту задачу.

Полнота

Логические схемы являются физическим представлением простых логических операций, И, ИЛИ и НЕ (и их комбинаций, таких как непоследовательные триггеры или сети схем), которые образуют математическую структуру, известную как Булева алгебра . Они являются полными в том смысле, что они могут выполнять любой детерминированный алгоритм. Однако просто так получается, что это не все. В физическом мире мы также сталкиваемся со случайностью, заметной в небольших системах, управляемых эффектами квантования, которые описываются теорией квантовой механики. Логические схемы не могут производить никакой случайности, и в этом смысле они образуют неполный логический набор. Средство от этого можно найти, добавив специальный генератор случайных битов к логическим сетям или компьютерам, например, в вероятностной машине Тьюринга . Недавняя работа ^[4] представила теоретическую концепцию изначально случайной логической схемы, называемой случайным триггером , которая завершает набор. Она удобно упаковывает случайность и совместима с детерминированными булевыми логическими схемами. Однако алгебраическая структура, эквивалентная булевой алгебре, и связанные с ней методы построения и редукции схем для расширенного множества пока неизвестны.

Смотрите также

Сноски

^ ab Vollmer, Heribert (1999). Введение в сложность схем . Берлин: Springer. ISBN 3-540-64310-9.
^ ab Sipser, Michael (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. ISBN 978-0-534-95097-2.
^ ab Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4.
^ Стипчевич, Марио; Бателич, Матея (2022). «Учет энтропии в улучшенных схемах для биологически вдохновленного компьютера случайных импульсов». Scientific Reports . 12 : 115. arXiv : 1908.04779 . doi : 10.1038/s41598-021-04177-9 .