Булева схема

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

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

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

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

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

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

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

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

Фон

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

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

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

Существует естественная связь между сложностью размера схемы и временной сложностью . ^[2]^{: 355} Интуитивно понятно, что язык с небольшой временной сложностью (то есть требует относительно небольшого количества последовательных операций на машине Тьюринга ), также имеет небольшую схемную сложность (то есть требует относительно небольшого количества логических операций). Формально можно показать, что если язык находится в , где — функция , то он имеет схемную сложность . ${\mathsf {TIME}}(t (n))$ $т$ $т:\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 {TIME}}(t (n))$ $O(t^{2}(n))$ $\subseteq$ $\subsetneq$ $\neq$ $\Sigma _{2}^{\mathsf {P}}$

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

Оценка схемы

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

Полнота

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

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

Сноски

^ аб Фоллмер, Гериберт (1999). Введение в сложность схемы . Берлин: Шпрингер. ISBN 3-540-64310-9.
^ Аб Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Курс технологии Томсона. ISBN 978-0-534-95097-2.
^ аб Арора, Санджив; Барак, Боаз (2009). Вычислительная сложность: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4.
^ Стипчевич, Марио; Бателич, Матея (2022). «Аспекты энтропии в улучшенных схемах для биологических компьютеров со случайными импульсами». Научные отчеты . 12 : 115. arXiv : 1908.04779 . дои : 10.1038/s41598-021-04177-9 .