8
$\begingroup$

I would like to understand why and when polynomial algorithms became of interest.

When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when the concept of an algorithm was discovered, or the the term algorithm used.

For instance, I've looked at some textbook of Algorithms such as the one by Cover, Leiserson, Rivest, and Stein "Introduction to Algorithms" 3rd ed. they states in the Preface "Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing".

Would it be the case that, before computers were invented, we were more interested in finding new ideas for solving problems, and were not so concerned with the time it took.

So I am interested in knowing when people became conscious of the importance of efficiency, started to study it more systematically.

Are there some reference papers on the subject, on the history of algorithms and their motivations, and on the concern with efficiency.

[note from the translator] The topic of the question may seem a bit wide, as I tried to keep the meaning without betraying the author. But it seems a good and useful general question that can be adressed with a few general remarks and some facts and examples

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm very sorry but I can't understand what you're trying to ask. $\endgroup$
    – David Richerby
    Jun 19, 2015 at 7:00
  • 2
    $\begingroup$ Maybe you would like to check Section 2 "Digression" of the famous paper Paths, trees, and flowers by Edmonds: "One can find many classes of problems, besides maximum matching and its generalizations, which have algorithms of exponential order but seemingly none better ... For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite." $\endgroup$
    – hengxin
    Jun 19, 2015 at 7:30
  • $\begingroup$ @hengxin Thank you so much, I'll read it, it seems amazing since Edmond is the author ... $\endgroup$
    – user777
    Jun 20, 2015 at 20:57
  • $\begingroup$ @DavidRicherby It is important for me that the question become clear, so I hope it is clear now ... $\endgroup$
    – user777
    Jun 20, 2015 at 20:59

3 Answers 3

Reset to default
11
$\begingroup$

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand

why and when polynomial algorithms became of interest.

I especially focus on the sub-question:

When did people realize the role and importance of efficient versus non-efficient algorithms?

Because algorithms, in its general terms, have existed since ancient times, it is hard to identify the person who is the first to highly praise the polynomial algorithms(, and when and why). However, there is a famous person who has explicitly advocated the polynomial algorithms. It is Jack Edmonds, in the paper Paths, Trees, and Flowers; 1965.

In Introduction, the author claims

We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality.

Then in the second section titled "Digression", the author

An explanation is due on the use of the words "efficient algorithm".

Then come the explanations:

There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph.

When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large, an asymptotic estimate of $\ldots$ the order of difficulty of an algorithm is theoretically important.

For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite.

However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. For one thing the task can then be described in terms of concrete conjectures.

ADDED: I have just happened to found a third-party confirmation that it was Jack Edmonds who originally advocated the polynomial algorithms.

The following is quoted from Section 2.18.1 of the book "Applied Combinatorics (second edition)" by Fred Roberts and Barry Tesman.

A generally accepted principle is that an algorithm is good if it is polynomial. This idea is originally due to Edmonds [1965].

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you @hengxin I just now know that when polynomial algorithm have been started. This would show that [computers] are the one which makes the invention of "efficient" and "non-efficient" algorithm. $\endgroup$
    – user777
    Jun 22, 2015 at 20:54
  • $\begingroup$ @user777 Placing the hard line between "polynomial" and "exponential" might have appeared in writing in 1965, but the interest for efficient vs non-efficient algorithms predates computers by many centuries, especially in algorithms for arithmetic computations, such as long-division, and precise multiplication of trigonometric values. $\endgroup$
    – Stef
    Mar 14 at 10:33
7
$\begingroup$

in addition to the other standard credits eg to Edmonds (1965); some obscure CS history that few are aware of and is not written in many (any?) textbook accounts so far, and is rarely cited, (maybe not even much on stackexchange CS sites): Gödel is given credit as being one of the 1st mathematicians/ "scientists" (from the modern CS pov) who 1st considered the idea of efficiency of algorithms, and polynomial growth, and Landau notation applied to algorithmic complexity, in a 1956 letter to Von Neumann. in a sense it is one of the first written/ posthumously published musings on complexity theory. the letter was not rediscovered for its significance to CS until decades later, apparently noted by Sipser in 1992. contents/ translation/ some more details in comments on following. (it would be nice for a complexity theorist expert to write a detailed analysis/ interpretation esp from historical pov, but have not seen one. cannot locate further analysis in RJ Liptons blog.)

