1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 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
    Commented Apr 12, 2013 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$
    – Karolis Juodelė
    Commented Apr 12, 2013 at 17:06
  • $\begingroup$ @KarolisJuodelė - It sounds as though other functions are possible too, such as iterated fractions, perhaps. $\endgroup$
    – Shaull
    Commented Apr 12, 2013 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
    Commented Apr 12, 2013 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$
    – Karolis Juodelė
    Commented Apr 13, 2013 at 6:47

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 14, 2013 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
    Commented Apr 14, 2013 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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