Логическая схема - Boolean circuit
В теории сложности вычислений и сложности схем , булева схема представляет собой математическую модель для комбинационных цифровых логических схем . Формальный язык может быть решен с помощью семейства булевых схем, один контур для каждой возможной длины входа. Булевы схемы также используются в качестве формальной модели комбинационной логики в цифровой электронике.
Логические схемы определяются в терминах содержащихся в них логических элементов . Например, схема может содержать двоичные И и ИЛИ ворота и одинарные НЕ ворота, или быть полностью описывается бинарных логических элементов . Каждый вентиль соответствует некоторой логической функции, которая принимает на вход фиксированное количество бит и выводит один бит.
Булевы схемы представляют собой модель для многих цифровых компонентов, используемых в компьютерной инженерии , включая мультиплексоры , сумматоры и арифметико-логические устройства , но они исключают последовательную логику . Они представляют собой абстракцию, в которой упускаются многие аспекты, относящиеся к разработке реальных цифровых логических схем, такие как метастабильность , разветвление , сбои , энергопотребление и изменчивость задержки распространения .
Формальное определение
Давая формальное определение булевых схем, Фоллмер начинает с определения базиса как набора B булевых функций, соответствующих логическим элементам, допустимым в модели схемы. Затем логическая схема над базисом B с n входами и m выходами определяется как конечный ориентированный ациклический граф . Каждая вершина соответствует либо базовой функции, либо одному из входов, и есть набор ровно m узлов, которые помечены как выходы. Ребра также должны иметь некоторый порядок, чтобы различать разные аргументы одной и той же логической функции.
В качестве особого случая пропозициональная формула или логическое выражение представляет собой логическую схему с одним выходным узлом, в которой каждый другой узел имеет разветвление 1. Таким образом, логическую схему можно рассматривать как обобщение, которое допускает общие подформулы и несколько выходов. .
Общей основой для логических схем является набор { И , ИЛИ , НЕ }, который является функционально полным , т.е. е. из которого могут быть построены все остальные логические функции.
Вычислительная сложность
Фон
Конкретная схема действует только на входы фиксированного размера. Однако формальные языки ( строковые представления задач принятия решений ) содержат строки разной длины, поэтому языки не могут быть полностью захвачены одной схемой (в отличие от модели машины Тьюринга, в которой язык полностью описывается одной цепочкой Тьюринга). машина). Вместо этого язык представлен семейством схем . Семейство схем - это бесконечный список схем , в котором есть входные переменные. Семейство схемы называется решить , язык , если для каждой строки , в языке тогда и только тогда , когда есть длина . Другими словами, язык - это набор строк, которые при применении к схемам, соответствующим их длине, оцениваются как 1.
Меры сложности
Для логических схем можно определить несколько важных показателей сложности , включая глубину схемы, размер схемы и количество чередований между логическими элементами И и ИЛИ. Например, сложность размера логической схемы - это количество вентилей.
Оказывается, существует естественная связь между сложностью размера схемы и временной сложностью . Интуитивно понятно, что язык с небольшой временной сложностью (то есть требует относительно небольшого числа последовательных операций на машине Тьюринга ) также имеет небольшую сложность схемы (то есть требует относительно небольшого числа логических операций). Формально можно показать, что если язык находится в , где - функция , то он имеет схемную сложность .
Классы сложности
Несколько важных классов сложности определены в терминах логических схем. Самым общим из них является P / poly , набор языков, которые разрешимы с помощью семейств схем полиномиального размера. Непосредственно из того факта, что в языках есть схемная сложность, следует, что P P / poly. Другими словами, любая проблема, которая может быть вычислена за полиномиальное время на детерминированной машине Тьюринга, также может быть вычислена семейством схем полиномиального размера. Кроме того, включение является правильным (т.е. P P / poly), потому что существуют неразрешимые проблемы, которые находятся в P / poly. P / poly обладает рядом свойств, которые делают его очень полезным при изучении взаимосвязей между классами сложности. В частности, это полезно при исследовании проблем, связанных с P по сравнению с NP . Например, если в NP есть какой-либо язык, которого нет в P / poly, то P NP. P / poly также помогает исследовать свойства полиномиальной иерархии . Например, если NP ⊆ P / poly, то PH сворачивается в . Полное описание отношений между P / poly и другими классами сложности доступно в разделе « Важность P / poly ». P / poly также имеет интересную особенность, заключающуюся в том, что он может быть эквивалентно определен как класс языков, распознаваемых машиной Тьюринга с полиномиальным временем с ограниченной полиномиальной функцией совета .
Два подкласса P / poly, которые обладают собственными интересными свойствами, - это NC и AC . Эти классы определяются не только с точки зрения размера их схемы, но и с точки зрения их глубины . Глубина схемы - это длина самого длинного направленного пути от входного узла к выходному узлу. Класс NC - это набор языков, которые могут быть решены с помощью семейств схем, которые ограничены не только полиномиальным размером, но и полилогарифмической глубиной. Класс AC определяется аналогично NC, однако логическим элементам разрешено иметь неограниченное разветвление (то есть вентили И и ИЛИ могут применяться к более чем двум битам). NC - важный класс, поскольку оказывается, что он представляет класс языков с эффективными параллельными алгоритмами .
Оценка схемы
Цепи Значение Задача - задача вычисления выходного сигнала заданной булевой схемы на данную входную строке - это Р-полной проблема решения . Следовательно, эта проблема считается «изначально последовательной» в том смысле, что, вероятно, не существует эффективного высокопараллельного алгоритма, который решает эту проблему.