The Gödel Letter (RJ Lipton blog)

The letter was originally written in German. Mike Sipser’s translation can be found in “The History and the Status of the P versus NP Question”, in the 24th STOC proceedings, 1992, pp. 603-618.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ also: "...earlier von Neumann [38], in 1953, distinguished between polynomial-time and exponential-time algorithms." P vs NP problem / Cook, Claymath. [38] J. von Neumann, A certain zero-sum two-person game equivalent to the optimal assignment problem, in Contributions to the Theory of Games II, H.W. Kahn and A.W. Tucker, eds. Princeton Univ. Press, Princeton, NJ, 1953, 5–12. $\endgroup$
    – vzn
    Jun 23, 2015 at 18:01
  • $\begingroup$ Maybe polynomial growth and Landau complexity, but certainly not "who 1st considered the idea of efficiency of algorithms". For instance, the whole point of logarithm, introduced in a published book in 1614, was to transform long-multiplication into long-addition, transforming a quadratic algorithm into a linear algorithm, especially useful for computation of products of trigonometric values. $\endgroup$
    – Stef
    Mar 14 at 9:25
  • $\begingroup$ Division is also an interesting example. In Elements, Euclid described the algorithm for division using repeated subtraction. This algorithm has been improved upon over the centuries. In 1202, in Liber Abaci, Fibonacci described a more efficient method that relies on prime factorisation. $\endgroup$
    – Stef
    Mar 14 at 9:29
4
$\begingroup$

People have been conducting calulations for centuries, and calculations in general follow some algorithms. It does not matter who or what calculates - computing takes time (and time is one of the resources you can never get back, once lost.) And to save more time you need to have better algorithms.

Can you imagine building atomic reactors without even simplest calulators to help? People did it (and many more amazing things), and they often spent literally months just calculating. With some better algorithms for their problems they could cut that to weeks, days or even hours.

Did it matter before computers? Yes, a lot! Even more than today as they actually needed people to compute, which is much more costly than having your PC do that. Faster algorithms are faster for humans, computers or anything else able of conducting them.

Also note that algorithms are not only related to computing. An algorithm is basically a recipe of "How to do something step-by-step" with a desired level of detail. So if people tried to make something easier/faster - they often tried to improve their algorithms of doing it (even if they did not look at it this way.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ @yakuya Thank you so much for your answer. it's so helpful. let me explain to you something. When Euler solved the well-known problem known as "The Seven Bridges of Konigsberg" using so-called Graph Theory, then did you call for what he did as "algorithm" or not? Becasue according to what you've said algorithm is just "step-by-step with details to save time", these details could be "idea" to solve difficult problem of course, if algorithm are not "related" to computation, then if we draw a Venn Diagram, then which relations you supposed "algorithms" have with "computations"; for me DIDJOINT $\endgroup$
    – user777
    Jun 20, 2015 at 20:53
  • 1
    $\begingroup$ The remarks on matrix multiplications are wrong, since the O(n2,4) matrix multiplication algorithms are unusable, due to their constant. The only one usable on computers is Strassen's, and I do not know whether it is really practical when multiplying by hand. $\endgroup$
    – babou
    Jun 21, 2015 at 9:54
  • $\begingroup$ @babou I failed to realize those facts about Coppersmith-Winograd's algorithm, so I removed the paragraph now, thank you. Author: I am not really sure what you mean. I can, however, repeat that an algorithm is a step-by-step description of a solution with a desired level of detail. Example: 1. Take a tea-bag, 2. Boil water, 3. put tea-bag into a cup, 4. pour water into that cup is a (not-too-detailed) tea making algorithm. Computations for me are operations on numbers (or things possible to represent as such) leading to some results. Should I clarify anything? $\endgroup$
    – 3yakuya
    Jun 21, 2015 at 20:43
  • 1
    $\begingroup$ @babou I've tried it and concluded: yes, Strassen's algorithm is practical when multiplying by hand, even for 4x4 matrices. Below that size, use the naive n^3 algorithm. Also, Strassen's requires a better organisation to keep track of the intermediate results properly (especially for large matrices). For a large matrix, Strassen's is definitely faster. For a 4x4 matrix, if it's your first time using Strassen's, you're probably not going to be faster than someone who uses the naive algorithm, but if you've already used Strassen's a few times and are well-organised, then you should be faster. $\endgroup$
    – Stef
    Mar 14 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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