Abstract:

We consider a computational complexity theory over arbitrary algebraic structures based on an approach to generalized computability developed by Ashaev, Belyaev and Myasnikov. Let $\mathcal{R}$ be a ring with a nilpotent element $\eta$ of nilpotency index $k>1$ such that $\eta$ is an algebraic element over $\mathbb{Z}$ of degree $k$. We prove that analogs of the classical computational complexity classes $\bf{P}$ and $\mathbf{NP}$ over $\mathcal{R}$ are different.