Say you have shown on paper that some algorithm is easy to compute (polynomial time with respect to input size $|X|$. It is clear to me that for a practical machine (essentially any current computer available to me, in the world), solution to a given problem with sufficiently large input size, is not only hard to compute the answer to, but impossible! The impossibility would come from the computer not being able to store any "faithful" representation of the output.

What axioms address this concern, or is it just neglected to be addressed across the board?

It seems like a good idea to consider the theoretical machine to have an infinite number of possible symbols (versus the 256 possible bytes), and an infinite amount of memory (versus the finite memory on a real machine). Where an algorithm is only considered possibly easy in time complexity if it has a finite representation on said infinite machine. Therefore, for some problems that are theoretically, actually easy to compute; they may be impossible to represent faithfully (in general) and compute on my home computer.

This is a highly confusing aspect of time complexity for me, and I am currently not comfortable with ignoring it. Take any general problem, such as sorting a list. If I can't even fit the list on my machine, then what!? Another example: multiplying two big integers in general "is easy" assumes that I can fit the every growing integer inputs on a machine!

Please guide me to the proper discussion for this, or convince me that my worries are not neccessary.


Great question! You are right in questioning the asymptotic analysis we make nowadays in theoretical computer science.

We can even see that the problem is actually worse than at first glance, because such an analysis neglects precomputations that may take a long but constant time to complete.

Indeed, if a function taking as input $n$ bits takes $100^{100} + n$ seconds to compute a computer scientist would say that it is still in the class of efficient functions. Why, it is linear!

But if we focus on the practical aspect, this function takes an awfully long time to compute, even for small inputs!

The problem goes the other way too. If we have that for every input of length $n$ performing a certain computation takes roughly $3$ seconds, except for only one input for which it takes $2^n$ seconds, the algorithm will not be in the class of efficient algorithms, albeit it seems to do a pretty darn good job almost always.

Thus we have the right to question the validity of identifying the $P$ class with the class of efficient algorithms...

... but still everybody keeps using this as a rule of thumb, and empirical evidence backs them up.

So the disappointing answer to this question is that we do not have extremely good theoretical grounds to assert this confidently. It seems to work, but we have no exact idea of why, in the same way that we are not exactly sure of why the time-space trade offs are so ubiquitous in practice.

For an in depth review of this and other open questions in the justifications of complexity theory, I refer you to this paper by Scott Aaronson.

  • $\begingroup$ So in proving the time complexity of an algorithm, I can assume arbitrarily sized integers are equal (usually; as long as smaller input size => smaller integers involved in computation)? And the use of arbitrarily many of those integers (usually; as long as smaller input size => smaller memory)? And so on... ? $\endgroup$ Oct 16 '16 at 17:52
  • $\begingroup$ Great analysis and examples of the issue! $\endgroup$ Oct 16 '16 at 17:54
  • $\begingroup$ @EnjoysMath I do not understand what you mean by "arbitrarily sized integers are equal". Can you rephrase your question? $\endgroup$ Oct 16 '16 at 17:57

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.