# Making sense of the various definitions of computational complexity

I'm a math student and have encountered the concept of computational complexity in several subjects in the course of my studies (numerical analysis, cryptography, intro to computer science and programming), although, having never taken a course in theoretical computer science, I have never had to deal with it from a theoretical point of view. I'm posting this thread because the definitions of complexity I have come across are quite different, and don't seem to be equivalent; I'm looking for a standard model for (mainly time) complexity which can be applied in the analysis of algorithms implemented in a high level programming language (such as C, or more informally pseudocode). Browsing through lecture notes of computer science professors, I came across definitions of complexity for algorithms implemented in low level languages, such as turing machines or RAMs; but these aren't easily applicable to algorithms implemented in C. Given an algorithm in a high level programming language, my main doubts are:

• Which operations are to be considered "fundamental operations", those having a cost $=1$ in terms of time units. In cryptography, for example, we dealt with bit operations, wheras in other courses any single arithmetic operation was considered to have cost $=1$. Is this the distinction between uniform and logarithmic cost models?

• Does changing cost model, or considering best, worst or average case affect the composition of complexity classes such as $P$ and $NP$ ? I'm asking this because these are often brought up without particular reference to context.

• Do assingments (or any other manipulation of memorized data) count as operations, or can they be disregarder altogether in the analysis of an algorithm? Couldn't this make quite a difference, for example, in cycles, with assingments such as i:=i+1?

Sorry if this sounds too vague...thanks to anybody who can help!

1. The classical complexity classes (P, NP, LOGSPACE, etc) are defined formally starting from a Turing cost model -- that is we count resources used by a Turing machine that solves the problem. It turns out, however, that this detail is not really relevant for classes such as P and NP, because a Turing machine can simulate most other realistic models of computation with at most polynomial slowdown. So NP relative to a RAM ends up being the same as NP relative to Turing machines.

As far as complexity is concerned, C can be viewed as a RAM with unit-cost basic arithmetic and bitwise operations -- except that this does not model the fact that C (or rather the real computers we program with it) has a limited word length. Allowing unlimited integers in C programs leads to anomalies, because one can quickly build very large numbers using multiplication, and then use those to pack unlimited parallelism into the unit-cost arithmetic operations. Totally unrealistic, of course.

What one usually does about this problem is sweep it under the rug and pretend it doesn't exist. Any polynomial-time C program that one can reasonably imagine running on a real computer can be simulated in polynomial time on a Turing machine (though probably a polynomial of higher degree), so that thinking about such programs suffices for understanding, say, $P\overset ?= NP$.

However, if one wants to face the problem more explicitly, then natural strategy would be to work in a restricted C-like model that includes a word length restriction. It won't do to insist on a fixed word size (as in reality), because then for large enough problem instances, the restricted C model won't even be able to index enough memory to store the problem itself -- but complexity is all about asymptotic behavior, so we must be able to contemplate arbitrarily large problem instances being solved by our programs. I don't know if there's any completely standard assumption here, but it seems reasonable to say that the program must work with a word length that is a fixed multiple of the shortest word that can represent the size of the input. This ought to allow representing algorithms up to PSPACE fairly naturally -- and in the other direction it lets us characterize LOGSPACE as problems solvable by programs with bounded recursion depth that don't allocate memory dynamically (but are given a read-only pointer to the input).

When one speaks of finer distinctions than the classical polynomial-or-not, such as the $O(n)$, $O(n^2)$, $O(n\log n)$ classes one learns about in introductory algorithmics, it is usually tacitly understood that this "RAM with unit-cost arithmetic up to a logarithmic word size" model unless something else is explicitly specified -- that is, unit cost except that you're must write the program such that it doesn't exceed the word size you announce it will need, and be prepared too prove this if challenged. (I believe this is equivalent to a logarithmic-cost model for arthimetic, since one can imagine implementing a bignum library using a limited word length -- multiplication and division may need $\log^2$-cost, though).

2. The classical complexity classes (again, such as P and NP) are always measured as worst-case times. Doing a best case analysis would collapse a lot of problems to "really fast"; for example there are SAT problems of all sizes that can be recognized to belonging to trivial special cases in linear time. Average case is not as obviously useless -- but it is not simple to compare the hierarchy that results, because the problems for average-case look different from the problems for worst-case: an average-case problem must include a sequence of probability distributions on the possible inputs of various sizes.

3. Yes -- in the "modified RAM" or "C-like" model I speak about above (which I claim to be the underlying model of most actual complexity analysis), copying an integer is indeed a unit-cost operation. It is a different matter in the classical "counter RAM" model, of course (where a programmed copying operation takes time linear in the number being copied), or in the Turing model (where it is slower yet).

At least, charging cost $1$ for an assignment is the easiest model to defend and motivate. One could also choose to assign zero cost to assignment and arithmetic! Unrealistic though this sounds, it leads to exactly the same asymptotic complexities as unit cost, as long as jumps still cost something. This is because constant factors don't matter in asymptotic analysis, and between two jumps the program can do a bounded amount of arithmetic and assignments. In fact, for a C program all you really need to count is (a) the number of times you start executing a loop body, plus (b) the number of possibly recursive function calls you make. Doing so can simplify the bookkeeping of analyzing a concrete algorithm a great deal -- as long as you're only interested in the big-O behavior!

• Thank you very much for your answer. By "RAM with unit-cost arithmetic up to a logarithmic word size" do you mean the logarithmic cost model (for example, 1 bit operation = 1 time unit working in base 2)? I had read about the invariance of $P$ and $NP$ when changing theoretical model (adding tapes and registers), but does this also apply when changing from logarithic cost to uniform cost model? – Emilio Ferrucci Dec 30 '11 at 20:13
• One weird effect of allowing all operations to be unit cost is that by supplying the innocuous floor function to an algorithm, you can solve PSPACE-complete problems in poly time by doing as Henning mentioned and then using the floor to "pick out" the answer. – Suresh Venkat Dec 30 '11 at 20:15
• One last thing: as you said in your answer, copying and integer does have a unit cost. I have frequently noticed that this detail is overlooked, for example, i quote from Koblitz - A Course in Number Theory and Cryptography: "we shall define a "time estimate" [...] without including any consideration of shift operations,changing registers ( "copying" ), memory access, etc.". Are there any theoretical results, or examples establishing whether these operations make a difference in the complexity analysis of an algorithm? Thanks again for your help :-) – Emilio Ferrucci Dec 30 '11 at 20:19
• @Emilio: I have edited the answer in an attempt to answer your follow-up questions. (I believe P is not stable under unit cost for unlimited-size arithmetic -- you need either logarithmic cost or the fixed-word-length assumption I describe). – Henning Makholm Dec 30 '11 at 22:28
• @Emilio: What I'm asserting is that zero-cost for non-jumps is asymptotically equivalent to unit-cost. Your $c(i)$ does not work with unit-cost, so it is no wonder (and no contradiction) that zero-cost doesn't work either. Also note that such a $c(i)$ does not actually exist in C -- it would need to be implemented as a function call with one or more internal loops, whose iterations would be counted in my scheme. – Henning Makholm Dec 30 '11 at 23:14