Exponenciální hierarchie - Exponential hierarchy

v teorie výpočetní složitosti, exponenciální hierarchie je hierarchie třídy složitosti, což je exponenciální čas analog polynomiální hierarchie. Stejně jako jinde v teorii složitosti se „exponenciální“ používá ve dvou různých významech (lineární exponenciální hranice ${ displaystyle 2 ^ {cn}}$ pro konstantu Ca plné exponenciální hranice ${ displaystyle 2 ^ {n ^ {c}}}$), což vede ke dvěma verzím exponenciální hierarchie.^[1][2]

EH

EH je spojení tříd ${ displaystyle Sigma _ {k} ^ { mathsf {E}}}$ pro všechny k, kde ${ displaystyle Sigma _ {k} ^ { mathsf {E}} = { mathsf {NE}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}}$ (tj. jazyky vypočítatelné v nedeterministické čas ${ displaystyle 2 ^ {cn}}$ pro nějakou konstantu C s ${ displaystyle Sigma _ {k-1} ^ { mathsf {P}}}$ věštec ). Jeden také definuje

${ displaystyle Pi _ {k} ^ { mathsf {E}} = { mathsf {coNE}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}, Delta _ {k } ^ { mathsf {E}} = { mathsf {E}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}.}$

Ekvivalentní definicí je, že jazyk L je v ${ displaystyle Sigma _ {k} ^ { mathsf {E}}}$ pouze a jen v případě, že to lze zapsat do formuláře

${ displaystyle x v L iff existuje y_ {1} for all y_ {2} dots Qy_ {k} R (x, y_ {1}, ldots, y_ {k}),}$

kde ${ displaystyle R (x, y_ {1}, ldots, y_ {n})}$ je predikát vypočítatelný v čase ${ displaystyle 2 ^ {c | x |}}$ (což implicitně omezuje délku y_i). Ekvivalentně také EH je třída jazyků vypočítatelných pro střídavý Turingův stroj včas ${ displaystyle 2 ^ {cn}}$ pro některé C s neustále mnoha střídáním.

EXPH

EXPH je spojení tříd ${ displaystyle Sigma _ {k} ^ { mathsf {EXP}}}$, kde ${ displaystyle Sigma _ {k} ^ { mathsf {EXP}} = { mathsf {NEXP}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}}$ (jazyky vypočítatelné v nedeterministickém čase ${ displaystyle 2 ^ {n ^ {c}}}$ pro nějakou konstantu C s ${ displaystyle Sigma _ {k-1} ^ { mathsf {P}}}$ Oracle) a znovu:

${ displaystyle Pi _ {k} ^ { mathsf {EXP}} = { mathsf {coNEXP}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}, Delta _ {k } ^ { mathsf {EXP}} = { mathsf {EXP}} ^ { Sigma _ {k-1} ^ { mathsf {P}}}.}$

Jazyk L je v ${ displaystyle Sigma _ {k} ^ { mathsf {EXP}}}$ právě tehdy, když lze zapsat jako

${ displaystyle x v L iff existuje y_ {1} for all y_ {2} dots Qy_ {k} R (x, y_ {1}, ldots, y_ {k}),}$

kde ${ displaystyle R (x, y_ {1}, ldots, y_ {k})}$ je vypočítatelný v čase ${ displaystyle 2 ^ {| x | ^ {c}}}$ pro některé C, což opět implicitně omezuje délku y_i. Ekvivalentně je EXPH třída jazyků vypočítatelných v čase ${ displaystyle 2 ^ {n ^ {c}}}$ na střídavém Turingově stroji s neustále mnoha střídáním.

Srovnání

E ⊆ NE ⊆ EH ⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE,

EH ⊆ EXPH.

Reference

externí odkazy

Složitost Zoo: Třída EH