# What complexity class decision problems can be solved by only addition, multiplication, division and subtraction?

So in what complexity class would all decision problems in that class can be transformed into a problem (by many-one reduction) that its solution only involves basic arithmetic operation of multiplication, division, addition and subtraction?

So, like this: for every problem, there is input and output (we consider only those that halt) and my question is that is there any complexity class that all problems in the class can be transformed into a problem that involves only elementary arithmetic of the form of arithmetic function involving only arithmetic like $2^x+x^5/4-4x+2$ where $x$ is input coded as natural number.

• What do you mean by "it's solution involves..."? If you have addition modulu 2, and multiplication modulu 2, then you have a complete Boolean system, and technically you can do anything a circuit does. Please define the model more carefully. – Shaull Apr 12 '13 at 17:03
• Do you mean, for what $L \subset \mathbb{N}$, does there exist a rational function $f$, such that $f(x) = 1 \leftrightarrow x \in L$? – Karolis Juodelė Apr 12 '13 at 17:06
• @KarolisJuodelė - It sounds as though other functions are possible too, such as iterated fractions, perhaps. – Shaull Apr 12 '13 at 17:42
• this is not well defined unless you add other constraints eg some kind of conditional logic, limits on size of formulas, etc – vzn Apr 12 '13 at 18:12
• So exponentiation is a basic arithmetic operation too? Or is that iteration? Give a complete list. Also, how do you encode the result? If $x \in L$ means $f(x) = 1$ then you'll get a different set of languages than if you chose it to mean $f(x) > 0$. – Karolis Juodelė Apr 13 '13 at 6:47

You can get more functions (the Primitive Recursive functions) by additionally allowing functions that call themselves (but are guaranteed to terminate). Finally, you can get the class of all Turing-computable functions by introducing a minimization operator: find the minimum $x$ such that $f(x) = 0$.
Anyway, it turns out that $\mathsf{EXPTIME} \subsetneq \mathsf{ELEMENTARY}$, so it includes many (most?) problems that we'd usually consider interesting.