В теоретической информатике , А цепь представляет собой модель вычислений , в котором входные значения протекают через последовательность вентилей, каждый из которых вычисляющой функции . Подобные схемы представляют собой обобщение логических схем и математическую модель цифровых логических схем. Цепи определяются воротами, которые они содержат, и значениями, которые они могут произвести. Например, значения в логической схеме являются логическими значениями, а схема включает в себя вентили конъюнкции , дизъюнкции и отрицания . Значения в качестве целочисленных схем являются наборамииз целых чисел и ворот вычислить объединение множеств , пересечение множеств , а также множество комплемент , а также арифметические операции сложения и умножения .
Формальное определение
Схема - тройная , где
- это набор значений,
- представляет собой набор меток ворот, каждая из которых является функцией из к для некоторого неотрицательного целого числа (где представляет количество входов в вентиль), и
- является меченого ориентированный ациклический граф с метками из.
Вершины графа называются воротами . Для каждых воротиз в-степени , ворота может быть помечен элементом из если и только если определяется на .
Терминология
Ворота нулевой степени называются входами или листами . Ворота исходящей степени 0 называются выходами . Если есть край от ворот к воротам в графике тогда называется ребенок из. Мы предполагаем, что вершины графа упорядочены, поэтому мы можем говорить ой ребенок ворот, когда меньше, чем угол выхода ворот.
Размера из схемы является число узлов схемы. Глубина ворот это длина самого длинного пути в начиная с до выходного затвора. В частности, ворота исходящей степени 0 являются единственными воротами глубины 1. Глубина контура - это максимальная глубина любых ворот.
Уровень это набор всех врат глубины . Выровнена схема представляет собой схему , в которой края для ворот глубины приходит только из врат глубины или от входов. Другими словами, ребра существуют только между соседними уровнями схемы. Ширина из выровненного схемы максимального размера любого уровня.
Оценка
Точное значение ворот со степенью и этикетка определяется рекурсивно для всех ворот .
где каждый является родителем .
Значение схемы - это значение каждого из выходных вентилей.
Схемы как функции
Метки листьев также могут быть переменными, которые принимают значения в . Если есть уходит, то схему можно рассматривать как функцию от к . Тогда обычно рассматривают семейство схем, последовательность схем, пронумерованная целыми числами, где схема имеет переменные. Таким образом, семейства схем можно рассматривать как функции от к .
Понятия размера, глубины и ширины можно естественным образом расширить до семейств функций, превратив их в функции из к ; Например, размер -й контур семьи.
Сложность и алгоритмические проблемы
Вычисление выхода данной логической схемы на конкретном входе - это P-полная проблема. Однако, если вход представляет собой целочисленную схему , неизвестно, разрешима ли эта проблема .
Сложность схемы пытается классифицировать булевы функции по размеру или глубине схем, которые могут их вычислить.
Смотрите также
Рекомендации
- Фоллмер, Хериберт (1999). Введение в сложность схем . Берлин: Springer. ISBN 978-3-540-64310-4.
- Ян, Кэ (2001). «Оценка целочисленной схемы завершена PSPACE». Журнал компьютерных и системных наук . 63 (2, сентябрь 2001 г.): 288–303. DOI : 10,1006 / jcss.2001.1768 . ISSN 0022-0000 .