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

редактировать

логическая иерархия - это иерархия из логических комбинаций (пересечение, объединение и дополнение ) наборов NP. Аналогично, логическая иерархия может быть описана как класс логических схем по предикатам NP. Коллапс логической иерархии будет означать коллапс иерархии полиномов.

Содержание

1 Формальное определение
2 Производные классы
3 Эквивалентные определения
4 Жесткость
5 Ссылки

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

BH определяется следующим образом:

BH1is NP.
BH2k- это класс языков, которые являются пересечение языка в BH 2k-1 и языка в coNP.
BH2k + 1 - это класс языков, которые являются объединением языка в BH 2k и языка в NP.
BH является объединением производных классов BH i

DP (разностное полиномиальное время) равно BH 2.

Эквивалентные определения

Определение конъюнкции и дизъюнкции классов следующим образом позволяет использовать более компактные определения. Соединение двух классов содержит языки, являющиеся пересечением языка первого класса и языка второго класса. Дизъюнкция определяется аналогичным образом с объединением вместо пересечения.

C ∧ D = {A ∩ B | A ∈ C B ∈ D}
C ∨ D = {A ∪ B | A ∈ C B ∈ D}

Согласно этому определению DP = NP ∧ coNP. Остальные классы булевой иерархии можно определить следующим образом.

BH 2 k = co NP ∧ BH 2 k - 1 {\ displaystyle {\ mathsf {BH}} _ {2k} = {\ mathsf {coNP}} \ wedge {\ mathsf {BH}} _ {2k- 1}}

{\ displaystyle {\ mathsf {BH}} _ {2k} = {\ mathsf {coNP}} \ wedge {\ mathsf {BH}} _ {2k-1}}

BH 2 k + 1 = NP ∨ BH 2 k {\ displaystyle {\ mathsf {BH}} _ {2k + 1} = {\ mathsf {NP}} \ vee {\ mathsf {BH}} _ {2k}}

{\ displaystyle {\ mathsf {BH}} _ {2k + 1} = {\ mathsf {NP}} \ vee {\ mathsf {BH}} _ {2k}}

В качестве альтернативных определений классов логической иерархии можно использовать следующие равенства:

BH 2 k = ⋁ i = 1 k DP {\ displaystyle {\ mathsf {BH}} _ { 2k} = \ bigvee _ {я = 1} ^ {k} {\ mathsf {DP}}}

{\ displaystyle {\ mathsf {BH}} _ {2k} = \ bigvee _ {i = 1} ^ {k} {\ mathsf {DP}}}

BH 2 k + 1 = NP ∨ ⋁ я = 1 k DP {\ displaystyle {\ mathsf {BH}} _ {2k + 1} = {\ mathsf {NP}} \ vee \ bigvee _ {i = 1} ^ {k} {\ mathsf {DP}}}

{\ displaystyle {\ mathsf {BH}} _ {2k + 1} = {\ mathsf {NP}} \ vee \ bigvee _ {я = 1} ^ {k} {\ mathsf {DP}}}

В качестве альтернативы, для каждого k ≥ 3:

BH k = DP ∨ BH k - 2 {\ displaystyle {\ mathsf {BH}} _ {k} = {\ mathsf {DP}} \ vee {\ mathsf {BH}} _ {k-2}}

{\ displaystyle {\ mathsf {BH}} _ {k} = {\ mathsf {DP}} \ vee {\ mathsf {BH}} _ {k-2}}

Твердость

Трудность для классов булевой иерархии может быть доказана путем демонстрации сокращения из числа экземпляров произвольной NP-полной задачи A. В частности, для данной последовательности {x 1,... x m } экземпляров A таких, что x i ∈ A влечет x i -1 ∈ A, требуется редукция, которая дает такой экземпляр y, что y ∈ B тогда и только тогда, когда число x i ∈ A нечетно или четно:

BH2k-твердость равна доказано, если $m = 2 k {\ displaystyle m = 2k}$ ${\ displaystyle m = 2k}$ и число x i ∈ A нечетно
BH2k + 1 -твердость равна доказано, если $m = 2 k + 1 {\ displaystyle m = 2k + 1}$ ${\ displaystyle m = 2k + 1}$ и число x i ∈ A четно

Такие сокращения работают для каждого фиксированный k. Если такие сокращения существуют для произвольного k, проблема сложна для P.

Ссылки

^Chang, R.; Кадин, Дж. (1996). «Булевы иерархии и полиномиальные иерархии: более тесная связь». SIAM J. Comput. 25(25): 340–354. CiteSeerX 10.1.1.77.4186. doi : 10.1137 / S0097539790178069.
^Зоопарк сложности : Класс BH
^Зоопарк сложности : DP класса
^ Вагнер, К. ( 1987). «Более сложные вопросы о максимумах и минимумах и некоторых замыканиях NP». Теорет. Comput. Sci. 51: 53–80. doi : 10.1016 / 0304-3975 (87) 90049-1.
^Riege, T.; Роте, Дж. (2006). "Полнота в булевой иерархии: точное четырехкратное раскрашивание, минимальная некрашируемость графа и проблемы с точным доматическим числом - обзор". Дж. Универс. Comput. Sci. 12(5): 551–578.