0
$\begingroup$

There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class?

For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity?

By converting into elementary recursive form, I mean:

Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form.

By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else".

Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $x$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity).

Improve this question
$\endgroup$
8
  • $\begingroup$ Note that ELEMENTARY is more alike to PR, R and RE in that it defines a model of computation, not so much a complexity class. But still, since we can simulate representations of an algorithm in every (known) Turing complete machine model with polynomial overhead, I think something similar may hold for weaker models. $\endgroup$
    – Raphael
    Apr 14, 2013 at 11:29
  • 1
    $\begingroup$ Every function in NP is in Elementary by definition. What do you mean by converting them to elementary form? Do you mean using expressing it using the basis? If so then the question is meaningless, unless you define what is the time complexity of them. $\endgroup$
    – Kaveh
    Apr 14, 2013 at 17:56
  • $\begingroup$ The previous comment still applies. Voting to close as not-a-real-question. $\endgroup$
    – Kaveh
    Apr 16, 2013 at 9:23
  • 1
    $\begingroup$ @Kaveh I don't follow. Usual assumptions make the question well-defined, e.g. counting elementary operations. $\endgroup$
    – Raphael
    Apr 16, 2013 at 9:27
  • 1
    $\begingroup$ @PålGD That may be so, but that is an answer, not a reason to close the question. $\endgroup$
    – Raphael
    Apr 18, 2013 at 8:18

1 Answer 1

Reset to default
1
$\begingroup$

This depends highly on the encoding. If you consider bounded summation, the number of summations done is the value of the first argument of the function.

If the "encoding" (whatever that means) of the input is unary, this takes linear time, otherwise it takes exponential time in the size of the input. It is not obvious that it makes sense to assume input to be unary.

Elementary recursive functions are over natural numbers and do not speak of their encoding: is $s(0)$ encoded as $1$ or as $s0$?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Now that I think about it, this does not quite answer the question. You correctly exhibit that for "reasonable" input encodings, ELEMENTARY does contains functions with exponential "runtime", which is no surprise. But we don't know yet whether there are representations of polynomial time TM-algorithms without summations/multiplications with length depending on the input. $\endgroup$
    – Raphael
    Apr 18, 2013 at 8:58

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