TC0

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

ТС0 Определение класса TC0 TC0 — это класс сложности схем, который включает логические схемы с постоянной глубиной и полиномиальным размером.  […]

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

ТС0

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

    • TC0 — это класс сложности схем, который включает логические схемы с постоянной глубиной и полиномиальным размером. 
    • В схемах используются вентили: ИЛИ, НЕ, мажоритарные и пороговые. 

  • Важные задачи в классе TC0

    • В классе TC0 решаются задачи сортировки, умножения, деления и распознавания языка Dyck. 

  • Отношения между классами схем

    • TC0 является подмножеством AC0 и NC1, но вопрос о строгости этого включения остается нерешенным. 
    • TC0 также является подмножеством PP, но это утверждение не является строгим. 

  • Функциональная версия униформы TC0

    • Униформа TC0 включает функции, такие как сложение, вычитание, побитовое И и функции, связанные с двоичным логарифмом. 

  • Рекомендации и внешние ссылки

    • Статья содержит ссылки на «Зоопарк сложности: TC0» для дополнительной информации. 

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

TC0 — Википедия

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

  1. Функциональная декомпозиция Функциональная декомпозиция Функциональная декомпозиция — метод проектирования, используемый для создания архитектурного описания компьютерной программы.  Архитектор программного...
  2. Функциональная проблема Функциональная проблема Определение и примеры функциональных задач Функциональная задача — это вычислительная задача с одним результатом...
  3. Функциональная модель Функциональная модель Основы функциональной модели Функциональная модель описывает взаимодействие между компонентами системы.  Функциональная модель используется для...
  4. Высказывание (логика) Утверждение (логическое) Термин «утверждение» имеет разные значения в логике и семантике.  Утверждение может быть осмысленным декларативным...
  5. Класс сложности Класс сложности Класс сложности — набор вычислительных задач, связанных по сложности с использованием ресурсов (время и...
  6. Полиномиальное сокращение времени Сокращение полиномиального времени Основы сокращения за полиномиальное время Сокращение за полиномиальное время позволяет решать одну задачу...
  7. Моделирование электронных схем Моделирование электронных схем Основы моделирования электронных схем Моделирование схем включает в себя создание и анализ математических...
  8. Функциональная неграмотность Функциональная неграмотность Функциональная неграмотность — недостаточные навыки чтения и письма для решения повседневных задач.  Функциональная неграмотность...
  9. Функциональная полнота Функциональная завершенность Функциональная полнота в логике означает, что набор логических операторов может выразить все другие логические...
  10. PSPACE ПРОСТРАНСТВО Определение PSPACE PSPACE — это класс задач, решаемых машиной Тьюринга за полиномиальное время с использованием...
  11. Описательная теория сложности Описательная теория сложности Основы логики первого порядка Логика первого порядка (FO) — это формальная система, которая...
  12. Сложность схемы Сложность схемы Основы теории сложности схем Теория сложности схем изучает вычислительные задачи, которые могут быть решены...
  13. Полный (сложность) Полный (сложность) Определение сложности задач Задача p считается завершенной для класса сложности C, если она является...
  14. Вычислительная задача Вычислительная задача Вычислительная задача — это задача, решаемая с помощью алгоритма.  Примеры вычислительных задач: факторинг, разложение...
  15. Аксиомы Блюма Аксиомы Блюма Основы аксиом Блюма Аксиомы Блюма определяют желаемые свойства показателей сложности вычислимых функций.  Сформулированы Мануэлем...

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

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