complexity theory

turing showed that we could break down computation into elementary steps, and computable functions were built from combinations of these steps. the most intuitive idea for trying to understand how hard some computation is would be to try to understand the resources we need to perform these steps. classically, the resources which have been the most important are:

• time. how much time will it cost us to perform a computation?
• space. how much memory or space will the computation require?

once we have clarified how to measure resources, then the dream of computational complexity theory is to develop techniques which, given some algorithm for some computation process, will enable us to prove that the algorithm at hand is the best we can ever hope to find for the problem, at least in terms of the relevant resources.
this dream is provably impossible, in that there are some functions which provably don't have fastest algorithms in any reasonable sense.
[cite:;taken from @computability_downey_2024 chapter chapter 6 computational complexity]

  (princ
   (book-collage
    (list
     "[[blk:1718010724.5348501][arora computational complexity book]]"
     )))




  
  Computational Complexity: A Modern Approach
  Boaz Barak and Sanjeev Arora
  2009