Логическая схема - Boolean circuit

Пример булевой схемы. В

{displaystyle wedge}

узлы И ворота, то

{displaystyle vee}

узлы ИЛИ ворота, а

{displaystyle eg}

узлы НЕ ворота

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

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

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

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

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

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

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

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

Фон

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

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

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

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

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

Несколько важных классов сложности определены в терминах булевых схем. Самый общий из них П / поли, множество языков, которые разрешимы семействами схем полиномиального размера. Это непосредственно следует из того, что языки в ${displaystyle {mathsf {TIME}} (t (n))}$ иметь сложность схемы ${displaystyle O (t ^ {2} (n))}$ который п ${displaystyle substeq}$ П / поли. Другими словами, любая проблема, которая может быть вычислена за полиномиальное время на детерминированной машине Тьюринга, также может быть вычислена семейством схем полиномиального размера. Далее, включение правильное (т. Е. P ${displaystyle subsetneq}$ P / poly), потому что в P / poly есть неразрешимые проблемы. P / poly обладает рядом свойств, которые делают его очень полезным при изучении взаимосвязей между классами сложности. В частности, это полезно при исследовании проблем, связанных с P против NP. Например, если в NP есть какой-либо язык, которого нет в P / poly, то P ${displaystyle eq}$ Н.П.^[5] P / poly также помогает исследовать свойства полиномиальная иерархия. Например, если НП ⊆ P / poly, тогда PH схлопнется до ${displaystyle Sigma _ {2} ^ {mathsf {P}}}$ . Полное описание отношений между P / poly и другими классами сложности доступно по адресу "Важность P / poly ". P / poly также обладает той интересной особенностью, что его можно эквивалентно определить как класс языков, распознаваемых машиной Тьюринга с полиномиальным временем и полиномиально ограниченной функция консультации.

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

Оценка схемы

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

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

Сноски

^ Фоллмер 1999, стр. 8.
^ Фоллмер 1999, стр. 9.
^ Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. п. 354. ISBN 978-0-534-95097-2.
^ Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. п. 355. ISBN 978-0-534-95097-2.
^ Арора, Санджив; Варак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. п. 286. ISBN 978-0-521-42426-4.
^ Арора, Санджив; Варак, Вооз (2009). Вычислительная сложность: современный подход. Издательство Кембриджского университета. п. 119. ISBN 978-0-521-42426-4.