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.

  • 3
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Apr 12 '13 at 17:03
  • $\begingroup$ 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$? $\endgroup$ Apr 12 '13 at 17:06
  • $\begingroup$ @KarolisJuodelė - It sounds as though other functions are possible too, such as iterated fractions, perhaps. $\endgroup$
    – Shaull
    Apr 12 '13 at 17:42
  • 1
    $\begingroup$ this is not well defined unless you add other constraints eg some kind of conditional logic, limits on size of formulas, etc $\endgroup$
    – vzn
    Apr 12 '13 at 18:12
  • $\begingroup$ 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$. $\endgroup$ Apr 13 '13 at 6:47

The question isn't exactly well-defined, but seems like a good/interesting question to me. I believe the answer you might be looking for is the class of Elementary Recursive functions. This class consists of almost exactly what you described: Problems solvable by functions that can be written with only addition, subtraction, and multiplication of integers. (Except, we also require a zero function and a "projection" function that outputs one of the inputs.)

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.

  • $\begingroup$ Cool, didn't know this class. It's interesting to me that ELEMENTARY is less powerfull than PR even though it has little more than iterated addition with known bound, too. $\endgroup$
    – Raphael
    Apr 14 '13 at 10:44
  • 1
    $\begingroup$ @Raphael - agreed! It's kind of an interesting "syntactic" limitation, that you just can't write down hyper-exponentiation (tetration) using only products and sums. $\endgroup$
    – usul
    Apr 14 '13 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.