Булева иерархия

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

Логическая иерархия Определение логической иерархии Логическая иерархия — это иерархия NP-множеств, основанная на логических операциях пересечения, объединения и дополнения.  Эквивалентно, […]

Computer science stubs, Hierarchy, Иерархия, незавершенные статьи по информатике

Логическая иерархия

  • Определение логической иерархии

    • Логическая иерархия — это иерархия NP-множеств, основанная на логических операциях пересечения, объединения и дополнения. 
    • Эквивалентно, логическая иерархия — это класс логических схем над NP-предикатами. 
    • Разрушение логической иерархии привело бы к разрушению полиномиальной иерархии. 

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

    • BH1 — это NP. 
    • BH2k — это пересечение языка в BH2k-1 и coNP. 
    • BH2k+1 — это объединение языка в BH2k и NP. 
    • BH — это объединение всех классов BHi. 

  • Производные классы и эквивалентные определения

    • DP (Разностное полиномиальное время) равно BH2. 
    • Эквивалентные определения позволяют более компактные определения классов логической иерархии. 

  • Твердость классов логической иерархии

    • Сложность для классов булевой иерархии может быть доказана через сокращение числа примеров NP-полной задачи. 
    • Если сокращения существуют для произвольного k, проблема является сложной для PNP. 

  • Рекомендации

    • Статья является заглушкой и нуждается в расширении. 

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

Булева иерархия — Википедия

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

  1. Иерархия Уэджа Иерархия Wadge Определение и свойства иерархии Вайджа Иерархия Вайджа — это порядок множеств в пространстве Бэра,...
  2. Иерархия Иерархия Определение и примеры иерархии Иерархия — это структура, в которой элементы упорядочены по степени важности...
  3. Полиномиальная иерархия Полиномиальная иерархия Определение и свойства полиномиальной иерархии Полиномиальная иерархия — это иерархия сложности задач, где каждая...
  4. Иерархия памяти Иерархия памяти Иерархия памяти в компьютерах Иерархия памяти разделяет компьютерное хранилище на уровни, основанные на времени...
  5. Логическая бомба Логическая бомба Определение и история логической бомбы Логическая бомба — это вредоносное программное обеспечение, которое активируется...
  6. Кумулятивная иерархия Совокупная иерархия Определение совокупной иерархии Совокупная иерархия — семейство множеств, индексированных по порядковым номерам, с определенными...
  7. Быстрорастущая иерархия Быстрорастущая иерархия Быстрорастущие иерархии функций — это системы функций, которые растут быстрее, чем любая вычислимая функция. ...
  8. Браузер классов Браузер классов История и эволюция браузеров классов Браузеры классов берут начало в Smalltalk, одном из первых...
  9. Логическая схема Логическая схема Определение логической модели данных Логическая модель данных описывает структуру данных без привязки к конкретной...
  10. Иерархия Бореля Иерархия Бореля Иерархия Бореля — это система кодирования множеств, основанная на ординалах.  Иерархия Бореля имеет три...
  11. Арифметическая иерархия Арифметическая иерархия Определение арифметической иерархии Арифметическая иерархия — это множество множеств, упорядоченных по сложности определения.  Множество...
  12. Теорема об иерархии времени Теорема о временной иерархии Теоремы о временной иерархии Теоремы о временной иерархии описывают иерархию классов сложности,...
  13. Иерархия доказательств Иерархия доказательств Иерархия доказательности в медицине используется для оценки качества и надежности исследований.  Иерархия включает уровни...
  14. Расширенная булева модель Расширенная логическая модель Основы расширенной логической модели Расширенная логическая модель (ELM) — это метод поиска информации,...
  15. Теорема о пространственной иерархии Теорема о пространственной иерархии Определение и свойства пространства Пространство — это количество места, необходимое для хранения...
  16. Логическая интуиция Логическая интуиция Логическая интуиция включает инстинктивное предвидение, ноу-хау и сообразительность, связанные с восприятием логической или математической...
  17. Аналитическая иерархия Аналитическая иерархия Определение аналитической иерархии Аналитическая иерархия — это система классификации множеств, основанная на их выразимости...
  18. Булева схема Логическая схема Определение и применение логических схем Логическая схема — математическая модель для комбинационных цифровых логических...
  19. Иерархия данных Иерархия данных Основы иерархии данных Иерархия данных представляет собой систематическую организацию данных в иерархической форме.  Включает...
  20. Сложность Сложность Определение сложности Сложность — это свойство системы, которое затрудняет ее понимание и контроль.  Сложность может...
  21. Иерархия Хомского Иерархия Хомского Иерархия Хомского Иерархия Хомского описывает классы формальных грамматик в теории формальных языков.  Ноам Хомский...
  22. Логическая форма Логическая форма Логическая форма утверждения — точно определенная семантическая версия утверждения в формальной системе.  Неформальная логическая...

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

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