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

Оглавление1 Логическая иерархия1.1 Определение логической иерархии1.2 Формальное определение BH1.3 Производные классы и эквивалентные определения1.4 Твердость классов логической иерархии1.5 Рекомендации2 Булева […]

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

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

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

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

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

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

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

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

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

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

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