AC0

От / / Оставьте комментарий

AC0 (Переменный ток) Определение класса AC0 AC0 — это класс схем сложности, который включает схемы с глубиной O(1) и полиномиальным […]

Circuit complexity, Complexity classes, Классы сложности, Сложность схемы

AC0 (Переменный ток)

  • Определение класса AC0

    • AC0 — это класс схем сложности, который включает схемы с глубиной O(1) и полиномиальным размером. 
    • Он содержит все семейства схем с неограниченным количеством элементов-fanin и элементов ИЛИ. 

  • Примеры задач в AC0

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

  • Описательная сложность AC0

    • DLOGTIME-uniform AC0 эквивалентен классу FO+BIT, описывающему языки с логикой первого порядка и предикатом BIT. 

  • Различия между AC0 и NC1

    • Ферст, Сакс и Сипсер показали, что вычисление четности входных битов не может быть выполнено схемами AC0. 
    • Это означает, что AC0 не равен NC1, так как последний класс может вычислять четность. 

  • Разделение оракула между PSPACE и полиномиальной иерархией

    • Лемма о переключении позволяет оценить разделение оракула между PSPACE и полиномиальной иерархией. 

Полный текст статьи:

AC0 — Википедия

Похожие статьи:

  1. PSPACE ПРОСТРАНСТВО Определение PSPACE PSPACE — это класс задач, решаемых машиной Тьюринга за полиномиальное время с использованием...
  2. NC (сложность) ЧПУ (сложность) Определение и иерархия классов сложности NC — класс функций, которые могут быть вычислены с...
  3. PSPACE-полный PSPACE-полный Определение PSPACE-полноты Задача считается PSPACE-полной, если она может быть решена с полиномиальным объемом памяти и...
  4. Экспоненциальная иерархия Экспоненциальная иерархия Экспоненциальная иерархия сложности Экспоненциальная иерархия представляет собой экспоненциальное расширение полиномиальной иерархии.  Существует два типа...
  5. TC0 ТС0 Определение класса TC0 TC0 — это класс сложности схем, который включает логические схемы с постоянной...
  6. Список языков программирования по типам Список языков программирования по типам Классификация языков программирования Языки программирования классифицируются по различным критериям, включая парадигмы,...
  7. Проективная иерархия Проективная иерархия Определение проективной иерархии Проективная иерархия — это система множеств, упорядоченных по возрастанию сложности.  Множество...
  8. Разделение ответственности Разделение интересов Определение и преимущества разделения задач Разделение задач (SoC) — это метод проектирования, при котором...
  9. Американский средний класс Американский средний класс Определение и характеристики среднего класса Средний класс — это социальный класс, который занимает...
  10. Обычный язык Обычный язык Определение и свойства обычных языков Обычные языки — это языки, которые распознаются конечными автоматами...
  11. Протокол Артура-Мерлина Протокол Артура–Мерлина Определение и свойства MA и AM MA — это класс задач, которые могут быть...
  12. Моделирование электронных схем Моделирование электронных схем Основы моделирования электронных схем Моделирование схем включает в себя создание и анализ математических...
  13. Разделение времени Совместное использование времени История разделения времени Разделение времени — это метод, при котором несколько пользователей могут...
  14. ИП (сложность) IP (сложность) Определение и свойства IP IP — это интерактивная система проверки подлинности, которая позволяет верификатору...
  15. Теорема о пространственной иерархии Теорема о пространственной иерархии Определение и свойства пространства Пространство — это количество места, необходимое для хранения...
  16. Контекстно-зависимая грамматика Контекстно-зависимая грамматика Определение и свойства контекстно-зависимых грамматик Контекстно-зависимые грамматики (CSGs) — это формальные языки, которые могут...
  17. Начальный класс Начальный класс Определение и примеры элементарных классов Элементарный класс — это класс, который удовлетворяет всем предложениям...

Оставьте комментарий

Прокрутить вверх