Booleovská hierarchie - Boolean hierarchy

The booleovská hierarchie je hierarchie z booleovský kombinace (průsečík, svaz a doplňování ) z NP sady. Ekvivalentně lze logickou hierarchii popsat jako třídu booleovské obvody přes NP predikáty. Kolaps booleovské hierarchie by znamenal kolaps polynomiální hierarchie.^[1]

Formální definice

BH je definována takto:^[2]

• BH₁ je NP.
• BH_2k je třída jazyků, kterými jsou průsečík jazyka v BH_2k-1 a jazyk v coNP.
• BH_2k+1 je třída jazyků, kterými jsou svaz jazyka v BH_2k a jazyk v NP.
• BH je svazkem BH_i

Odvozené třídy

• DP (Difference Polynomial Time) je BH₂.^[3]

Ekvivalentní definice

Definování konjunkce a disjunkce tříd následujícím způsobem umožňuje formovat kompaktní definice. Spojení dvou tříd obsahuje jazyky, které jsou průsečíkem jazyka první třídy a jazyka druhé třídy. Disjunkce je definována podobným způsobem jako spojení na místě křižovatky.

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

Podle této definice je DP = NP ∧ coNP. Ostatní třídy booleovské hierarchie lze definovat následovně.

${ displaystyle { mathsf {BH}} _ {2k} = { mathsf {coNP}} klín { mathsf {BH}} _ {2k-1}}$

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

Následující rovnosti lze použít jako alternativní definice tříd Booleovské hierarchie:^[4]

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

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

Alternativně,^[5] pro každého k ≥ 3:

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

Tvrdost

Tvrdost pro třídy booleovské hierarchie lze prokázat ukázáním redukce z řady případů libovolného NP-kompletní problém A. Zejména vzhledem k posloupnosti {X₁, ... X_m} případů A takový, že X_i ∈ znamená X_i-1 ∈ A, je nutná redukce, která vytvoří instanci y takhle y ∈ B právě tehdy, pokud počet X_i ∈ je liché nebo sudé:^[4]

• BH_2k- tvrdost je prokázána, pokud ${ displaystyle m = 2k}$ a počet X_i ∈ A je zvláštní
• BH_2k+1- tvrdost je prokázána, pokud ${ displaystyle m = 2k + 1}$ a počet X_i ∈ A je sudé

Taková snížení fungují pro každou fixní k. Pokud takové snížení existuje libovolně k, problém je pro P^{NP [Ó(log n)]}.

Reference

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.