Булевы схемы и сложность схем

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

Definition

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

Scope

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

Core questions

• Чем представление вычислений в виде сети вентилей отличается от последовательных машин?
• Что измеряют размер и глубина схемы, и как они соотносятся со временем и параллелизмом?
• Почему нижние границы схем являются путем к разделению классов сложности?
• Какие нижние границы известны и какие барьеры препятствуют получению более сильных?

Key theories

Неравномерность и класс P/poly

Схемы допускают отдельную машину для каждой длины входа, что дает неравномерный класс P/poly, который содержит P; демонстрация того, что NP-полная проблема не имеет схем полиномиального размера, разделила бы P и NP, что мотивирует изучение нижних границ схем.

Нижние границы для ограниченных схем

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

Clinical relevance

Схемы являются естественной моделью цифрового оборудования, поэтому сложность схем влияет на проектирование чипов и пределы параллельных вычислений; классы малой глубины отражают то, что может быть быстро вычислено с помощью множества процессоров, а нижние границы схем являются основной стратегией в долгосрочных усилиях по решению таких вопросов, как P против NP.

History

Шеннон связал булеву алгебру с переключающими схемами в 1937 году, а сложность схем сформировалась как дисциплина в 1980-х годах, когда Фурст, Сакс, Сипсер и другие доказали нижние границы постоянной глубины для четности, а Разборов и Смоленский разработали алгебраические методы, прежде чем барьер естественных доказательств выявил, почему общие нижние границы так трудно найти.

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

Чем схемы отличаются от машин Тьюринга?

Машина Тьюринга — это единое устройство, обрабатывающее входы всех размеров пошагово, в то время как схема — это фиксированная сеть вентилей для одной длины входа, с отдельной схемой для каждой длины. Эта неравномерность делает схемы естественной моделью аппаратного обеспечения и параллельных вычислений, и она может выражать то, что не может выразить ни одна отдельная равномерная машина.

Почему исследователи интересуются нижними границами схем?

Доказательство того, что проблема в NP требует очень больших схем, разделило бы классы сложности и могло бы решить проблему P против NP. Нижние границы известны для ограниченных семейств схем, но их распространение на общие схемы блокируется формальными барьерами, что делает это одной из самых глубоких открытых проблем в этой области.