Class Description

ModL: ModL

A language ${\displaystyle L\in {\mathsf {ModL}}}$ if there are functions ${\displaystyle f\in {\mathsf {GapL}}}$ and ${\displaystyle g\in {\mathsf {FL}}}$ such that for all strings ${\displaystyle x}$:

• There exists a prime ${\displaystyle p}$ and a natural number ${\displaystyle \alpha }$ such that ${\displaystyle g(x)=0^{p^{\alpha }}}$.
• ${\displaystyle x\in L}$ if and only if ${\displaystyle f(x)\equiv 0(\left|g(x)\right|)}$.

Thus, for any prime ${\displaystyle p}$ and natural number ${\displaystyle \alpha }$, ${\displaystyle {\mathsf {Mod}}_{p^{\alpha }}{\mathsf {L}}\subseteq {\mathsf {ModL}}}$. Moreover, FL^ModL = FL^GapL [AV04].

Defined in [AV04].

Linked From

No class.