8
$\begingroup$

When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.

My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.

Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$. The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time. For example:

  • The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
  • The maximum element in an array can be found in recursive time $O(1)$.
  • The recursive runtime of merge sort is $O(n)$, because of the merging step.

The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.

Now my question is:

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?

Some specific variants of this question are:

  • Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
  • Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.

Improve this question
$\endgroup$
9
  • $\begingroup$ Maybe proving a kernelization lower bound would do the trick en.wikipedia.org/wiki/Kernelization $\endgroup$
    – Tyson Williams
    Oct 17, 2014 at 15:22
  • $\begingroup$ The output size is a lower bound on the running time. Thus any problem with output size matching its complexity has this property. $\endgroup$
    – Chao Xu
    Oct 17, 2014 at 15:53
  • $\begingroup$ @Chao Xu: Why doesn’t your argument apply to the input size? I think that the argument depends on which cost model (and computational model) we consider. $\endgroup$
    – Tsuyoshi Ito
    Oct 18, 2014 at 2:31
  • 2
    $\begingroup$ This is the opposite of what you're looking for, but given those oracles your model can solve subset sum - a known NP-Complete problem - in linear time, thus assuming P!=NP it's much more powerful than iterative functions in this case. The function would simply check if the current set adds to 0, then if not it calls itself on the n subsets of size n-1. The runtime itself is n! however, which is worse than brute force, so I'm not really sure how much value this model provides, but it's still an interesting question. $\endgroup$
    – Phylliida
    Oct 18, 2014 at 5:32
  • 2
    $\begingroup$ Your recent edit ("recursive" -> "divide-and-conquer") is a pretty big change to the question. I would just post a separate question instead. We can probably say things about divide-and-conquer by looking for instance at the depths of circuits. $\endgroup$
    – usul
    Oct 20, 2014 at 13:25

3 Answers 3

Reset to default
8
$\begingroup$

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

Yes. Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P. There is a tally language in E∖P by a standard diagonalization argument.

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?

It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.

Random comments on your questions in this post:

  • I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest. As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense. Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
  • In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
  • Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Regarding your first answer: let me try to expand it to see if I understand correctly. Assume that a certain tally language has an algorithm with polynomial "recursive runtime". A polynomial algorithm for this language can be constructed using dynamic programming. The answer for $n=0$ can be found in polynomial time since no recursive calls are required. The answer for $n=1$ can then be found in polynomial time using the answer for $n=0$. Then answer for $n=2$ can be found in polynomial time using the answers for $n=1$ and $n=0$, etc. Is this correct? $\endgroup$
    – Erel Segal-Halevi
    Oct 18, 2014 at 20:18
  • $\begingroup$ Yes, although it is better to avoid asymptotic notions such as “polynomial time” when you talk about a particular value of n; for example, it does not make sense to say “the algorithm runs in polynomial time when n=0.” If a tally language has a “recursive algorithm” with polynomial “recursive runtime” p(n), then we can compute the answer for n without the oracle by computing the answers for 0, 1, 2, …, n, and this takes time $O(\sum_{i=0}^n p(i))$, which is polynomial in n. $\endgroup$
    – Tsuyoshi Ito
    Oct 18, 2014 at 20:33
  • $\begingroup$ Thanks. I agree with your comment about divide-and-conquer and I edited the question accordingly. $\endgroup$
    – Erel Segal-Halevi
    Oct 20, 2014 at 7:30
0
$\begingroup$

Any question which has recursive answer has iterative answer and vice versa.

Any recursive algorithm can be rewritten in iterative way and vice versa.

Hence, your question doesn't stand good.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ The complexity of an algorithm, as I defined it in the question, generally does not remain the same when it is converted from iterative to recursive. For example, the maximum of n elements can be found by an iterative algorithm with O(n) operations, but it can also be found by a recursive algorithm with O(1) operations (one of which is a recursive call). Although finally the runtime of both algorithms is the same, the recursive algorithm is simpler to program because it has less operations. $\endgroup$
    – Erel Segal-Halevi
    Oct 17, 2014 at 14:19
-2
$\begingroup$

I am not sure if I correctly understand your notion of "recursive complexity".

Lets (reasonably) Assume a programming language that contains a schema for primitive recursion i.e. in which one can define functions $f$ from

$$ f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x) $$

where $c$ and $g$ are previously defined functions. Further let us assume that the basic functions (constants, projections, successor) have $\mathcal{O}(1)$ "recursive complexity" If I understand your definition correctly, then all primitive recursive functions (and thus problems/relations) have $\mathcal{O}(1)$ "recursive runtime". This, I think, can be seen by induction on the build up of recursive functions.

If all my assumptions are met, then the example you are looking for cannot be primitive recursive.

Improve this answer
$\endgroup$
5
  • $\begingroup$ please elaborate on the downvotes $\endgroup$
    – D.F.F
    Jan 11, 2016 at 16:20
  • $\begingroup$ From the question, "The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time." . This definition of runtime gives naturally a rise to a complexity measure. This is a fancy way of saying that we do not care about the cost of lower size recursions, but only of the current step. So in your notation, we ask what is the complexity of comuting $g(f(n,x),n,x)$ given an oracle for $f(n,x)$ that has constant runtime. I didn't downvote you, but this is a year-old answered question and you also misinterpreted a given definition. $\endgroup$
    – chazisop
    Jan 12, 2016 at 9:08
  • $\begingroup$ thanks for your comment. I think I understood the definition. Since $g$ is a prim. rek. function, by induction hypothesis it has runtime $\mathcal{O}(1)$ since $f(n,x)$ is given by the oracle in constant time, evaluating the whole expression takes $\mathcal{O}(1\circ 1)=\mathcal{O}(1)$. $\endgroup$
    – D.F.F
    Jan 12, 2016 at 11:15
  • $\begingroup$ You have to use the full complexity for $g$, not its recursive complexity. That's not $O(1)$. $\endgroup$
    – Emil Jeřábek
    Jan 14, 2016 at 10:30
  • $\begingroup$ ahh, ok... now everything makes sense... thanks for the clarification... I was probably confused by the fact that recursive complexity is not invoked recursively^^ (which is not very celar from the definition imo) $\endgroup$
    – D.F.F
    Jan 14, 2016 at 10:40

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.