Computational complexity seems to be used quite a lot in cryptographic papers.

The time complexity I am referring to is the one from Computational Complexity Theory.

Are these two the same things?


There are many different cost models for computation, of which time (measured by some clock) is only one.

  • How many seconds must we wait to run this algorithm? [time, measured in seconds]
  • How many CPU cycles does it cost run this algorithm? [time, measured in CPU cycles]
  • How many bits of memory does this algorithm use? [space]
  • How many NAND gates does it take to represent this algorithm as a logic circuit? [NAND metric]
  • How many bits are in the description of the program, how many bits of memory does it use, and how long does it take to run assuming a bit operation and a memory reference each take one unit of time? [RAM metric]
  • How large a silicon die does it take to run this algorithm, and for how long must we power it? [AT metric]
  • How many joules of energy will it cost to run this algorithm? [energy]
  • How many yen does it cost to run this algorithm? [pocketbook]

The answer to each of these questions may be a complicated function of the size of the input, or of the input itself. For example, the worst-case RAM cost of quicksort is a quadratic polynomial function of the input size, $an^2 + bn + c$, for some coefficients $a$, $b$, and $c$ that depend on exactly how we write it, while on optimal inputs the RAM cost is $u n + v$.

Complexity theory is usually not concerned with the coefficients $a$, $b$, and $c$ but with the degree of the polynomial, $O(n^2)$ vs. $O(n)$, or other qualitatively different shapes of growth curves like $O(2^n)$, $O(\log n)$, $O(A^{-1}(n))$ where $A(n)$ is the Ackermann function, etc., in whichever cost model you're considering.

Computational complexity may refer to any of the cost models; time complexity usually just refers to the time-based ones—for example, the time complexity of heap sort is $O(n \log n)$ while the space complexity is $O(n)$, assuming memory access cost is constant, yet in the more realistic AT metric the best-known cost of sorting a length-$n$ array of $n$-bit numbers is $n^{1.5 + o(1)} = (n\sqrt n)^{o(1)}$ owing in part to communication costs on a silicon mesh.

The last three cost models are the really important ones for studying cryptanalytic attacks, because they are connected to real-world economic costs of attacks: the AT metric, which is easy to formalize and study for algorithms, is a good proxy for the energy cost, and energy cost essentially determines pocketbook cost.

  • 1
    $\begingroup$ It's still quite unclear as to the difference between computational complexity and time complexity from your answer. I understand that there are many different cost models from your answer $\endgroup$ Aug 23 '19 at 18:13
  • 2
    $\begingroup$ @WeCanBeFriends computational complexity is a wider definition that encompass time complexity (AFAICT) and also other complexities. It's the sum of all practical complexities affecting your cost and speed of computation. $\endgroup$
    – Natanael
    Aug 23 '19 at 19:35
  • $\begingroup$ @WeCanBeFriends: The difference between computational complexity and time complexity is the same as the difference between a vehicle and a Toyota Camry. $\endgroup$ Aug 26 '19 at 15:21

In short: Yes.

Complexity theory makes a distinction, where you don't care about time and only limit space. And there are still interesting differences there in theory. That case isn't considered when cryptographers talk about computational complexity, because in that scenario, a Brute Force algorithm will always win - which is not very interesting.

Btw., keep in mind, limiting time automatically limits space. For example you can not read or write exponentially many bits when the time complexity is polynomial.

  • $\begingroup$ To re-iterate; so cryptographers, disregard space complexity for the most part, and so computational complexity can be seen as time complexity? You mentioned "in short", so I'm guessing that I cannot simply replace all mentions of "computational complexity" with "time complexity" without losing meaning? $\endgroup$ Aug 23 '19 at 18:16
  • $\begingroup$ @WeCanBeFriends usually yes. Exceptions involve memory hard functions for password hashing and similar techniques. $\endgroup$
    – Natanael
    Aug 23 '19 at 19:37
  • 3
    $\begingroup$ Cryptographers do not generally disregard space complexity. Sometimes they do, but that often leads to wildly unrealistic cost estimates for algorithms like the alleged MD5 preimage attack which are actually far more expensive than generic attacks. A bound on time implies a bound on space, but the converse is not true. $\endgroup$ Aug 24 '19 at 0:11
  • $\begingroup$ @WeCanBeFriends I would say, cryptographers care about the overall picture and realistic settings (with fairly large margins over the current global limits of computation and known algorithms). The mindset 'disregard one aspect for theory's purpose' is only part of the mindset in complexity theory. That's why I stated, you can't disregard space in either field - only limiting time and not space makes no sense in either field (unless you allow reading and writing unlimited information per operation, like working with numbers with infinite precision. Which isn't realistic in classical computing) $\endgroup$
    – tylo
    Aug 24 '19 at 22:25

Your Answer

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

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