Оглавление
Логическая иерархия
-
Определение логической иерархии
- Логическая иерархия – это иерархия NP-множеств, основанная на логических операциях пересечения, объединения и дополнения.
- Эквивалентно, логическая иерархия – это класс логических схем над NP-предикатами.
- Разрушение логической иерархии привело бы к разрушению полиномиальной иерархии.
-
Формальное определение BH
- BH1 – это NP.
- BH2k – это пересечение языка в BH2k-1 и coNP.
- BH2k+1 – это объединение языка в BH2k и NP.
- BH – это объединение всех классов BHi.
-
Производные классы и эквивалентные определения
- DP (Разностное полиномиальное время) равно BH2.
- Эквивалентные определения позволяют более компактные определения классов логической иерархии.
-
Твердость классов логической иерархии
- Сложность для классов булевой иерархии может быть доказана через сокращение числа примеров NP-полной задачи.
- Если сокращения существуют для произвольного k, проблема является сложной для PNP.
-
Рекомендации
- Статья является заглушкой и нуждается в расширении.
Полный текст статьи: