1
$\begingroup$

I've written an unpublished paper that describes FOR-programs.

FOR-programs are programs that only contain bounded for loops and basic operations (assignment, addition, multiplication, etc.). A bounded for loop is a for loop with a bound on the number of times that it can loop. This bound is fixed before entering the for loop for the first time and is not changed until the loop completes.

Is there a complexity class that captures this type of programs? Since the number of for loops in a program is known in advance, the time complexity is of course limited to $O(n^k)$ with $k$ nested for loops. Thus, all FOR-programs run in polynomial time. Are there additional limitations to this class of programs?

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ These sound like the primitive recursive functions. $\endgroup$
    – Yuval Filmus
    Commented Oct 13, 2012 at 18:03
  • 5
    $\begingroup$ These programs are not bounded to polynomial time. If you interpret the input (perhaps expressed in binary) as an integer, it may be polynomial in the value of the integer; but not in the length of its representation. For instance, a program unsigned int identity(unsigned int x) { unsigned int y; for (y = 0; y < x; y++); return y; } performs $x$ iterations, which requires $\Omega(x) = \Omega(2^n)$ time, where $n = |x|$ is the length of the representation of $x$, i.e. $n = \lceil \log_2(x+1) \rceil$ for $x \geqslant 0$. $\endgroup$
    – Niel de Beaudrap
    Commented Oct 13, 2012 at 23:05
  • 1
    $\begingroup$ Related: cstheory.stackexchange.com/questions/5120/… $\endgroup$
    – Radu GRIGore
    Commented Oct 14, 2012 at 9:40
  • $\begingroup$ @NieldeBeaudrap: true (I was more interested on the effects on arrays: what if the counters can't be modified before they are used on arrays, but somehow I didn't post that part). $\endgroup$
    – willeM_ Van Onsem
    Commented Oct 14, 2012 at 23:31
  • 1
    $\begingroup$ @CommuSoft: what you mean is still not clear. Do you mean that the input must be an array, and all loops are in terms of the size of the array? Please revise your question to state quite precisely what it is that you mean, because it is quite likely to have a bearing on what the answer will be. $\endgroup$
    – Niel de Beaudrap
    Commented Oct 14, 2012 at 23:52

2 Answers 2

Reset to default
4
$\begingroup$

Having just asked a very similar question:

The language of for programs can express exactly the primitive recursive functions -- see Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465. (I found a copy online here.)

The complexity class for the p.r. functions is called PR.

Improve this answer
$\endgroup$
3
$\begingroup$

This is the language Bloop as describes by Hofstaedter.

Improve this answer
$\endgroup$

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.