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

редактировать

модель вычисления

Пример логической схемы. Узлы

∧ {\ displaystyle \ wedge}

\ wedge

- это логические элементы И, узлы

∨ {\ displaystyle \ vee}

\ vee

- это Логические элементы ИЛИ и узлы

¬ {\ displaystyle \ neg}

\ neg

являются вентилями НЕ

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

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

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

Содержание

1 Формальное определение
2 Вычислительная сложность
- 2.1 Предпосылки
- 2.2 Меры сложности
- 2.3 Классы сложности
- 2.4 Оценка схемы
3 См. Также
4 Сноски
5 Ссылки

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

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

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

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

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

Предпосылки

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

Показатели сложности

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

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

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

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

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

Оценка схемы

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

См. Также

Сноски

Ссылки