Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
research [2016-10-30] – junheechoresearch [2017-11-10] (current) – external edit 127.0.0.1
Line 7: Line 7:
 Mere computability investigates the algorithmic solvability of (decision or function) problems in principle. Although this is often already difficult enough to establish (and for many natural problems even wrong), in practice one usually wants efficient a solution: by devising data structures and algorithms and analyzing their worst-case behavior. Here, exponential asymptotic growth is generally considered inefficient -- yet a refined diagonalization argument (the hierarchy theorem due to Hartmanis and Stearns) proves that some decidable problems may require such running times for their solution. This raises the question of optimality of an algorithm, that is, how close it comes asymptotically to the intrinsic difficulty of the problem it solves. Put differently: is it worth while to try improving it or not? Mere computability investigates the algorithmic solvability of (decision or function) problems in principle. Although this is often already difficult enough to establish (and for many natural problems even wrong), in practice one usually wants efficient a solution: by devising data structures and algorithms and analyzing their worst-case behavior. Here, exponential asymptotic growth is generally considered inefficient -- yet a refined diagonalization argument (the hierarchy theorem due to Hartmanis and Stearns) proves that some decidable problems may require such running times for their solution. This raises the question of optimality of an algorithm, that is, how close it comes asymptotically to the intrinsic difficulty of the problem it solves. Put differently: is it worth while to try improving it or not?
  
-To avoid possible confusion with heuristics: We consider here as algorithm only one formally correct with an asymptotic running time bound provably obeyed on every possible input.+To avoid possible confusion with //heuristics// or //methods//: We consider here as algorithm only one formally correct with an asymptotic running time bound provably obeyed on every possible input.
  
 This 'intrinsic difficulty' of a problem is called its complexity; and the running time of any algorithm solving it constitutes (asymptotically) an upper bound. Conversely, if this can be complemented by a matching lower bound, it means that the algorithm is optimal. This 'intrinsic difficulty' of a problem is called its complexity; and the running time of any algorithm solving it constitutes (asymptotically) an upper bound. Conversely, if this can be complemented by a matching lower bound, it means that the algorithm is optimal.