What is the complexity of the following problem? I can see it's in NP for reasonable definitions of closed form, is there anything else one can say about it?

Given a recurrence relation $R_0 = \alpha_0,... ,R_n = \alpha_n, R_{f_2(n)} = g(R_{f_1(n)})$, $f_1(n) < f_2(n)$, where $f_1, f_2$, and $g$ are in closed form (for some reasonable definition of closed form, you pick; for example one could consider a solution in terms of $H_n$ closed form) and an integer $k$, find a closed form expression for $R_n$ expressible in less than k bits

  • 3
    $\begingroup$ IIRC, solving recurrences is not computable. 1) How do you deal with irrational or, worse, uncomputable numbers? 2) Even solving equation systems of moderate degree is uncomputable. For a computable subset, you need to severly restrict $g$ (and the $f_i$, I guess). Note that you don't even require that they be computable! For instance, linear equation systems can always be solved with computer algebra. $\endgroup$ – Raphael Feb 26 '16 at 21:59
  • 2
    $\begingroup$ How can you see that it's in NP? For it to be in NP, you need the expression for the solution to have length bounded by some polynomial in the length of the input. It's not at all obvious that this should be the case; indeed, for the similar-sounding problem of finding integer roots of Diophantine equations, this isn't the case (in fact, it's undecidable whether a Diophantine equation has any integer roots). $\endgroup$ – David Richerby Feb 26 '16 at 23:43
  • 1
    $\begingroup$ Even under the new edit it's not clear that the problem is in NP, since it's not clear how you would verify in polynomial time that a given closed form expression indeed satisfies the recurrence. $\endgroup$ – Yuval Filmus Feb 27 '16 at 21:32

Your Answer

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

Browse other questions tagged or ask your own question.