Схема (информатика)

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

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

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

Схема представляет собой триплет , где ${\displaystyle (M,L,G)}$

• ${\displaystyle M}$это набор значений,
• ${\displaystyle L}$представляет собой набор меток вентилей, каждая из которых является функцией от до для некоторого неотрицательного целого числа (где представляет собой количество входов в вентиль), и ${\displaystyle M^{i}}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle i}$
• ${\displaystyle G}$представляет собой помеченный ориентированный ациклический граф с метками из . ${\displaystyle L}$

Вершины графа называются воротами . Для каждого ворот входящей степени ворота могут быть помечены элементом тогда и только тогда, когда определено на ${\displaystyle g}$ ${\displaystyle i}$ ${\displaystyle g}$ ${\displaystyle \ell }$ ${\displaystyle L}$ ${\displaystyle \ell }$ ${\displaystyle M^{i}.}$

Терминология

Вентили степени захода 0 называются входами или листьями . Вентили степени исхода 0 называются выходами . Если в графе есть ребро от вентиля до вентиля, то называется потомком . Мы предполагаем, что на вершинах графа есть порядок, поэтому мы можем говорить о потомке вентиля, когда меньше степени исхода вентиля. ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle G}$ ${\displaystyle h}$ ${\displaystyle g}$ ${\displaystyle k}$ ${\displaystyle k}$

Размер схемы — это количество узлов схемы. Глубина вентиля — это длина самого длинного пути от начала до выходного вентиля. В частности, вентили исходящей степени 0 — это единственные вентили глубины 1. Глубина схемы — это максимальная глубина любого вентиля. ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle g}$

Уровень ${\displaystyle i}$ — это набор всех вентилей глубины . Выровненная схема — это схема, в которой ребра к вентилям глубины исходят только из вентилей глубины или из входов. Другими словами, ребра существуют только между соседними уровнями схемы. Ширина выровненной схемы — это максимальный размер любого уровня. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Оценка

Точное значение вентиля с входящей степенью и меткой определяется рекурсивно для всех вентилей . ${\displaystyle V(g)}$ ${\displaystyle g}$ ${\displaystyle i}$ ${\displaystyle l}$ ${\displaystyle g}$

${\displaystyle V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}}$

где каждый является родителем . ${\displaystyle g_{j}}$ ${\displaystyle g}$

Значение схемы равно значению каждого из выходных вентилей.

Схемы как функции

Метки листьев также могут быть переменными, которые принимают значения в . Если есть листья, то схема может рассматриваться как функция от до . Тогда обычно рассматривается семейство схем , последовательность схем, индексированных целыми числами, где схема имеет переменные. Таким образом, семейства схем могут рассматриваться как функции от до . ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle M^{n}}$ ${\displaystyle M}$ ${\displaystyle (C_{n})_{n\in \mathbb {N} }}$ ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle M^{*}}$ ${\displaystyle M}$

Понятия размера, глубины и ширины естественным образом могут быть расширены до семейств функций, становясь функциями от до ; например, — размер -го контура семейства. ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle size(n)}$ ${\displaystyle n}$

Сложность и алгоритмические проблемы

Вычисление выходных данных заданной булевой схемы на конкретных входных данных является P-полной задачей. Однако, если входные данные представляют собой целочисленную схему , неизвестно, разрешима ли эта задача .

Сложность схем пытается классифицировать булевы функции по размеру или глубине схем, которые могут их вычислять.

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

• Сложность арифметической схемы
• Булева схема
• Сложность схемы
• Схемы над множествами натуральных чисел
• Классы сложности NC , AC и TC
• Квантовая схема и BQP

Ссылки

• Фолльмер, Хериберт (1999). Введение в сложность схем . Берлин: Springer. ISBN 978-3-540-64310-4.
• Ян, Кэ (2001). «Оценка целочисленных схем является PSPACE-полной». Журнал компьютерных и системных наук . 63 (2 сентября 2001 г.): 288–303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000.