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

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

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

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

• BH ₁ представляет собой NP .
• BH _{2 k} — класс языков, являющихся пересечением языка из BH _{2 k -1} и языка из coNP .
• BH _{2 k +1} — класс языков, представляющих собой объединение языка из BH _{2 k} и языка из NP .
• BH — объединение всех классов BH _i .

Производные классы

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

определения

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

• C ∧ D знак равно { А ∩ B | А € С В € D }
• C ∨ D знак равно { А ∪ B | А € С В € D }

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

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

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

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

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

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

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

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

Твердость

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

• BH _{2 k} -твердость доказана, если $m=2k$ и число x _i ∈ A нечетно
• BH _{2 k +1} -трудность доказана, если $m=2k+1$ и число x _i ∈ A четно

Такие сокращения работают для любого фиксированного k . Если такие редукции существуют для произвольного k , проблема сложна для P ^{NP[ O (log n )]} .