Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
These sound like the primitive recursive functions. –  Yuval Filmus Oct 13 '12 at 18:03
4  
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  
    
@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). –  CommuSoft Oct 14 '12 at 23:31
    
@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 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

This is the language Bloop as describes by Hofstaedter.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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