Булева схема

Пример логической схемы. $\wedge$ узлы — это вентили И , $\vee$ узлы являются вентилями ИЛИ , а $\neg$ узлы НЕ являются воротами

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

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

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

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

Давая формальное определение булевых схем, Фоллмер начинает с определения базиса как набора B булевых функций, соответствующих вентилям, допустимым в модели схемы. Булева схема на базисе B с n входами и m выходами затем определяется как конечный ориентированный ациклический граф . Каждая вершина соответствует либо базовой функции, либо одному из входов, и существует набор ровно из m узлов, которые помечены как выходы. Края также должны иметь некоторый порядок, чтобы различать разные аргументы одной и той же логической функции.

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

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

Вычислительная сложность

Предыстория

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

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

См. Также: Сложность схемы.

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

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

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

Основная статья: Классы сложности § Булевы схемы

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

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

Оценка схемы

Проблема значения схемы — проблема вычисления выходных данных заданной логической схемы по заданной входной строке — является P-полной проблемой решения . Следовательно, эта проблема считается «по своей сути последовательной» в том смысле, что, вероятно, не существует эффективного, высокопараллельного алгоритма, который бы решил эту проблему.

Полнота

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

См. также

• Выполнимость схемы
• Логический вентиль
• Булева логика
• Лемма о переключении