Сложность схемы
-
Основы теории сложности схем
- Теория сложности схем изучает вычислительные задачи, которые могут быть решены с помощью схем.
- Сложность схем измеряется в терминах размера схемы и глубины ее вычислений.
-
История и основные результаты
- Шеннон в 1949 году доказал, что для многих булевых функций требуются схемы размером Θ(2n/n).
- До сих пор не доказана сверхлинейная нижняя граница для явных функций.
- Нижние границы были получены для функций, таких как четность и проблема k-клики.
-
Сложность и монотонные схемы
- Монотонные схемы могут вычислять только монотонные логические функции.
- Разборов и Рудич в 1997 году показали, что многие известные нижние границы подразумевают существование естественных свойств.
-
Классы сложности и временные сложности
- Иерархия классов NC описывает схемы полиномиального размера с ограниченной глубиной.
- Временная сложность языка связана с размером и глубиной схемы, вычисляющей его.
-
Монотонные схемы и минимизация замыканий
- Монотонные схемы могут быть использованы для вычисления монотонных функций.
- Минимизация замыканий — это метод для уменьшения размера схем.
Полный текст статьи: