1

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?

Community
  • 1
willeM_ Van Onsem
  • 377
  • 1
  • 12
  • 7
    These sound like the primitive recursive functions. – Yuval Filmus Oct 13 '12 at 18:03
  • 5
    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$. – Niel de Beaudrap Oct 13 '12 at 23:05
  • 1
    Related: http://cstheory.stackexchange.com/questions/5120/programming-languages-for-efficient-computation – Radu GRIGore Oct 14 '12 at 09:40
  • @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). – willeM_ Van Onsem Oct 14 '12 at 23:31
  • 1
    @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. – Niel de Beaudrap Oct 14 '12 at 23:52

2 Answers2

4

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.

Community
  • 1
Chris Pressey
  • 380
  • 2
  • 7
3

This is the language Bloop as describes by Hofstaedter.

Dave Clarke
  • 16,666
  • 3
  • 60
  • 106
bloop
  • 31
  • 1